不使用栈进行中序遍历

在任何数据结构中，遍历都是一个重要的操作。在遍历操作中，我们至少遍历一次数据结构中的每个元素。遍历操作在数据结构上的各种其他操作（如搜索）中扮演着非常重要的角色。我们需要至少访问一次数据结构的每个元素，以将每个传入的元素与我们想要在数据结构中找到的键进行比较。

与任何其他数据结构一样，树数据也需要遍历才能访问每个元素，这些元素被称为树数据结构的节点。根据访问树节点​​的顺序以及用于遍历树的数据结构类型，有不同的遍历树的方法。

遍历树涉及各种数据结构，因为遍历树涉及以某种方式迭代所有节点。由于从给定节点遍历或访问树的下一个节点可能有多种方式，因此存储一个节点以进一步遍历，并存储其余节点以在需要时回溯树的可能路径就变得很重要。

正如我们所知，回溯不是一种线性方法，因此我们需要不同的数据结构来遍历整个树。

树遍历的类型

栈和队列是用于遍历树的主要数据结构。因此，根据访问树节点的顺序，树遍历的不同类型是：

1. 深度优先搜索树遍历
   • 前序树遍历。
   • 后序树遍历。
   • 中序树遍历。
   • 逆前序树遍历。
   • 逆后序树遍历。
   • 逆中序树遍历。
2. 广度优先搜索树遍历。

现在，我们将重点介绍中序树遍历类型。所有三种类型：中序树遍历、前序树遍历和后序树遍历，在访问树的根节点时有所不同，例如：

• 在前序树遍历中，首先访问树的根节点，然后是左节点（或子树）和右节点（或子树）。
• 在中序树遍历中，首先访问左节点（或子树），然后是根节点，最后是右节点（或子树）。
• 而在后序树遍历中，首先访问左节点（或子树），然后是右节点（或子树），最后访问树的根节点。

中序树遍历

中序遍历可以定义为通过递归处理左子树，然后处理根，最后处理右子树来处理所有树节点的遍历。

例如，让我们为下面给定的树编写一个中序遍历。

上面的树有七个节点。节点 A 是树的根节点，其左右子树分别有三个节点。

• 根据中序树遍历的定义，应该首先访问左子树，在左子树中，最深的左节点是节点 D。
• 然后访问这个子树的根节点 B（左子树的根节点）。
• 最后，访问二叉树最右边的节点 E，因此现在我们的左子树已完全遍历，我们将访问根节点 A，最后遍历右子树。
• 同样，在右子树中，我们首先需要遍历最左边的节点 F，然后访问右子树的根节点 C。最后，访问右子树最右边的节点 G。
• 因此，上述树的中序树遍历是：

栈数据结构主要用于树的中序遍历，但在本文中，我们将看到递归遍历树的方法。

C++ 代码

让我们编写一个 C++ 代码，使用递归对树进行中序遍历。

输出：上述代码的输出是

The inorder traversal of the tree with recursion is:
40 20 10 70 50 80 30 60 

在上面的 C++ 代码中，我们使用了递归而不是栈数据结构来遍历树。为了遍历树，创建了一个名为 'inorder' 的递归函数，它将被递归调用以遍历树。这个递归函数将为整个树的每个子树调用。

在每个子树中，此函数将首先打印树的最左侧叶子子节点。打印最左侧叶子子节点后，它将打印树的根节点，然后最后打印最右侧叶子子节点，并再次为另一个子树调用。因此，通过递归调用 inorder() 函数，所有树节点都成功遍历。

Java 代码

现在让我们用 Java 编写一个代码来创建一棵树并以中序树遍历的方式打印树的元素。

输出：上述代码的输出是

The inorder traversal of the tree with recursion is:
40 20 10 70 50 80 30 60 

在上面的 Java 代码中，我们使用了递归而不是栈数据结构来遍历树。为了遍历树，创建了一个名为 'inorder' 的递归函数，它将被递归调用以遍历树。这个递归函数将为整个树的每个子树调用。

在每个子树中，根据中序树遍历的定义，此函数将首先打印树的最左侧叶子子节点。打印最左侧叶子子节点后，它将打印树的根节点，然后最后打印最右侧叶子子节点，并再次为另一个子树调用。因此，通过递归调用 inorder() 函数，所有树节点都成功遍历。