构造平衡二叉树例题_考研数据结构笔记——第四章树与二叉树(下)
上一篇:考研数据结构笔记——第四章树与二叉树(上)8️⃣.数的存储结构(善用特殊法)(1)表示方法① 双亲表示法:增加一个伪指针,指向双亲结点在的数组中的位置② 孩子表示法:每个结点的孩子用单链表链接起来③ 孩子兄弟表示法:第一个孩子和右兄弟(2)树二叉树: 左孩子 右兄弟(由于根结点没有兄弟,所以没有右子树)(3)森林二叉树:后一棵树为前一棵树的右子树(森林也可以只有一棵树)(4)树的遍...
![4279dee8947cf0d24737629e85190fe8.png](https://i-blog.csdnimg.cn/blog_migrate/3f0ced7e1e028c1c328cb45e047f291f.jpeg)
上一篇:考研数据结构笔记——第四章树与二叉树(上)
8️⃣.数的存储结构(善用特殊法)
(1)表示方法
① 双亲表示法:增加一个伪指针,指向双亲结点在的数组中的位置
② 孩子表示法:每个结点的孩子用单链表链接起来
③ 孩子兄弟表示法:第一个孩子和右兄弟
(2)树
![equation?tex=%5CRightarrow](https://i-blog.csdnimg.cn/blog_migrate/b3f14e4173a5e71af2b3788193853c8b.png)
(3)森林
![equation?tex=%5CRightarrow](https://i-blog.csdnimg.cn/blog_migrate/b3f14e4173a5e71af2b3788193853c8b.png)
(森林也可以只有一棵树)
(4)树的遍历对应森林以及二叉树的遍历(注意表述)
树 | 森林 | 对应二叉树 |
---|---|---|
先根遍历 | 先序遍历 | 先序遍历 |
后根遍历 | 中序遍历 | 中序遍历 |
9️⃣.树与二叉树的应用
(1)二叉排序树(BST)
① 左子树 < 根结点 < 右子树 (有时候会反向定义,看树的特征)
② 查找,插入(插入一定是叶子结点)
③ 删除
case1:叶子结点就直接删除
case2:若删除结点只有一颗子树,直接用子树代替
case3:若删除结点Z有左右子树,另Z的后继r(或者前驱)赋值给Z,并删掉r(递归删除,这个问题就变成删除r了,直到删除到case1,2的情况)
④ 平均查找长度取决于树的高度H:插入和删除都为
![equation?tex=O%28h%29](https://i-blog.csdnimg.cn/blog_migrate/c42ed8f5c55cb311a742911c1ed8dd42.png)
(2)平衡二叉树(ALV)
① 左右子树高度差绝对值不超过1,即0,-1,1 (平衡因子)
② 插入:前一步和BST插入一样,后不平衡后,调整最小平衡子树
③ 调整:(把子树移动到被旋转下来根的下面)
![bd1bdd7d8a352c6f08cde23c8fbf0c13.png](https://i-blog.csdnimg.cn/blog_migrate/278b85cff736a443073926db2ba5c3c0.jpeg)
④
![equation?tex=N_%7Bh%7D](https://i-blog.csdnimg.cn/blog_migrate/99a5c9d48ac84c88404826b42d17f1e1.png)
![equation?tex=N_%7Bh%7D+%3D+N_%7Bh-1%7D+%2BN_%7Bh-2%7D+%2B1](https://i-blog.csdnimg.cn/blog_migrate/99a5c9d48ac84c88404826b42d17f1e1.png+%3D+N_%7Bh-1%7D+%2BN_%7Bh-2%7D+%2B1)
所以平衡二叉树查找最多次数或最大高度为
![equation?tex=log_%7B2%7Dn+%2B+1](https://i-blog.csdnimg.cn/blog_migrate/422bb973538aebf95c000a155a8ca970.png)
(3) 哈夫曼树和哈夫曼编码(不唯一,但代权路径长度相同且最优)
① 所有叶子结点的代权路径长度之和
![equation?tex=WPL%3D%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%7Bw_%7Bi%7D+%5Ctimes+l_%7Bi%7D%7D](https://i-blog.csdnimg.cn/blog_migrate/3aa05642278b3d16ec13968fdf114f9e.png)
② 构造:每次选两根最小权值的树作为左右子树形成一颗新的树,直到只剩下一颗树
③ 哈夫曼编码:按字符频度构造哈夫曼树 左0右1 ,每个字符用路径上的数字编码
(原理:没有一个编码是另一个编码的前缀)
④ 对于严格的m叉树,若结点数不够,要补权值为0的结点
(哈夫曼m叉树只有度为0和m的结点)
(我才发现我这篇文章在草稿箱中一直没发出去 脸黑.jpg)
更多推荐
所有评论(0)