二叉树前序遍历理解

Question

这个作业要求我写树的前序遍历，但我很困惑它是如何工作的，因为它访问节点、左子树、右子树，但它不会到达中间。它会跳过它还是给出错误？还是我直接忽略中间的？

Answer 1

这不是二叉树

Binary 是英语，意思是“与 2 有关”。因此，二叉树是这样的树：任何节点要么是叶子（没有子节点），要么有“恰好 2 个子节点”。本质上，所有节点都有 0 或 2 个子节点。 你的图片不是二叉树：节点 D 有 3 个子节点。节点 B 只有 1。

但是你可以预购遍历就好了

前序遍历与特定的二叉树无关。这是一种适用于树的算法。树不需要是二叉树。

预订此产品：

从根源开始。

1. 发出当前“选定”节点的值。
2. 按从左到右的顺序浏览它的子项。对于每个孩子，在步骤 2 中递归应用此算法。
这就是您在这里要做的全部事情。在这里应用它：

从根源开始。

1. 发出它的价值：我们有
"A"
2. 循环其直接子级 - 将此算法应用于 B 和 C。
到 B 的递归将最终打印

"BDHIJ"

，到 C 的递归将打印

"CEG"

。最终结果是

"ABDHIJCEG"

。不存在“跳过中间节点”这样的事情，除非您正在阅读一些教程或解释说“首先迭代左侧，然后迭代右侧”。这些术语（“左侧”和“右侧”）假定是二叉树。没有提到“中间节点”，因为解释假设是二叉树；二叉树没有

有

中间节点。 某些遍历，例如有序遍历，

不适用于非二叉树

。这是因为它们访问左侧，然后是节点本身，然后是右侧。这对于非二叉树来说没有“意义”。但是，预排序并不能做到这一点，因此可以简单地扩展到 N 叉树。