遛树，父母先行

Question

访问链接树的所有节点（所有节点都有对父节点和所有子节点的引用，根节点将 null 作为父节点）的最佳方法是什么，以便在其任何祖先之前不会访问任何节点？非递归的布朗尼点。

Answer 1

伪代码：

NodesToVisit = some stack or some list
NodesToVisit.Push(RootNode)

While NodesToVisit.Length > 0
{
   CurNode = NodesToVisit.Pop()
   For each Child C in CurNode
        NodesToVisit.Push(C)
   Visit(CurNode) (i.e. do whatever needs to be done)
}

编辑：是否递归？
从技术上讲，正如 AndreyT 和其他人在这篇文章中指出的那样，这种方法是递归算法的一种形式，其中使用显式管理的堆栈来代替CPU 堆栈的位置以及在 While 循环级别进行递归的位置。也就是说，它与递归实现本身在一些微妙但重要的方面有所不同：

• 只有“变量”被推入堆栈；堆栈上没有“堆栈帧”和关联的返回地址，唯一的“返回地址”隐含在 while 循环中，并且只有一个实例。
• “堆栈”可以用作列表，从而可以在列表中的任何位置获取下一个“帧”，而无需以任何方式中断逻辑。

Answer 2

广度优先搜索

Answer 3

您正在寻找预购遍历。我认为你可以非递归地做到这一点
队列:.用伪代码来说：

创建一个空队列，然后推送根节点。

while nonempty(q)
  node = pop(q)
  visit(node)
  foreach child(node)
    push(q,child)

Answer 4

如果您有到所有子级和父级的链接，那么非递归算法就相当简单了。只是忘记你有一棵树。可以把它想象成一个迷宫，其中每个父子链接都是从一个路口到另一个路口的普通双向走廊。要走完整个迷宫，你需要做的就是在每个路口拐进左边的下一个走廊。 （或者，可以将其视为在迷宫中行走，左手始终接触左侧的墙壁）。如果您从根结点开始（并向任何方向移动），您将遍历整棵树，始终先访问父母，然后再访问孩子。在这种情况下，每个“走廊”将被行驶两次（在一个方向和另一个方向），并且每个“交汇处”（节点）将被访问与加入它的“走廊”一样多的次数。

Answer 5

使用一组节点。将根放入集合中以启动。然后在循环中，从集合中拉出一个节点，访问它，然后将其子节点放入集合中。当集合为空时，您就完成了。

Answer 6

在伪代码中：

currentList = list( root )
nextList = list()
while currentList.count > 0:
    foreach node in currentList:
        nextList.add(node.children)
    currentList = nextList

Answer 7

如果您从根节点开始，并且仅访问已访问过的节点的父节点/子节点，则无法遍历树以便在访问其祖先节点之前访问节点。

任何类型的遍历，深度优先（基于递归/堆栈），广度优先（基于队列），深度限制，或者只是将它们从无序集合中取出，都可以。

“最佳”方法取决于树。对于一棵非常高、树枝很少的树来说，广度优先很有效。深度优先对于有很多分支的树来说效果很好。

由于节点实际上有指向其父节点的指针，因此还有一种常量内存算法，但速度要慢得多。

Answer 8

我不同意广度优先搜索，因为空间复杂度通常是该特定搜索算法的祸根。对于这种类型的使用，使用迭代加深算法可能是更好的选择，并且它涵盖了与广度优先搜索相同类型的遍历。在处理广度优先搜索的边缘方面存在细微差别，但（伪）编码应该不会太难。

参考：
http://en.wikipedia.org/wiki/Iterative_deepening

Answer 9

这是一种真正的非递归方法：没有堆栈，空间恒定。这段Python代码假设每个节点都包含一个子节点列表，并且节点对象没有定义相等性，因此“索引”函数正在比较身份：

def walkTree(root, visit_func):
    cur  = root
    nextChildIndex = 0

    while True:
        visit_func(cur)

        while nextChildIndex >= len(cur.children) and cur is not root:
            nextChildIndex = cur.parent.children.index(cur) + 1
            cur  = cur.parent

        if nextChildIndex >= len(cur.children):
            break

        cur = cur.children[nextChildIndex]
        nextChildIndex = 0

我确信它可以稍微完善一下，变得更加简洁和更容易阅读，但这就是要点。

Answer 10

在根节点（级别 0）建立一个节点列表，依次迭代每个节点并查找直接子节点（其父节点是我们当前正在查找的节点）（级别 1），完成级别 0 后继续迭代级别 1，依此类推，直到没有剩余的未访问节点。