这篇文章的后序遍历是否正确？

Question

3

我有一个问题，不明白如何后序遍历一棵树林。它的定义是：（出自Rohit Khurana的C语言数据结构第330页）

这里是树林的图示：

书中提到的树林后序遍历结果为：

C F E D B Q P Z Y X A

但我认为P在错误的位置上，正确答案应该是：

C F E D B Q Z Y X P A

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

谢谢。

- Fatemeh Karimi

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dgkr · Answer 1

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

根据这个陈述，书中的答案是正确的。将访问根节点作为最后一个操作仅适用于森林中的第一棵树。

您所建议的是，将此语句视为适用于森林中的其他树。

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