数据结构和算法树遍历


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

  • 有序遍历
  • 预订遍历
  • 下订单遍历

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

有序遍历

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

如果按 顺序 遍历二叉树,则输出将按升序生成排序的键值。

在订单遍历中

我们从开始 一个 ,并按照中序遍历,我们移动到其左子树 B 也按顺序遍历。该过程一直持续到访问所有节点。这棵树的inorder遍历的输出将是 -

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

算法

Until all nodes are traversed 
**Step 1**  Recursively traverse left subtree.
**Step 2**  Visit root node.
**Step 3**  Recursively traverse right subtree.

预订遍历

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

预订遍历

我们从开始 一个 ,并按照前序遍历,我们首先访问 一个 本身,然后移动到它的左子树 B 也是预先遍历的。该过程一直持续到访问所有节点。此树的预订遍历的输出将是

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

算法

Until all nodes are traversed 
**Step 1**  Visit root node.
**Step 2**  Recursively traverse left subtree.
**Step 3**  Recursively traverse right subtree.

下订单遍历

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

邮政订单遍历

我们从开始 一个 ,并按照后序遍历,我们首先参观的左子树 B 也在下单后遍历。该过程一直持续到访问所有节点。此树的后序遍历输出将为 -

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

算法

Until all nodes are traversed 
**Step 1**  Recursively traverse left subtree.
**Step 2**  Recursively traverse right subtree.
**Step 3**  Visit root node.