构造平衡二叉树例题_考研数据结构笔记——第四章树与二叉树(下)
上一篇:考研数据结构笔记——第四章树与二叉树(上)8️⃣.数的存储结构(善用特殊法)(1)表示方法① 双亲表示法:增加一个伪指针,指向双亲结点在的数组中的位置② 孩子表示法:每个结点的孩子用单链表链接起来③ 孩子兄弟表示法:第一个孩子和右兄弟(2)树二叉树: 左孩子 右兄弟(由于根结点没有兄弟,所以没有右子树)(3)森林二叉树:后一棵树为前一棵树的右子树(森林也可以只有一棵树)(4)树的遍...
上一篇:考研数据结构笔记——第四章树与二叉树(上)
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)
更多推荐
所有评论(0)