如何最好地访问链接树的所有节点(所有节点都有对父节点和所有子节点的引用,根节点的父节点为null),以便在任何祖先节点之前不访问任何节点?非递归方法将获得额外奖励。
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 nonempty(q)
node = pop(q)
visit(node)
foreach child(node)
push(q,child)
伪代码如下:
currentList = list( root )
nextList = list()
while currentList.count > 0:
foreach node in currentList:
nextList.add(node.children)
currentList = nextList
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
我相信这可以再打磨一下,让它更简洁易读,但这就是要点。
如果您从根节点开始,并且只访问已经访问过的节点的父节点/子节点,则无法遍历树,以便在访问其祖先之前访问节点。
任何类型的遍历,深度优先(递归/基于堆栈),广度优先(基于队列),有限深度或仅从无序集合中提取它们都可以工作。
“最佳”方法取决于树。对于分支较少但非常高的树,广度优先将很好地工作。对于具有许多分支的树,深度优先将很好地工作。
由于节点实际上具有指向其父节点的指针,因此还存在一种常量内存算法,但速度要慢得多。
我不太赞同广度优先搜索算法,因为空间复杂度通常是这种特定搜索算法的弊端。对于这种情况,可能使用迭代加深算法是更好的选择,它涵盖了与广度优先搜索相同类型的遍历。在处理边缘节点方面,与广度优先搜索有一些细微的差别,但应该不难编写出(伪)代码。
在根节点(层级0)建立一个节点列表,依次迭代每个节点并查找直接子节点(其父节点是我们当前正在查找的节点)(层级1),当完成层级0后,继续迭代层级1,以此类推,直到没有剩余未访问的节点。