¶ 树
定义：
- 由 n(n≥0)个结点组成的有限集合
- 当n≥1时，有且仅有一个特定的称为根的节点
- 除根以外的其它结点划分为m(m≥0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。
- 每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继
¶ 几种表示方法
好像没什么用
¶ 基本概念
• 节点的度：节点子树的个数
• 树的度：最大的节点度数
• 叶子节点：度为 0 的节点
• 分支节点：度不为 0 的节点
• 节点的层次：根为第 1 层，依次加 1
• 树的高度（深度）：最大层次数
- 孩子结点——某节点子树的根
- 双亲结点——相对于某节点子树的根
- 祖先节点——从根节点到该节点所经分支上的所有节点
- 子孙节点——某一节点子树中的所有节点
- 兄弟结点——同一双亲节点孩子节点互为兄弟节点
¶ 二叉树
二叉树是n(n≥0)个结点的有限集。它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成
- 二叉树每个节点最多有两个子树
- 二叉树子树有左右之分，即使只有一个子树也要区分左右
- 因此，二叉树是不同于树的东西，二叉树不是树的特例
- 五种基本形态：
- 对非空二叉树,如果其叶结点个数为 n0,度为2的非叶结点个数为n2, 则有
- 具有n个节点的二叉树的高度为$$\lfloor\log_2n\rfloor+1\text{ 或 }\lceil\log_2(n+1)\rceil$$
¶ 特殊形态的二叉树
¶ 满二叉树
- 每一层的节点数都达到最大值
- 高度为 h 的满二叉树有个节点
- 所有叶子节点都在最后一层
¶ 完全二叉树
- 除最后一层外，每层节点数都达到最大
- 最后一层的节点从左到右连续排列
- 可以看作从满二叉树的最下层从右向左删除若干叶子节点
- 满二叉树是完全二叉树，完全二叉树不一定是满二叉树
¶ 二叉树的存储
¶ 顺序存储
编号：
进行顺序存储：
这种编号具有以下性质：
- 当i=1时，该结点为二叉树的根;若i>1，则该结点的双亲的序号为
- 若2i≤n，则该结点的左孩子的序号为2i，否则该结点无左孩子
- 若2i+1≤n，则该结点的右孩子的序号为2i+1，否则该结点无右孩子
¶ 链式存储
- n 个结点的二叉树中，共有 n+1 个空链接域
¶ 二叉树的遍历
需求：访问节点本身、左子树、右子树
- 前序遍历
- 中序遍历
- 后序遍历
便捷方法：
参考
中序遍历的代码：
void InOrder(BinTree T){
if(T){
InOrder(T->lchild);
printf("%c", T->data);
InOrder(T->rchild);
}
}
是否能从遍历结果逆推二叉树形态？
- 先序+中序->可以
- 后序+中序->可以
- 先序+后序->不可以
¶ 森林
森林是树的集合
¶ 森林转二叉树
孩子->左，兄弟->右
- 将每棵树转换为二叉树（第一个孩子作为左子树，兄弟作为右子树）
- 将各树的根节点视为兄弟，连接起来
- 第一棵树的根作为整个二叉树的根
¶ 二叉树转森林
左->孩子，右->兄弟
¶ 霍夫曼树、霍夫曼编码
-
扩充二叉树
- 指除叶子结点外，其余结点都必须有两个孩子的二叉树（任何节点，不能有1度，要么0度，要么2度）
-
内路径长度
- 从根到所有非叶节点的路径长度之和
-
外路径长度
- 从根到所有叶子节点的路径长度之和
-
加权路径长度
- 各叶结点所带的权值与该叶结点到根的路径长度的乘积之和
-
- 二叉树的带权路径长度WPL最小的称为最优二叉树, 也称为霍夫曼树
¶ 霍夫曼算法
由n个只有根节点的树的集合（森林）构成霍夫曼树的过程
步骤：
- 将 n 个权值构成 n 棵只有根的树的森林
- 选取权值最小的两棵树合并，新树根的权值为两子树权值之和
- 删除原来两棵树，将新树加入森林
- 重复步骤 2-3，直到森林中只剩一棵树
¶ 霍夫曼编码
短码不是长码的前缀的编码称为“前缀码”
霍夫曼编码的特点
- 电文的总长度最短
- 是前缀码（译码唯一性，译码无歧义）
编码方式：
霍夫曼树中，左子树给一个0,右子树给一个1,总根节点到任一个节点总的编码就是霍夫曼编码
¶ 作业
¶ 1
画出该树等效的二叉树，并写出其先序、中序和后续遍历结果。
| 先序 | A | B | E | K | L | F | C | G | M | H | D | I | J |
| 中序 | K | L | E | F | B | M | G | H | C | I | J | D | A |
| 后序 | L | K | F | E | M | H | G | J | I | D | C | B | A |
¶ 2
一棵二叉树的中序、后序序列如下，请画出该二叉树。
中序：DCBGEAHFIJK后序：DCEGBFHKJIA
¶ 3
给定25个字符组成的电文为DDDDAAABEEAAFCDAABCCCBADD，请基于Huffman树为字符A、B、C、D、E、F设计Huffman编码。
各个字符出现的次数为：
A：8次，B：3次，C：4次，D：7次，E：2次，F：1次
设计对应的Huffman树：
对应的编码为：
A：11
B：001
C：01
D：10
E：0000
F：0001