数据结构——树和森林的遍历方法

1、树的遍历的定义 ：以某种方式访问树中的每一个结点，且仅访问一次。 树的遍历主要有先根遍历和后根遍历。

2、(1)先根遍历： 若树非空，则先访问根结点，再按照从左到右的顺序遍历根结点的每一棵子树。这个访问顺序与这棵树对应的二叉树的先序遍历顺序相同。

(2)后根遍历： 若树非空，则按照从左到右的顺序遍历根结点的每一棵子树，之后再访问根结点。其访问顺序与这棵树对应的二叉树的中序遍历顺序相同。

Example one：

根据以上这幅图有如下结果：

注意到我们并没有定义一般树的中根遍历，因为子结点该怎么分两部分并没有定义，所以只定义先、后根。

Example two:

1、前序遍历

前序遍历的定义为：

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

（2）前序遍历第一棵树的根结点的子树；

（3）前序遍历去掉第一棵树后的子森林。

2、中序遍历

中序遍历的定义为：

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

（2）访问森林中第一棵树的根结点；

（3）中序遍历去掉第一棵树后的子森林。

森林与二叉树的转换

树转化为二叉树：

⑴ 加虚线（或者粗实线）。在树的每层按从“左至右”的顺序在兄弟结点之间加虚线相连。

⑵ 去连线。除最左的第一个子结点（长子节点）外，父结点与所有其它子结点的连线都去掉。

森林转换成二叉树：

当一般的树转换成二叉树后，二叉树的右子树必为空。若把森林中的第二棵树(转换成二叉树后)的根结点作为第一棵树(二叉树)的根结点的兄弟结点，则可导出森林转换成二叉树的转换步骤如下：

（1）、把每棵树转换为二叉树

（2）、按给出的森林中树的次序，第一棵树不动，从第二棵树开始，依次把后一棵树的根结点作为前一棵二叉树的根结点的右孩子，用线连起来，当所有的二叉树连接起来后，就得到了由森林转换来的二叉树。

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

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

这两个步骤是说"先遍历第一棵树,而第一棵树,是要先遍历它的子森林,再访问根节点"

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

这个步骤,是说继续遍历同级的其他树

结合起来理解,就是依次遍历同级的几棵树,然后访问根节点

(对于森林,你可以想象有一个虚拟的根节点在上面,这样其实就是一棵树了,先遍历这个虚拟树的几棵子树,再访问那个虚拟的根节点)

按这个理解,对于第一棵树,先访问B,C,D,再访问根A

然后访问第二棵树,先访问树F,树H,再根E

然后第三棵树,先访问树I,再访问根G,而对数I,要先访问它的子树J,所以顺序是J,I,G

按这个逻辑,我理解J是跟在I下面的,是么?从你的图上看不清楚

补充一下,说穿了就是"依次对每一棵树进行后根遍历"

递归算法

指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则将左子作为新的结点参数进行判断，打印左子。左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。

非递归算法

首先建立两个栈，然后定义两个常量。第一个为status，取值为0，1，2.0代表左右子都没有去过，1代表去过左子，2，代表左右子都去过，默认为0。第二个常量为flag，取值为0或者1，0代表进左栈，1代表进右栈。初始时指针指向根结点，判断根结点是否有左子，有左子则，将根结点入左栈，status置0，flag置0，若没有左子则判断结点有没有右子，有右子就把结点入右栈，status置0，flag置1，若左右子都没有，则打印该结点，并将指针指向空，此时判断flag，若flag为0，则从左栈出栈一个元素作为当前结点，重新判断；若flag为1则从右栈出栈一个元素作为当前结点，重新判断左右子是否去过，若status为1，则判断该结点有没有右子，若有右子，则将该结点入右栈，status置1，flag置1，若没有右子，则打印当前结点，并将指针置空，然后再次判断flag。若当前结点status为2，且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情况，按上述方法处理，直至遍历结束。

---