algorithm - 走路一棵树， parent 先行

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 循环中，并且只有一个实例。
• “堆栈”可以用作列表，下一个“帧”可以在列表中的任何位置获取，而不会以任何方式破坏逻辑。