树和森林的遍历

树和森林的遍历

一、树的遍历

数的结构是一个根加上森林，而森林又是树的集合，由此我们可以引出树的两种遍历方式（这两种遍历方式本身也是一种递归定义）。

1、先根（先序）遍历：即先访问树的根结点，然后依次先根遍历根的每棵子树

2、后根（后序）遍历：即先依次后根遍历根的每棵子树，然后访问根结点

3、另外还有一种层序遍历，这种遍历就是自上向下，自左向右按层次进行遍历即可

根据上面的两种遍历定义可得上图树的遍历结果如下：

先根遍历：ABEFCDGHIJK

后根遍历：EFBCIJKHGDA

层次遍历：ABCDEFGHIJK

二、森林的遍历

森林由三部分构成：森林中第一个树的根结点+森林中第一颗树的根结点的子树森林+森林中除去第一棵树而由其它树构成的森林。按照森林和树相互递归的定义，我们可以推出森林的两种遍历方（这两种遍历方法也是递归定义）。

1、先序遍历森林，访问规则如下：

第一、先访问森林中第一棵树的根结点

第二、然后，先序遍历第一棵树中根结点的子树森林（相当于二叉树的左子树）

第三、然后，先序遍历除去第一棵树之后剩余的树构成的森林（相当于二叉树的右子树）

2、中序遍历森林

第一、中序遍历第一棵树中根结点的子树森林（相当于二叉树的左子树）

第二、然后，访问森林中第一棵树的根结点

第三、然后，中序序遍历除去第一棵树之后剩余的树构成的森林（相当于二叉树的右子树）

将上面的树的根结点去掉得到的森林，按照森林的两种遍历方法得到的结果如下：

先序遍历：BEFCDGHIJK

中序遍历：EFBCIJKHGD

三、总结

对照上面树和图的遍历我们可以得到树、森林、二叉树遍历的对应关系