一. 树的概念与定义
相关术语：结点 结点的度 叶结点 分支结点 孩子结点 双亲结点 兄弟结点 祖先结点 子孙结点 树的度 树的高度（深度）有序树 森林
二. 二叉树
1.定义：
每个结点的度都不大于2 每个结点的孩子结点次序不能颠倒
满二叉树：深度为k且结点数为 2的k次方减一 的二叉树，对比性质二
完全二叉树：深度为k，结点数为n的二叉树。。。。。。具体见课本122页
满二叉树必为完全二叉树，完全二叉树不一定为满二叉树。
2.二叉树的性质：
性质一：二叉树 第i层 至多有 2 的 i-1 次方 个结点
性质二：深度为k的二叉树至多有 2的k次方减一 个结点
性质三：对任意一棵二叉树T，若终端结点数为n0，而其度数为2的结点数为n2，则n0 = n2 + 1
证明很重要，在122页
性质四：具有n个结点的完全二叉树的深度为 [向下取整(log2(n))+1] 123页
性质五：对于具有n个结点的完全二叉树，对于第i个结点
（1）双亲结点：向下取整(i/2)
（2）左孩子：2×i （3）右孩子：2×i+1
3.二叉树的存储结构
1.顺序存储结构：
一维数组存放，顺序为从上到下，从左到右顺序存放 124页
优点是方便查找，缺点是空间浪费。
2.链式存储结构（重点）：125页
性质：若一个二叉树含有n个结点，则二叉链表含有2n个指针域，其中必有n+1个空的链域。
二叉链表形式的二叉树的创建：134页
二叉树的创建采用的是先序创建，本质上和先序遍历是一样的，只不过把遍历的读出改成了赋值而已
二叉树的遍历：先序，中序，后序：127页
一般是考给一个先序和中序序列，或者给一个后序和中序序列，让你还原二叉树 相关习题 6.4 6.8
其中的递归思想会出一道编程题，比如统计叶子结点数目（设置一个计数器，左右结点同时为空则计数器加一），左右子树互换（一道作业题）等等。
3.树，森林和二叉树：141页
树的存储结构：双亲表示法 孩子表示法 孩子兄弟表示法
树转换为二叉树：孩子在左，兄弟在右
森林转换为二叉树：将森林中的每棵树转换为响应二叉树，然后第一个二叉树不动，后边的依次加到前边二叉树根节点的右孩子上
二叉树还原为森林：145页
4.哈夫曼树，哈夫曼编码：147页 必考！！
1.哈夫曼树：
路径和路径长度：147页 结点的权和带权路径长度：147页
树的带权路径长度：必考 所有叶子结点的带权路径长度之和
哈夫曼树又叫最优二叉树，是由n个带权叶子结点构成的所有二叉树中带权路径长度WPL最短的二叉树
哈夫曼算法：每两个权重最小的结点组合成一颗树，以此累加直到所有结点用完
哈夫曼编码：150页 左分支为0，右分支为1（或者左为1，右为0）
5.习题
6.1 6.4 6.5 6.9 6.11 6.23 6.24
