遍历树，先父节点后子节点

Question

如何最好地访问链接树的所有节点（所有节点都有对父节点和所有子节点的引用，根节点的父节点为null），以便在任何祖先节点之前不访问任何节点？非递归方法将获得额外奖励。

- George

---

相关：https://dev59.com/GnRA5IYBdhLWcg3w_DLF - ire_and_curses

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

- mjv

---

好的。这不是一个学术问题，而是一个实际问题。这个答案令我满意，而且不需要我思考或进一步阅读。谢谢。也许以后我有时间会再去思考，但没关系，这很有用...任务完成。再次感谢 :) - George

Answer 2

广度优先搜索

- Mercurybullet

Answer 3

您正在寻找一个先序遍历。我认为您可以使用队列来非递归地实现它。伪代码如下：

创建一个空队列，然后将根节点入队。

while nonempty(q)
  node = pop(q)
  visit(node)
  foreach child(node)
    push(q,child)

- Jim Lewis

---

这将是一个非递归实现的递归算法。用显式栈替换隐式栈并不会将递归算法转变为非递归算法。事实上，它根本不会改变算法。你上面所写的显然是递归的（就算是算法而言）。 - AnT stands with Russia

通常人们说不想要递归时，指的是函数层面的递归。这样做满足了这个条件。 - JSBձոգչ

有时候是这样的。然而，我们在这里考虑的问题是专门设计的，以允许真正的非递归解决方案（即非递归算法）。死结点的存在是一个明显的线索。你的“非递归”解决方案没有使用父指针。难道你不想知道它们为什么会出现吗？它们的存在是为了允许真正的非递归解决方案，具有O(1)的内存需求。 - AnT stands with Russia

但大多数情况下 - 不需要递归。通常，当人们说他们不想要递归时，他们的意思是他们不想要递归所需的内存，即他们不想要一个非常量大小的数据结构来存储“子问题”，无论是FIFO、LIFO还是其他什么。 - AnT stands with Russia

@AndreT：我从未听说过“非递归”被用来表示“常数空间要求”，就像你所认为的那样。因此，我不同意你的用法是“典型的”。 - Jim Lewis

Answer 4

如果您有所有子节点和父节点的链接，那么非递归算法就非常简单。只需忘记您有一棵树。将其视为迷宫，其中每个父-子链接都是从一个交叉口到另一个交叉口的普通双向走廊。要遍历整个迷宫，您只需要在每个交叉口左侧进入下一个走廊。(或者，将其视为始终触摸左侧墙壁行走的迷宫)。如果您从根节点开始（并朝任何方向移动），则始终访问父节点后再访问子节点，并且此时每个“走廊”将被两次遍历（前进和后退），每个“交叉口”（节点）将被访问与之相连的“走廊”数相同的次数。

- AnT stands with Russia

---

这是我提到的常量内存算法。 - Artelius

Answer 5

伪代码如下：

currentList = list( root )
nextList = list()
while currentList.count > 0:
    foreach node in currentList:
        nextList.add(node.children)
    currentList = nextList

- JSBձոգչ

Answer 6

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

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

我相信这可以再打磨一下，让它更简洁易读，但这就是要点。

- divegeek

Answer 7

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

- Keith Randall

---

你需要一个FIFO的数据结构，而不仅仅是任何旧容器，以保证先序条件。 - Jim Lewis

问题中没有这样的要求。 - Keith Randall

Answer 8

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

任何类型的遍历，深度优先（递归/基于堆栈），广度优先（基于队列），有限深度或仅从无序集合中提取它们都可以工作。

“最佳”方法取决于树。对于分支较少但非常高的树，广度优先将很好地工作。对于具有许多分支的树，深度优先将很好地工作。

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

- Artelius

---

OP说：“在访问其祖先节点之前，没有任何节点被访问。”因此应该反过来。 - AnT stands with Russia

也许不是这样。我认为在你的第一句话中，你声称问题无法解决，因为我假设你误解了探视顺序要求，这是不可能满足的。 - AnT stands with Russia

我想说明的是，任何遍历（从根节点开始）都能满足要求。 - Artelius

Answer 9

我不太赞同广度优先搜索算法，因为空间复杂度通常是这种特定搜索算法的弊端。对于这种情况，可能使用迭代加深算法是更好的选择，它涵盖了与广度优先搜索相同类型的遍历。在处理边缘节点方面，与广度优先搜索有一些细微的差别，但应该不难编写出（伪）代码。

Reference: http://en.wikipedia.org/wiki/Iterative_deepening

- mduvall

---

+1 是因为你考虑到了空间复杂度，但是为什么不直接使用深度优先搜索呢？ - Artelius

实际应用中，许多树往往比它们的“宽度”更深，尤其是在人工智能决策过程中。问题没有说明树是否有限，但你可能会遇到循环。迭代加深法受欢迎的原因之一是它是完备的（可以找到解决方案）。 - mduvall

Answer 10

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

- Wayne Cornish