树、森林与其对应的二叉树的遍历方法的对应关系

╰+攻爆jí腚メ 2022-05-25 00:47 71阅读 0赞

给定一棵树，可以找到唯一一棵二叉树与之对应，同样，森林也与一棵树存在一一对应关系。树与二叉树，森林与二叉树的转化如下图所示，（a）（b）（c）为三棵树，并构成一个森林，（d）（e）（f）分别为（a）（b）（c）对应的二叉树，（g）为森林对应的二叉树。这里不再详细介绍转化方法。

![20180504194618689][]

下面首先说一说树的遍历方法，及与其对应二叉树的遍历方法的关系。

树结构有两种次序遍历树的方法：

1. 先根遍历：先访问树的根节点，再依次先根遍历子树；

2.后根遍历：先依次后根遍历子树，再访问树的根节点。

不曾看到过树的‘中根遍历’的概念，因为树并不一定是二叉树，‘中’的概念不好定义，比如对于一个拥有3个子树的根节点来说，根节点除了先根和后根两种遍历方式之外还有另外两种次序，如一种次序是先遍历根节点的第一棵子树，再访问根节点，之后再依次遍历剩余子树，另一种次序是，先遍历根节点的前两棵子树，再访问根节点，最后访问第三棵子树。对于拥有更多子树的根节点来说，依次遍历的方法更多。

**树的先根遍历和后根遍历可分别借用对应二叉树的先序遍历和中序遍历实现。**以上图（a）中的树和其对应的（d）中的二叉树为例：

对树进行先根遍历：A B C D

对树进行后根遍历：B C D A

对二叉树进行先序遍历：A B C D（与树的先根遍历一致）

对二叉树进行中序遍历： B C D A （同树的后根遍历）

接下来说一说森林的遍历方法，及与其对应的二叉树的遍历方法的关系。

森林的两种遍历方法：

1.先序遍历森林：

（1）访问森林中第一棵树的根节点；

（2）先序遍历第一棵树中根节点的子树森林；

（3）先序遍历除去第一棵树之后剩余的树构成的森林。

2.中序遍历森林

（1）中序遍历森林中第一棵树的根节点的子树森林；

（2）访问第一棵树的根节点；

（3）中序遍历除去第一棵树之后剩余的树构成的森林。

在森林的中序遍历方法中需要**注意**，森林的中序遍历与二叉树的中序遍历方法的定义不同，二叉树的中序遍历是按照LDR的顺序进行遍历，而森林的中序遍历是要先中序遍历第一棵树的所有子树，再访问这棵树的根节点，对于这棵树来说，根节点的访问次序其实是整棵树遍历的最后（类似于二叉树的后序），这里经常与二叉树的中序遍历混淆，傻傻分不清楚~

下面，看看森林遍历方法和其对应的二叉树遍历方法的对应关系。当森林转换成二叉树时，其第一棵树的子树森林转换成左子树，剩余树的森林转换成右子树，则**森林的先序和中序遍历即对应二叉树的先序和中序遍历**。以上图中（a）（b）（c）构成的森林和对应的二叉树（g）为例：

对森林进行先序遍历：A B C D E F G H I J

对森林进行中序遍历：B C D A F E H J I G

对二叉树进行先序遍历： A B C D E F G H I J （与森林先序遍历一致）

对二叉树进行中序遍历：B C D A F E H J I G(同森林中序遍历)

[20180504194618689]: /images/20220525/98cbc7f9211a404a8ec0db2f218639d9.png