树遍历

树遍历是指我们访问给定树中每个节点的方式。根据遍历的方式，我们可以遵循三种不同的遍历方式。这些遍历在很多方面都非常重要。用于表达式评估的波兰语符号转换就是使用树遍历的最常见例子之一。

中序遍历

无序树遍历首先访问左节点，然后访问根节点，接着访问右节点。如此递归访问每个节点。与根节点值相比，左节点存储的值较小，而右节点存储的值则比根节点大。因此，当我们应用无序遍历时，我们得到的是一个排序列表。这就是为什么到目前为止，我们的二叉树遍历显示的是一个已排序的数字列表。这部分遍历实际上就是无序树遍历的例子。无序树遍历遵循以下原则：

  1. 通过递归调用 in-order 函数来遍历左子树。

  2. 显示根（或当前节点）的数据部分。

  3. 通过递归调用 in-order 函数来遍历右子树。

image 2023 11 08 10 51 11 919

前面的树将显示 A、B、C、D、E、F、G、H 和 I 作为输出，因为它是按顺序遍历的。

先序遍历

在先序遍历中，首先访问根节点，然后访问左节点，最后访问右节点。先序遍历的原理如下：

  1. 显示根节点（或当前节点）的数据部分。

  2. 通过递归调用 pre-order 遍历左侧子树。

  3. 通过递归调用 pre-order 遍历右侧子树。

image 2023 11 08 10 55 44 084

前面的树将以 F、B、A、D、C、E、G、I 和 H 作为输出，因为它是按先序遍历的。

后序遍历

在后序遍历中，根节点最后被访问。先访问左节点，然后访问右节点。后序遍历的原理如下：

  1. 通过递归调用 post-order 遍历左侧子树。

  2. 通过递归调用 post-order 遍历右侧子树。

  3. 显示根节点（或当前节点）的数据部分。

image 2023 11 08 10 57 18 530

前面的树将会有 A、C、E、D、B、H、I、G 和 F 的输出，因为它是以后序方式遍历的。

现在，让我们在 BST 类中实现遍历逻辑：

Unresolved include directive in modules/ROOT/pages/ch06/ch6-09.adoc - include::example$Chapter06/6.php[]

现在，如果我们为之前的二叉搜索树运行三种不同的遍历方法，下面是运行遍历部分的代码：

Unresolved include directive in modules/ROOT/pages/ch06/ch6-09.adoc - include::example$Chapter06/6.php[]

这将在命令行中产生以下输出：

10 3 6 8 12 13 15 36
3 6 8 10 12 13 15 36
3 6 8 12 13 15 36 10