算法 - 不确定层级含有children节点的数组结构如何遍历？

问题描述

问 题

数据结构如下：

[
    {
        'xx': 'oo',
        'children': [
            {
                'xx': 'oo',
                'children': [
                    {
                        'xx': 'oo',
                        'children': []
                    },
                ]
            },
            {
                'xx': 'oo',
                'children': []
            }
        ]
    },
    {
        'xx': 'oo',
        'children': []
    }
]

层级数量不确定，每个节点都有一个children节点，children节点为不确定数量的数组，children节点的结构跟父级结构一样，如果数据量不大的话可以很容易用递归去遍历，但我发现这个并不能用尾递归去优化，那如果数据量很大的话就有爆栈的可能性，这种情况下该如何处理呢？

解决方案

树遍历可用循环代替递归。广度优先用一个队列：

bfs(root)
  q ← empty_queue()
  q.enqueue(root)
  while (q not empty)
    node ← q.dequeue()
    visit(node.xx)
    for x in node.children
      if (x ≠ {}) q.enqueue(x)

调用方式：

bfs({xx:oo, your_array})

深度拷贝的话，可以用两个队列，一个盛放原对象，一个盛放目标对象，做亦步亦趋的同步出队入队，原对象遍历的同时目标对象完成拷贝。下面代码需要借用类似C语言中指针的语义，x.pointer代表x这个对象本身，而不是x的值。

copy(root)
  dup ← {xx:oo, children:[]}
  q1 ← empty_queue
  q2 ← empty_queue
  q1.enqueue(root)
  q2.enqueue(dup.pointer)
  while q1. not_empty()
    src ← q1.dequeue()
    ptr ← q2.dequeue()
    ptr.xx ← src.xx
    ptr.children ← src.children
    for i from 1 to src.children.size()
      if (src.children[i] ≠ {})
        q1.enqueue(src.children[i])
        q2.enqueue(ptr.children[i].pointer)
  return dup

这篇关于算法 - 不确定层级含有children节点的数组结构如何遍历？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！