algorithm - 这个后序森林遍历是否正确？

Question

我在理解如何遍历森林后序时遇到问题。它的定义是:(source: Data structures using C by Rohit Khurana page 330)

1. 以树后序遍历第一棵树的子树。

2. 按树后序遍历F的剩余树。

3. 访问F的第一棵树的根节点。

这里是森林:

而书中提到的它的后序遍历是:

C F E D B Q P Z Y X A

但我认为 P 的位置不对，正确答案是:

C F E D B Q Z Y X P A

我想知道我的答案是否正确，或者书上的答案是否正确，为什么是正确的？？

谢谢，

Answer 1

1. 访问F的第一棵树的根节点。

按照这个说法，书上的答案是正确的。作为最后一个 Action 访问根节点只对森林的第一棵树有效。

你的意思是说这个陈述对森林中的其他树木也有效。

在您的示例中，在输出 Q 之后，您不输出 P，而是在 A 之前输出它。但是，P 是 F 的第二棵树的根，而不是第一棵树。因此，您应该在 Q 之后立即输出 P，而不是在 A 之前的末尾。