走路一棵树,父母先行

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

广度优先搜索