5.7 树和森林
5.7.1 树的存储结构
1双亲表示法
2孩子链表
?3 孩子兄弟表示（二叉树表示法，二叉链表表示法）
?表示方法
?总结：左斜的元素为一层的，右边存放的是下一个兄弟结点
5.7.2 树与二叉树的转换
- 由于树和二叉树都可以用二叉链表作存储结构，则以二叉链表作媒介可以导出树与二叉树之间的一个对应关系
1将树转化为二叉树
?方法：
?例题1
?2将二叉树转化为树
?例题2
?5.7.3 森林与二叉树的转化
1森林转化成二叉树
?例题1
?2二叉树转化成森林
?例题2
?5.7.4树与森林的遍历
1树的遍历（三种）
- 先根遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树
- 后根遍历：若树不空，则先依次后根遍历各棵子树，然后访问根结点
- 按层次遍历：若树不空，则自上而下自左至右访问树中每个结点
?2 森林的遍历
将森林看作由三个部分组成的
- ?先序遍历：依次从左至右对森林的每一颗树进行先根遍历
- 中序遍历：依次从左至右对森林的每一颗树进行后根遍历
?例题1
5.8哈夫曼树及其应用
基本概念
- 路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径
- 结点的路径长度：两结点间路径上的分支树
- 树的路径长度：从树根到每一个结点的路径长度之和，记作：TL
?
- 结点数目相同的二叉树中，完全二叉树是路径最短的二叉树
- 权：将树中结点赋给一个有着某种含义的数值，则这个数值为该结点的权
- 结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积
- 树的带权路径长度（WPL）：树中所有叶子结点的带权路径长度之和
哈夫曼树：最优树（带权路径长度（WPL）最短的树）
哈夫曼树：最优二叉树（带权路径长度（WPL）最短的二叉树）
5.8.2 哈夫曼树的构造算法
哈夫曼树中权越大的叶子离根越近
贪心算法：构造哈夫曼树时首先选择权值小的叶子结点
构造哈夫曼树的方法
?例题1
?总结：
1、在哈夫曼算法中，初始有n棵树，要经过n-1次合并最终形成哈夫曼树
2、经过n-1次合并产生n-1个新结点，且这n-1个新结点都是具有两个孩子的分支结点
可见：哈夫曼树中共有2n-1个结点，且其所有的分支结点的度均不为1
5.8.3哈夫曼树算法的实现
?5.8.4哈夫曼编码
定义：设计的前缀码使得电文总长最短。
方法
?例题1
? 总结：哈夫曼数并不唯一
?1、首先根据题目的信息画出哈夫曼树
2、依照左子树为”0“，右子树为”1“，对每个元素进行编码（从根结点出发）
5.8.5 哈夫曼编码的实现过程?
?
5.8.6应用：文件的编码与解码
?
?