大话数据结构-树( 十 ) _前序遍历

然后把第三棵二叉树作为第二棵二叉树根结点的右孩子：
依次处理，得到最终结果：
7.7.3 二叉树转换为树
按如下步骤操作：
(1) 加线，若某个结点的左孩子结点存在，则将这个结点与这个结点的左孩子的的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点…全部用线连起来；
(2) 删除原二叉树中所有结点与其右孩子结点的连线；
(3) 调整层次；
假设有以下二叉树：
从根结点开始，先看G ，发现其有左孩子L ，因此把G与L的右孩子M、M的右孩子N、N的右孩子O连在一起：
再来看L ，其有左孩子R ，因此把L与R的右孩子S、S的右孩子T边在一起：
再看R ，没有左孩子，跳过， M、S、N、T、O都没有左孩子，全部跳过。
删除所有结点与其右孩子结点的连线：
拉直，得到一棵二叉树：
7.7.4 二叉树转换为森林
按如下步骤操作：
(1) 查看二叉树的根结点，若有右孩子存在，则把与右孩子结点的连线删除，得到两棵分离的二叉树；再看第二棵二叉树的根结点，若有右孩子，则把右孩子连线删除，得到三棵二叉树；再看第三棵二叉树的根结点，若有右孩子，则把右孩子连线删除，得到四棵二叉树…依此类推，得到多棵分离的二叉树；
(2) 将每棵分离后的二叉树转换为树；
例如有以下二叉树：
先看根结点A ，其有右孩子，因此把与右孩子的连线删除，得到两棵二叉树：
再看第二棵二叉树的根结点E ，其有右孩子，因此把与右孩子的连线删除，得到三棵二叉树：
依此类推，得到最终分离的二叉树：
接着，按照7.7.3的方法，把所有二叉树转换为树，得到一片森林：
7.7.5 树的遍历
树的遍历有两种方式，一种是先根遍历，一种是后根遍历，实际上与二叉树的前序遍历（根->左->右，若只有一个孩子时默认为左孩子）和后序遍历（左->右->根，若只有一个孩子时默认为左孩子）类似。
如以下树：
先根遍历（前序遍历）结果为，后根遍历（后序遍历）结果为。
我们把这棵树转化为二叉树，如下：
对它进行前序遍历，结果为，与树的先根遍历结果相同；对它进行中序遍历，结果为，与树的后根遍历结果相同。
因此结论是：
(1) 树的先根遍历，即对树做前序遍历，只有一个孩子的结点默认该孩子为左孩子；
(2) 树的后根遍历，即对树做后序遍历，只有一个孩子的结点默认该孩子为左孩子；
(3) 树的先根遍历，与其转化为二叉树后的前序遍历结果相同；树的后根遍历，与其转化为二叉树后的中序遍历结果相同；
7.7.6 森林的遍历
森林的遍历也分为两种方式：
(1) 前序遍历，从第一棵树开始，使用先根遍历，再串起来，实际上与二叉树的前序遍历相同（根->左->右，若只有一个孩子时默认为左孩子）；
(2) 后序遍历，从第一棵树开始，使用后根遍历，再串起来；
如以下森林：