目录
一、树（⭐⭐）
二、二叉树（⭐⭐⭐）
三、线索二叉树（⭐⭐⭐）
四、树与森林（⭐⭐）
五、哈夫曼树与并查集（⭐⭐⭐）
一、树（⭐⭐）
选择题：数形结合（特殊图法，能满足所有的必须也要满足特殊图）
1、结点与树的高度、深度、层次。
2、结点和树的度：
1、树的性质：
二、二叉树（⭐⭐⭐）
1、二叉树的性质：
2、完全二叉树：
- 最多只有一个度为1的结点，且只有左孩子（除去最后一层其余都满）
- 若i<=n/2，则为分支结点，若大于则为叶子节点。
- 例：若第六层有叶子节点，第七层可能也有。
- 完全二叉树一定是平衡二叉树。
- 完全二叉树高度为lg(n+1)（上取整）或lgn+1（下取整）
3、满二叉树：
- 每层都是满结点。
4、二叉排序树：
- 左<根<右（同层递增）
5、平衡二叉树：
- 任意结点左右子树高度绝对值之差不超过1。
1、二叉树的链式存储结构：
- 二叉链表n个结点：n+1个空链域，2n个指针域，n个数据域。
- 二叉树用三叉链表(左、右、双亲)：空指针n+2，画图更直观。
- 三叉树用三叉链表：简单，画图去吧，更直观。
- 删除二叉链表所有结点并释放存储空间，后序最合适。（先删除左右孩子，再释放空间最后删除根结点）
2、二叉树的遍历：
- 后序遍历仍需要栈支持（右子树紧挨根结点的点，无法指向根节点）
- 先序遍历即给出入栈顺序，根据卡特兰数：1÷(n+1)×（2n与n的组合数）
三、线索二叉树（⭐⭐⭐）
1、线索二叉树：
四、树与森林（⭐⭐）
1、树与森林的对应关系：
五、哈夫曼树与并查集（⭐⭐⭐）
1、哈夫曼树：
- 固定长度编码：所有字符均在叶子结点。
- 可变长度编码（哈夫曼编码）：根据频次进行映射，起到压缩编码的作用。
- 哈夫曼树：左0右1，贪心策略，只有度为2和0的结点没有度为1的结点，总结点为2n-1，新建的结点为n-1。
2、并查集：
