目录

DSA - 树遍历(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 class="notranslate">Step 1</b> − Recursively traverse left subtree.
<b class="notranslate">Step 2</b> − Visit root node.
<b class="notranslate">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 class="notranslate">Step 1</b> − Visit root node.
<b class="notranslate">Step 2</b> − Recursively traverse left subtree.
<b class="notranslate">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 class="notranslate">Step 1</b> − Recursively traverse left subtree.
<b class="notranslate">Step 2</b> − Recursively traverse right subtree.
<b class="notranslate">Step 3</b> − Visit root node.

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

↑回到顶部↑
WIKI教程 @2018