数据结构--树4.2.4（树、森林即二叉树的相互转换（仅供参考））

目录

一、树转换成二叉树步骤

二、森林转换成二叉树

 三、二叉树到树、森林的转换

---

一、树转换成二叉树步骤

分两个步骤：

        1、在树中所有的兄弟结点之间加一连线。

        2、对每个结点，除了保留与其长子（最左边）的连线外，去掉该结点与其他孩子的连线。

二、森林转换成二叉树

        1、先将森林中的每棵树变为二叉树

        2、将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树

 三、二叉树到树、森林的转换

1、若结点x是其双亲y的左孩子，则把x的右孩子，右孩子的右孩子，……，都与y用连接线连起来。

        二叉树转换为普通树是刚才的逆过程，步骤也就是反过来做。

        判断一棵二叉树能够转换成一棵树还是森林，标准很简单，那就是只要看这颗二叉树的根结点有没有右孩子，有的话就是森林，没有的话就是一棵树。

        森林的遍历也分为前序遍历和后序遍历，其实就是按照树的先根遍历和后根遍历依次访问森林的每一棵树。

        树、森林的前序遍历和二叉树的前序遍历结果相同。

        树、森林的后序遍历和二叉树的中序遍历结果相同。