数据结构 第5章 树的二叉树 单元小结（3）树和森林
一.树的存储结构：
1.双亲表示法： 2.双亲孩子表示法
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
3、孩子兄弟表示法
二.森林与二叉树的转换
1、森林转换为二叉树
步骤如下：(1)把每个树转换为二叉树; (2)第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。 简单地说，就是 左是孩子，右是兄弟。
2、二叉树转换为森林
判断一棵二叉树能够转换成一棵树还是森林，标准很简单，那就是只要看这棵二叉树的根结点有没有右孩子，有就是森林，没有就是一棵树。 转换成森林，步骤如下：(1)从根结点开始，若右孩子存在，则把与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除……，直到所有右孩子连线都删除为止，得到分离的二叉树。(2) 再将每棵分离后的二叉树转换为树即可。
重点！！！！！！！
三.树和森林的遍历（每年都考概念）
1、树的遍历
（1）先根遍历方式。即先访问树的根结点，然后依次先根遍历根的每棵子树。
（2）后根遍历方式，即先依次后根遍历每棵子树，然后再访问根结点。
2、森林的遍历
（1）前序遍历：先访问森林中第一棵树的根结点，然后再依次先根遍历根的每棵子树，再依次用同样方式遍历除去第一棵树的剩余树构成的森林。
（2）后序遍历：后根遍历第一棵树的每棵子树，然后再访问第一棵树根结点，再依次同样方式遍历除去第一棵树的剩余树构成的森林。
更多精彩
