树与二叉树
如何将一棵树转化成二叉树？
树的孩子兄弟表示法与二叉树的二叉链表表示法都是用到两个指针
- 将孩子兄弟表示法理解成二叉链表
树转换成二叉树的手动模拟方法：
- ①将同一结点的各个孩子用线串连起来
- ②将每个结点的子树分支，从左往右，除了第一个以外全部删除
如何将一棵二叉树转化成树？
二叉树转换成树的手动模拟方法：
- ①将二叉树从上到下分层，并调节成水平方向。
(分层方法：每遇到左孩子则为一层)
* ②找到每一层的双亲结点，方法为它的上一层相连的那个结点就是双亲结点。例如bcd这一层，与它相连的上一层结点即为a,所以bcd这三个结点的双亲结点都是a.
* ③将每一层结点和其双亲结点相连，同时删除该双亲结点各个孩子结点之间的联系。
森林与二叉树
- 森林：森林是m（m≥0）棵互不相交的树的集合
- 由于二叉树和树都可用二叉链表来作为其存储结构，则以二叉链表为媒介可以导出树与二叉树之间的对应关系。
如何将森林转换成二叉树？
森林转换成树的手动模拟方法：
- ①将森林中每棵树都转换成二叉树
- ②将第二棵树作为第一棵树的根结点的右子树，将第三棵树作为第二棵树的根结点的右子树..依次类推
如何将二叉树转换成森林？
二叉树转换成森林的手动模拟方法：
- 反复断开二叉树根结点的右孩子的右子树指针，直到不存在根结点有右孩子的二叉树为止。
通过递归定义容易写出相互转换的递归算法。
树与森林的遍历
- 先序：先访问根结点，再访问根结点的每棵子树。 访问子树也是按照先序的要求
- 后序：先访问根结点的每棵子树，再访问根结点。 访问子树也是按照先序的要求
- 树的先序遍历等于它对应二叉树的先序遍历，后序遍历等于它对应的二叉树的中序遍历
