Data Structures Algorithms 简明教程

Tree Traversal

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

Traversal is a process to visit all the nodes of a tree and may print their values too. Because, all nodes are connected via edges (links) we always start from the root (head) node. That is, we cannot randomly access a node in a tree. There are three ways which we use to traverse a tree −

  1. In-order Traversal

  2. Pre-order Traversal

  3. Post-order Traversal

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

Generally, we traverse a tree to search or locate a given item or key in the tree or to print all the values it contains.

In-order Traversal

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

In this traversal method, the left subtree is visited first, then the root and later the right sub-tree. We should always remember that every node may represent a subtree itself.

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

If a binary tree is traversed in-order, the output will produce sorted key values in an ascending order.

In order Traversal

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

We start from A, and following in-order traversal, we move to its left subtree B.B is also traversed in-order. The process goes on until all the nodes are visited. The output of in-order traversal of this tree will be −

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

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

Algorithm

到所有节点都已遍历−

Until all nodes are traversed −

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

Example

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

Following are the implementations of this operation in various programming languages −

Pre-order Traversal

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

In this traversal method, the root node is visited first, then the left subtree and finally the right subtree.

Pre order Traversal

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

We start from A, and following pre-order traversal, we first visit A itself and then move to its left subtree B. B is also traversed pre-order. The process goes on until all the nodes are visited. The output of pre-order traversal of this tree will be −

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

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

Algorithm

到所有节点都已遍历−

Until all nodes are traversed −

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

Example

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

Following are the implementations of this operation in various programming languages −

Post-order Traversal

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

In this traversal method, the root node is visited last, hence the name. First we traverse the left subtree, then the right subtree and finally the root node.

Post order Traversal

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

We start from A, and following pre-order traversal, we first visit the left subtree B. B is also traversed post-order. The process goes on until all the nodes are visited. The output of post-order traversal of this tree will be −

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

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

Algorithm

到所有节点都已遍历−

Until all nodes are traversed −

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

Example

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

Following are the implementations of this operation in various programming languages −

Complete Implementation

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

Now let’s see the complete implementation of tree traversal in various programming languages −