第六章 树（续章）
二叉树的存储结构：
1.顺序存储结构（适用于完全二叉树）
2.二叉链表：一个数据域和两个指针域。
二叉树的遍历：是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。
二叉树遍历方法：
1.前序遍历（根左右）
2.中序遍历（左根右）
3.后序遍历（左右根）
4.层序遍历
扩展二叉树：将二叉树中每个结点的空指针引出一个虚结点，并将其值改为特定值。
线索二叉树：加上线索的二叉链表相应的二叉树。（指向前驱和后继的指针称为线索）
优点：
（1）充分利用空指针域空间（节省空间）
（2）创建时一次遍历终生受用前驱后继的信息（节省时间）
赫夫曼编码——最基本的压缩编码方式：
按照各个自负的出现次数或频率作为相应叶子结点的权值来构造赫夫曼树，并对左分支为0，右分支为1。从根结点到叶子结点所经过得路径分支组成的序列变为该结点对应的编码。
赫夫曼树（最优二叉树）：带权路径长度WPL最小的二叉树。
确定赫夫曼树方法：
（1）带权值叶子从小到大排序
（2）取最小的两个叶结点结合（相对较小的为左孩子）
（3）以结合后的插入有序序列在进行排序
（4）依次重复步骤二、三
tips:
1.树的路径长度：从树根到每一结点的路径长度之和。
2.前缀编码：任一字符的编码都不是另一个字符的编码的前缀。
