8

访问链接树的所有节点的最佳方法是什么（所有节点都引用父节点和所有子节点，根节点的父节点为 null），这样在其任何祖先之前都不会访问节点？非递归的布朗尼点。

4

10 回答 10

6

伪代码：

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

广度优先搜索

于 2009-10-23T23:04:34.363 回答
3

您正在寻找预购遍历。我认为您可以使用队列非递归地执行此操作：。在伪代码中：

创建一个空队列，然后推送根节点。

while nonempty(q)
  node = pop(q)
  visit(node)
  foreach child(node)
    push(q,child)
于 2009-10-23T23:03:48.467 回答
3

如果您有所有子节点和父节点的链接，那么非递归算法就相当简单了。忘记你有一棵树。可以把它想象成一个迷宫，其中每个父子链接都是从一个路口到另一个路口的普通双向走廊。走完整个迷宫所需要做的就是在每个路口转入左侧的下一个走廊。（或者，把它想象成用你的左手总是接触左侧的墙壁走迷宫）。如果您从根结点开始（并向任何方向移动），您将走完整棵树，总是先于孩子拜访父母。在这种情况下，每个“走廊”将被行驶两次（一个方向和另一个方向），每个“路口”（节点）将被访问的次数与加入它的“走廊”的数量一样多。

于 2009-10-23T23:08:09.363 回答
1

使用一组节点。将根放入集合中以启动。然后在一个循环中，从集合中拉出一个节点，访问它，然后将其子节点放入集合中。当集合为空时，您就完成了。

于 2009-10-23T23:02:22.777 回答
1

在伪代码中：

currentList = list( root )
nextList = list()
while currentList.count > 0:
    foreach node in currentList:
        nextList.add(node.children)
    currentList = nextList
于 2009-10-23T23:03:45.737 回答
1

如果您从根节点开始，并且只访问您已经访问过的节点的父/子，则无法遍历树以便您在访问其祖先之前访问一个节点。

任何类型的遍历、深度优先（基于递归/堆栈）、广度优先（基于队列）、深度限制，或者只是将它们拉出无序集合，都可以。

“最佳”方法取决于树。广度优先适用于一棵树枝很少的非常高的树。深度优先适用于有许多树枝的树。

由于节点实际上有指向其父节点的指针，因此还有一个常量内存算法，但速度要慢得多。

于 2009-10-23T23:06:02.270 回答
1

我不同意广度优先搜索，因为空间复杂度通常是该特定搜索算法的祸根。可能使用迭代深化算法是此类使用的更好替代方案，它涵盖与广度优先搜索相同的遍历类型。在处理广度优先搜索的边缘方面存在细微差别，但（伪）编码应该不会太难。

参考： http ://en.wikipedia.org/wiki/Iterative_deepening

于 2009-10-23T23:33:58.843 回答
1

这是一种真正的非递归方法：没有堆栈，恒定空间。此 Python 代码假定每个节点都包含一个子节点列表，并且节点对象不定义相等性，因此“索引”函数正在比较身份：

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

我相信它可以稍微完善一下，使其更简洁，更易于阅读，但这就是要点。

于 2009-10-26T15:02:46.767 回答
0

在根节点（级别 0）建立一个节点列表，依次遍历每个节点并寻找直接子节点（其父节点是我们当前正在查找的节点）（级别 1），当完成级别 0 时继续迭代第 1 级，依此类推，直到没有剩余的未访问节点。

于 2009-10-23T23:01:57.257 回答