遛树，父母先行

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代码假设每个节点都包含一个子节点列表，并且节点对象没有定义相等性，因此'index'函数正在比较标识：

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级，依此类推，直到你没有剩余的未访问节点。