走在树上，父母第一 [英] Walking a tree, parent first

问题描述

访问链接树的所有节点的最佳方式是什么(所有节点都引用父节点和所有子节点，根节点的父节点都为空)，以便在访问其任何祖先之前不访问任何节点？非递归的布朗尼点。

推荐答案

伪码：

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

这篇关于走在树上，父母第一的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！