Data Structures Algorithms 简明教程

Tree Traversal

遍历是一个访问树的所有节点并可能打印其值的过程。因为，所有节点都通过边（链接）连接，所以我们总是从根（头）节点开始。也就是说，我们无法随机访问树中的节点。有三种方法可以遍历树 -

通常，我们遍历一棵树以搜索或定位树中给定的项目或键，或打印它包含的所有值。

在这种遍历方法中，首先访问左子树，然后访问根，最后访问右子树。我们应该始终记住，每个节点本身都可能表示一个子树。

如果遍历一棵二叉树 in-order ，输出将按升序生成排序的键值。

从 A 开始，按照中序遍历，我们将移动到它的左子树 B 。 B 也以中序遍历。此过程一直持续到所有节点都已访问。这棵树的中序遍历的输出将是−

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

到所有节点都已遍历−

Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

以下是该操作在各种编程语言中的实现 −

在这种遍历方法中，首先访问根节点，然后访问左子树，最后访问右子树。

从 A 开始，并按照先序遍历，我们首先访问 A 本身，然后移动到它的左子树 B 。 B 也以先序遍历。此过程一直持续到所有节点都已访问。这棵树的先序遍历的输出将是−

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

到所有节点都已遍历−

Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.

以下是该操作在各种编程语言中的实现 −

在这种遍历方法中，根节点最后被访问，因此得名。我们首先遍历左子树，然后遍历右子树，最后遍历根节点。

从 A 开始，并按照后序遍历，我们首先访问左子树 B 。 B 也以后序遍历。此过程一直持续到所有节点都已访问。这棵树的后序遍历的输出将是−

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

到所有节点都已遍历−

Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

以下是该操作在各种编程语言中的实现 −

现在，让我们看看各种编程语言中树遍历的完整实现：