数据结构-树与森林

树与二叉树

• 如何将一棵树转化成二叉树？

  • 树的孩子兄弟表示法与二叉树的二叉链表表示法都是用到两个指针

    • 将孩子兄弟表示法理解成二叉链表

  • 树转换成二叉树的手动模拟方法：

    • ①将同一结点的各个孩子用线串连起来
    • ②将每个结点的子树分支，从左往右，除了第一个以外全部删除

• 如何将一棵二叉树转化成树？

  • 二叉树转换成树的手动模拟方法：

    • ①将二叉树从上到下分层，并调节成水平方向。

(分层方法：每遇到左孩子则为一层)

    * ②找到每一层的双亲结点，方法为它的上一层相连的那个结点就是双亲结点。

例如bcd这一层，与它相连的上一层结点即为a,所以bcd这三个结点的双亲结点都是a.

    * ③将每一层结点和其双亲结点相连，同时删除该双亲结点各个孩子结点之间的联系。
   

森林与二叉树

• 森林：森林是m（m≥0）棵互不相交的树的集合
• 由于二叉树和树都可用二叉链表来作为其存储结构，则以二叉链表为媒介可以导出树与二叉树之间的对应关系。

• 如何将森林转换成二叉树？

  • 森林转换成树的手动模拟方法：

    • ①将森林中每棵树都转换成二叉树
    • ②将第二棵树作为第一棵树的根结点的右子树，将第三棵树作为第二棵树的根结点的右子树..依次类推

• 如何将二叉树转换成森林？

  • 二叉树转换成森林的手动模拟方法：

    • 反复断开二叉树根结点的右孩子的右子树指针，直到不存在根结点有右孩子的二叉树为止。

通过递归定义容易写出相互转换的递归算法。

树与森林的遍历

• 先序：先访问根结点，再访问根结点的每棵子树。 访问子树也是按照先序的要求
• 后序：先访问根结点的每棵子树，再访问根结点。 访问子树也是按照先序的要求
• 树的先序遍历等于它对应二叉树的先序遍历，后序遍历等于它对应的二叉树的中序遍历