树遍历（中序、前序和后序）

在本文中，我们将讨论数据结构中的树遍历。术语“树遍历”意味着遍历或访问树的每个节点。对于线性数据结构（如链表、队列和栈）只有一种遍历方式。然而，遍历树有多种方式，如下所示：

• 前序遍历
• 中序遍历
• 后序遍历

因此，在本文中，我们将讨论上述树遍历技术。现在，让我们开始讨论树遍历的方式。

前序遍历

此技术遵循“根-左-右”策略。这意味着首先访问根节点，然后递归遍历左子树，最后递归遍历右子树。由于根节点在左子树和右子树之前（或前）遍历，因此称为前序遍历。

因此，在前序遍历中，每个节点都在其两个子树之前被访问。

前序遍历的应用包括：

• 它用于创建树的副本。
• 它也可以用于获取表达式树的前缀表达式。

算法

示例

现在，让我们看看前序遍历技术的示例。

现在，开始对上述树应用前序遍历。首先，我们遍历根节点 A；之后，移动到其左子树 B，它也将以前序遍历。

所以，对于左子树 B，首先遍历根节点 B 本身；之后，遍历其左子树 D。由于节点 D 没有子节点，移动到右子树 E。由于节点 E 也没有子节点，根节点 A 的左子树遍历完成。

现在，移动到根节点 A 的右子树 C。因此，对于右子树 C，首先遍历根节点 C 本身；之后，遍历其左子树 F。由于节点 F 没有子节点，移动到右子树 G。由于节点 G 也没有子节点，根节点 A 的右子树遍历完成。

因此，树的所有节点都被遍历。所以，上述树的前序遍历输出是 -

A → B → D → E → C → F → G

要了解更多关于数据结构中前序遍历的信息，您可以点击链接 前序遍历。

后序遍历

此技术遵循“左-右-根”策略。这意味着首先遍历根节点的左子树，然后递归遍历右子树，最后遍历根节点。由于根节点在左子树和右子树之后（或后）遍历，因此称为后序遍历。

因此，在后序遍历中，每个节点都在其两个子树之后被访问。

后序遍历的应用包括：

• 它用于删除树。
• 它也可以用于获取表达式树的后缀表达式。

算法

示例

现在，让我们看看后序遍历技术的示例。

现在，开始对上述树应用后序遍历。首先，我们以后序遍历左子树 B。之后，我们以后序遍历右子树 C。最后，遍历上述树的根节点，即 A。

因此，对于左子树 B，首先遍历其左子树 D。由于节点 D 没有子节点，遍历右子树 E。由于节点 E 也没有子节点，移动到根节点 B。遍历节点 B 后，根节点 A 的左子树遍历完成。

现在，移动到根节点 A 的右子树 C。因此，对于右子树 C，首先遍历其左子树 F。由于节点 F 没有子节点，遍历右子树 G。由于节点 G 也没有子节点，因此，最后遍历右子树的根节点，即 C。根节点 A 的右子树遍历完成。

最后，遍历给定树的根节点，即 A。遍历根节点后，给定树的后序遍历完成。

因此，树的所有节点都被遍历。所以，上述树的后序遍历输出是 -

D → E → B → F → G → C → A

要了解更多关于数据结构中后序遍历的信息，您可以点击链接 后序遍历。

中序遍历

此技术遵循“左-根-右”策略。这意味着首先访问左子树，然后遍历根节点，最后遍历右子树。由于根节点在左子树和右子树之间遍历，因此称为中序遍历。

因此，在中序遍历中，每个节点都在其子树之间被访问。

中序遍历的应用包括：

• 它用于按递增顺序获取 BST 节点。
• 它也可以用于获取表达式树的前缀表达式。

算法

示例

现在，让我们看看中序遍历技术的示例。

现在，开始对上述树应用中序遍历。首先，我们中序遍历左子树 B。之后，我们将遍历根节点 A。最后，中序遍历右子树 C。

所以，对于左子树 B，首先遍历其左子树 D。由于节点 D 没有子节点，遍历它之后，节点 B 将被遍历，最后遍历节点 B 的右子树，即 E。节点 E 也没有子节点；因此，根节点 A 的左子树遍历完成。

之后，遍历给定树的根节点，即 A。

最后，移动到根节点 A 的右子树 C。因此，对于右子树 C；首先遍历其左子树 F。由于节点 F 没有子节点，节点 C 将被遍历，最后遍历节点 C 的右子树，即 G。节点 G 也没有子节点；因此，根节点 A 的右子树遍历完成。

由于树的所有节点都被遍历，给定树的中序遍历完成。上述树的中序遍历输出是 -

D → B → E → A → F → C → G

要了解更多关于数据结构中中序遍历的信息，您可以点击链接 中序遍历。

树遍历技术的复杂性

上述树遍历技术的时间复杂度为 O(n)，其中 'n' 是二叉树的大小。

而上述树遍历技术的空间复杂度为 O(1)，如果我们不考虑函数调用的栈大小。否则，这些技术的空间复杂度为 O(h)，其中 'h' 是树的高度。

树遍历的实现

现在，让我们看看使用不同编程语言实现上述讨论的技术。

程序： 编写一个程序以在 C 语言中实现树遍历技术。

输出

程序： 编写一个程序以在 C# 语言中实现树遍历技术。

输出

程序： 编写一个程序以在 C++ 语言中实现树遍历技术。

输出

程序： 编写一个程序以在 Java 语言中实现树遍历技术。

输出

执行上述代码后，输出将是 -

结论

在本文中，我们讨论了不同类型的树遍历技术：前序遍历、中序遍历和后序遍历。我们已经看到了这些技术及其算法、示例、复杂性以及在 C、C++、C# 和 Java 中的实现。

以上就是本文的全部内容。希望对您有所帮助，并具有启发性。