上一篇：考研数据结构笔记——第四章树与二叉树（上）

8️⃣.数的存储结构（善用特殊法）

（1）表示方法

① 双亲表示法：增加一个伪指针，指向双亲结点在的数组中的位置

② 孩子表示法：每个结点的孩子用单链表链接起来

③ 孩子兄弟表示法：第一个孩子和右兄弟

（2）树

（3）森林

（森林也可以只有一棵树）

（4）树的遍历对应森林以及二叉树的遍历（注意表述）

树	森林	对应二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

9️⃣.树与二叉树的应用

（1）二叉排序树（BST）

① 左子树 < 根结点 < 右子树 （有时候会反向定义，看树的特征）

② 查找，插入（插入一定是叶子结点）

③ 删除

case1：叶子结点就直接删除

case2：若删除结点只有一颗子树，直接用子树代替

case3：若删除结点Z有左右子树，另Z的后继r（或者前驱）赋值给Z，并删掉r（递归删除，这个问题就变成删除r了，直到删除到case1，2的情况）

④ 平均查找长度取决于树的高度H：插入和删除都为

（2）平衡二叉树（ALV）

① 左右子树高度差绝对值不超过1，即0，-1，1 （平衡因子）

② 插入：前一步和BST插入一样，后不平衡后，调整最小平衡子树

③ 调整：（把子树移动到被旋转下来根的下面）

④

所以平衡二叉树查找最多次数或最大高度为

(3) 哈夫曼树和哈夫曼编码（不唯一，但代权路径长度相同且最优）

① 所有叶子结点的代权路径长度之和

② 构造：每次选两根最小权值的树作为左右子树形成一颗新的树，直到只剩下一颗树

③ 哈夫曼编码：按字符频度构造哈夫曼树 左0右1 ，每个字符用路径上的数字编码

（原理：没有一个编码是另一个编码的前缀）

④ 对于严格的m叉树，若结点数不够，要补权值为0的结点

（哈夫曼m叉树只有度为0和m的结点）

（我才发现我这篇文章在草稿箱中一直没发出去 脸黑.jpg）