二叉树遍历

遍历指的是访问树的所有节点。有三种遍历二叉树的标准方法。如下所示：

1. 前序遍历
2. 后序遍历
3. 中序遍历

1. 前序遍历：二叉树的前序遍历是一个递归过程。树的前序遍历是

• 访问树的根节点。
• 以前序遍历遍历左子树。
• 以前序遍历遍历右子树。

2. 后序遍历：二叉树的后序遍历是一个递归过程。树的后序遍历是

• 以后序遍历遍历左子树。
• 以后序遍历遍历右子树。
• 访问树的根节点。

3. 中序遍历：二叉树的中序遍历是一个递归过程。树的中序遍历是

• 以中序遍历遍历左子树。
• 访问树的根节点。
• 以中序遍历遍历右子树。

示例：确定如图所示二叉树的前序、后序和中序遍历

解决方案：树的前序、后序和中序遍历如下所示

算法

(a) 在给定树的中序和前序遍历的情况下绘制唯一二叉树的算法

1. 我们知道二叉树的根节点是其前序遍历中的第一个节点。绘制树的根节点。
2. 要找到根节点的左子节点，首先，使用中序遍历找到二叉树左子树中的节点。（中序遍历中位于根节点左侧的所有节点都是左子树的节点）。之后，通过选择左子树的前序遍历中的第一个节点来获得根节点的左子节点。绘制左子节点。
3. 以同样的方式，使用中序遍历找到二叉树右子树中的节点。然后，通过选择右子树的前序遍历中的第一个节点来获得右子节点。绘制右子节点。
4. 对每个新节点重复步骤 2 和 3，直到在前序遍历中访问了每个节点。最后，我们得到一个唯一的树。

示例：当给定中序和前序遍历时，绘制唯一的二叉树，如下所示

解决方案：我们知道二叉树的根节点是前序遍历中的第一个节点。现在，在中序遍历中检查 A，所有位于 A 左侧的节点都是左子树的节点，所有位于 A 右侧的节点都是右子树的节点。读取前序遍历中的下一个节点，并根据根节点检查其位置，如果它在根节点的左侧，则将其绘制为左子节点，否则将其绘制为右子节点。对每个新节点重复上述过程，直到读取前序遍历的所有节点，最后我们得到如图所示的二叉树

(b) 在给定树的中序和后序遍历的情况下绘制唯一二叉树的算法

1. 我们知道二叉树的根节点是其后序遍历中的最后一个节点。绘制树的根节点。
2. 要找到根节点的右子节点，首先，使用中序遍历找到二叉树右子树中的节点。（中序遍历中位于根节点右侧的所有节点都是右子树的节点）。之后，通过选择右子树的后序遍历中的最后一个节点来获得根节点的右子节点。绘制右子节点。
3. 以同样的方式，使用中序遍历找到二叉树左子树中的节点。然后，通过选择左子树的后序遍历中的最后一个节点来获得左子节点。绘制左子节点。
4. 对每个新节点重复步骤 2 和 3，直到在后序遍历中访问了每个节点。访问最后一个节点后，我们得到一个唯一的树。

示例：为给定的中序和后序遍历绘制唯一的二叉树，如下所示

解决方案：我们知道二叉树的根节点是后序遍历中的最后一个节点。因此，在一个根节点中。

现在，检查中序遍历，我们知道根节点位于中心，因此中序遍历中位于根节点左侧的所有节点都是左子树的节点，而所有位于根节点右侧的节点都是右子树的节点。

      现在，从后序遍历中向后访问下一个节点，并检查其在中序遍历中的位置，如果它位于根节点的左侧，则将其绘制为左子节点，如果它位于右侧，则将其绘制为右子节点。

对每个新节点重复上述过程，我们得到如图所示的二叉树

(c)将一般树转换为二叉树的算法

1. 从根节点开始，树的根也是二叉树的根。
2. 树中根节点（从左侧开始）的第一个子节点 C₁ 是二叉树中根节点 C₁ 的左子节点，C₁ 的兄弟节点是 C₁ 的右子节点，依此类推。
3. 对每个新节点重复步骤 2。

示例：将如图所示的以下树转换为二叉树。

解决方案：树的根是二叉树的根。因此，A 是二叉树的根。现在，B 成为二叉树中 A 的左子节点，C 成为 B 的右子节点，D 成为 C 的右子节点，E 成为二叉树中 D 的右子节点，同样应用该算法，我们得到如图所示的二叉树