《算法与数据结构基础》学习笔记05_02——树、森林、哈夫曼树（最优树） 声明 本文章只是本人个人学习笔记，如有错误，欢迎批评指正 以下是本人自学的视频数据结构与算法基础（青岛大学-王卓）_哔哩哔哩_bilibili 概要： 树（Tree）的存储结构比二叉树复杂树和二叉树的转换：树可以通过二叉链表表示法转换为二叉树（兄弟变右孩子）森林：m棵不相交的树哈夫曼树（最优树）————带权路径长度WPL最小的树哈夫曼编码（最优前缀码）————编码总长最短（省空间）、无歧义（解码唯一） 5.5 树的存储结构（不局限于二叉树） 5.5.1 双亲表示法 双亲表示法：结构数组表示数据域——存放结点本身信息；双亲位置域——存放双亲结点在数组中的下标 特点：找双亲容易，找孩子难
5.5.2 孩子链表 孩子链表：（数组的每个素是单链表）数据域——存放结点本身信息；（每个单链表的头指针指向）孩子指针域——指向孩子的下标位置 特点：找孩子容易，找双亲难
5.5.3 带双亲的孩子链表 结合双亲表示和孩子链表这2种方法： 特点：找双亲和孩子都容易
5.5.4 孩子兄弟表示法（二叉链表表示法） 孩子兄弟表示法（二叉链表表示法）数据域第一个指针域：指向第一个孩子结点第二个指针域：指向下一个兄弟结点 （类似于二叉链表，分别指向左右孩子） 特点：找孩子容易，找双亲难。若想快速找到双亲，可以在加个指向双亲结点的指针域
5.6 树与二叉树的转换 树可以用二叉链表表示，将这个二叉链表解释成二叉树的形式；树转成二叉树————兄弟结点变成右孩子结点一棵树与一棵二叉树唯一对应
1.树转二叉树步骤：加线————兄弟间郏县减线————减去非长子线顺转45°————兄弟变右孩子
2.二叉树转树步骤：加线————右孩子 跟 左孩子的双亲连线，（右孩子变兄弟）减线————减去原来右孩子连线逆转45°
5.7 森林与二叉树的转化 森林：m棵不相交的树 一个森林与一个二叉树唯一对应 1.森林转二叉树的步骤：树转二叉树————将不相交的树分别转为二叉树根相连————将这些二叉树的根相连顺转45°
2.二叉树转森林的步骤：二叉树分离————去掉根结点的右孩、右孩的右孩……的连线将孤立的二叉树转成树
5.8 树与森林的遍历 5.8.1 树的三种遍历方式 先根（序）遍历————先访问根结点，然后依次先根遍历各棵子树后根（序）遍历————先依次后根遍历各棵子树，然后访问根结点层次遍历————从上到下，从左到右访问结点
5.8.2 森林的遍历 先根（序）遍历————依次从左至右对森林中的每棵树进行树的先根遍历中根（序）遍历————依次从左至右对森林中的每棵树进行树的后根遍历
5.9 哈夫曼树（最优树） 5.9.1 一些概念：树的带权路径长度WPL 路径————两个结点之间的分支路径长度————两个结点之间的分支数
树的路径长度TL————从根结点到每个结点的路径长度之和（完全二叉树是路径长度最短的二叉树，但是存在和完全二叉树路径同样短的二叉树）
权（weight）————结点被赋予的某一数值，该数值表示结点在整个树中占的重要性。（举个例子，结点表示各个成绩等级：ABCDE五等，权表示该等级下学生的比例）结点的带权路径长度————从根结点到该结点之间的路径长度与该结点的权的乘积树的带权路径长度WPL（Weighted Path Length）————所有叶子结点的带权路径长度之和；
—————— 权值， 结点到根的路径长度
5.9.2 哈夫曼树的基本概念 1.哈夫曼树（最优树）————带权路径长度WPL最小的树 2.哈夫曼树的特点：满二叉树不一定是哈夫曼树（因为存在权）哈夫曼树种权值越大的叶子离根越近！哈夫曼树并不唯一哈夫曼树的结点的度为0或2，没有度为1的结点n个叶子结点的哈夫曼树共有2n-1个结点
5.9.3 构造哈夫曼树 哈夫曼算法：（此处的哈夫曼树限制为二叉树）构造森林全是根————将n个给定权值的结点构造成n棵二叉树（每个二叉树只有其一个结点），组成森林F选用两小造新树（贪心算法）————挑选F中根结点权值最小的二叉树，成为左右子树，新二叉树的根结点权值为两者权值之和，将新二叉树加入到森林F中在森林F中删去刚才的2棵树重复2、3步骤，直到森林F中只有一棵树（共要进行n-1次合并）
5.9.4 哈夫曼树构造算法的实现 采用顺序存储结构——一维结构数组 
5.9.5 哈夫曼树的应用——哈夫曼编码 1.几种不合理的编码等长编码：浪费空间
简单的不等长编码：有歧义
2.哈夫曼编码（最优前缀码）：保证编码总长最短（省空间）无歧义（解码唯一）：任何字符的编码不是其他字符的编码的前缀（前缀码）
3.哈弗曼编码步骤：统计字符在句子中出现的概率or频率，当作权值构造哈夫曼树将哈夫曼树的结点左分支标0，右分支标1（如上图）；从根到叶子路径上的标号连接起来，就是该字符的编码 5.9.6 哈夫曼编码的算法实现 找编码：从叶子结点开始——根据其parent找到双亲下标，根据双亲的lch和rch判断改结点是左孩子还是右孩子，用于记录0和1；然后再重复根据parent找，直到找到根结点用char数组存储记录的编码值————char数组开辟n个空间，但只用到0~n-2位置，n-1存\0标志位。存储记录的编码值，是从数组后面地址往前面存储的（因为我们是从叶子结点开始的）
5.9.7 哈夫曼的解码 1.编码：输入各字符及其权值构造哈夫曼树——HT[i]进行哈夫曼编码——HC[i]查HC[i]，得到各字符的哈夫曼编码 2.解码：构造哈夫曼树——HT[i]依次读入二进制码，读入0走左孩子，读入1走右孩子当到达叶子结点时，译出字符从根出发，译下一个字符，直到二进制码被译完
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/19758.html
