数据结构和算法树遍历

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

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

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

有序遍历

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

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

在订单遍历中

我们从开始 一个 ，并按照中序遍历，我们移动到其左子树 乙 。 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.