V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
onlinewjm
V2EX  ›  问与答

不懂就问系列:如何不递归遍历层级结构?

  •  
  •   onlinewjm · 2019-04-24 15:15:22 +08:00 · 1834 次点击
    这是一个创建于 2029 天前的主题,其中的信息可能已经有所发展或是发生改变。

    Souce Data:

    [
      {
        "Id": 1,
        "Name": "顶级",
        "Pid": 0,
        "Children": [
          {
            "Id": 2,
            "Name": "层级二 A",
            "Pid": 1,
            "Children": [
              {
                "Id": 5,
                "Name": "层级三 A",
                "Pid": 2,
                "Children": null
              }
            ]
          },
          {
            "Id": 3,
            "Name": "层级二 B",
            "Pid": 1,
            "Children": [
              {
                "Id": 4,
                "Name": "层级三 B",
                "Pid": 3,
                "Children": null
              }
            ]
          }
        ]
      }
    ]
    

    Target Data:

    [{
        "Id": 1,
        "Name": "顶级",
        "Pid": 0
    },{
        "Id": 2,
        "Name": "层级二 A",
        "Pid": 1
    }, {
        "Id": 5,
        "Name": "层级三 A",
        "Pid": 2
    },{
        "Id": 3,
        "Name": "层级二 B",
        "Pid": 1
    }, {
        "Id": 4,
        "Name": "层级三 B",
        "Pid": 3
    }]
    
    8 条回复    2019-04-24 23:07:07 +08:00
    SorcererXW
        1
    SorcererXW  
       2019-04-24 15:34:58 +08:00 via Android
    就模拟递归栈,用个栈来存,每次弹出栈顶节点,将此节点的所有子节点入栈。循环直到栈为空
    ywcjxf1515
        2
    ywcjxf1515  
       2019-04-24 15:59:43 +08:00 via iPad
    和上面类似的,用一个队列来存,对于队列中的每个节点,把其子节点入队,之后把该节点出队,循环直到队列为空。参见深度优先搜索和广度优先搜索。
    kljsandjb
        3
    kljsandjb  
       2019-04-24 16:09:43 +08:00 via iPhone
    用 stack
    mugglezzz
        4
    mugglezzz  
       2019-04-24 16:09:45 +08:00
    onlinewjm
        5
    onlinewjm  
    OP
       2019-04-24 17:34:48 +08:00
    @ywcjxf1515
    @SorcererXW
    @kljsandjb

    感谢老哥指点~
    rookiebulls
        6
    rookiebulls  
       2019-04-24 18:50:38 +08:00 via iPhone
    搭车问一下,如何把 target data 转为 sourcee data
    smdbh
        7
    smdbh  
       2019-04-24 21:28:27 +08:00 via iPhone
    广度 vs 深度 遍历
    reself
        8
    reself  
       2019-04-24 23:07:07 +08:00 via Android
    用队列。
    函数调用就会有局部信息的入栈出栈,只不过是编译器帮你完成了而不是自己显式地去入栈出栈而已。
    扩展一下,层级结构是树状,树是也是一种图。图遍历时用栈记录路径对应着深入遍历,用队列则对应着广度遍历,很有意思的。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2829 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 00:23 · PVG 08:23 · LAX 16:23 · JFK 19:23
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.