树遍历（Tree Traversal）

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

• 有序遍历
• Pre-order Traversal
• Post-order Traversal

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

In-order Traversal

在此遍历方法中，首先访问左子树，然后访问根，然后访问右子树。 我们应该永远记住，每个节点都可以代表一个子树。

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

我们从A开始，在按顺序遍历之后，我们移动到它的左子树B B也按顺序遍历。 该过程一直持续到访问所有节点。 这棵树的inorder遍历的输出将是 -

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

算法 (Algorithm)

Until all nodes are traversed −
<b>Step 1</b> − Recursively traverse left subtree.
<b>Step 2</b> − Visit root node.
<b>Step 3</b> − Recursively traverse right subtree.

Pre-order Traversal

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

我们从A开始，并且在预订遍历之后，我们首先访问A本身然后移动到其左边的子树B B也是预先遍历的。 该过程一直持续到访问所有节点。 此树的预订遍历的输出将是 -

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

算法 (Algorithm)

Until all nodes are traversed −
<b>Step 1</b> − Visit root node.
<b>Step 2</b> − Recursively traverse left subtree.
<b>Step 3</b> − Recursively traverse right subtree.

Post-order Traversal

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

我们从A开始， A跟踪后遍历之后，我们首先访问左子树B B也在下单后遍历。 该过程一直持续到访问所有节点。 此树的后序遍历输出将为 -

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

算法 (Algorithm)

Until all nodes are traversed −
<b>Step 1</b> − Recursively traverse left subtree.
<b>Step 2</b> − Recursively traverse right subtree.
<b>Step 3</b> − Visit root node.

要检查树遍历的C实现，请单击此处 。