文章目录哈夫曼树编程实现哈夫曼树哈夫曼编码例子树的性质树的存储树与二叉树的转换森林与二叉树转换B树B树的python实现B 树练习题哈夫曼树思想使权值比重大的节点最靠近树根权值越小越远离树根二叉树中叶子节点的带权路径为 权重w i ∗ l i {w_i * l_i}wi​∗li​l i {l_i}li​为根到叶子的路径长度w i {w_i}wi​为叶子节点的比例权重树的带权路径长度 所有叶子节点的带权路径长度和有n个叶子节点的二叉树中带权路径长度最小的二叉树为哈夫曼树 是一种最优的二叉树哈夫曼树不是唯一的但树WPL 【带权路径长度】是唯一的哈夫曼树的构建步骤以每个权值创建只有一个根节点的二叉树形成二叉树森林并按照树根权值升序排序在该森林中每次取根节点权值最小的两棵树合并成一棵新树新树根的权值为左右子树根权值之和从森林中删除使用过的旧树添加新树并重新排序重复以上步骤直到森林中只剩一棵树停止利用如下权值构造一棵哈夫曼树哈夫曼树没有度为1的节点即都是度为0或2哈夫曼树 优化 if 分支的比较次数 if 条件先走比例最大的情况elif 条件走剩余部分中比例最大的情况依次处理编程实现哈夫曼树节点结构数据、左子树指针、右子树指针,父节点指针构建以【7524】为权值的哈夫曼树以每个权值的叶子节点为根构建只有根的二叉树放入列表列表升序排序以根节点权值升序并取出根节点权值最小的两棵树分别为左右子树新的根节点权值为左右子树权值之和新的二叉树放入列表中并重新排序以根节点权值升序并重复步骤2直到列表中只有一棵树为止。classNode:def__init__(self,data,leftNone,rightNone,height1,parentNone):self.datadata self.leftleft self.rightright# 可以加入统计树高self.heightheight self.parentparentdefbuild_huffman(alist):# 初始化只有一个根的二叉树的森林forest[Node(v)forvinalist]whilelen(forest)1:# 升序排序forest.sort(keylambdai:i.data)leftforest.pop(0)rightforest.pop(0)# 合并树root_dataleft.dataright.data rootNode(root_data)root.leftleft root.rightright root.heightmax(left.height,right.height)left.parentroot right.parentroot# 新树入森林forest.append(root)returnforest[0]defpreorder_travel(root):ifrootisNone:returnprint(root.data,end )preorder_travel(root.left)preorder_travel(root.right)# 中序inorder# 后序postorderif__name____main__:weights[7,5,2,4]rootbuild_huffman(weights)preorder_travel(root)# 先序遍历18 7 11 5 6 2 4哈夫曼编码编码将字符信息转为0/1二进制串为节约传输时间使编码的二进制串尽可能短- 非等长编码任何字符的编码不能是其他编码的前缀保证解码的唯一性哈夫曼编码统计每个字符的概率作为权重按照权重构建哈夫曼树左分支的路径符号为0右分支路径符号为1从根到叶子节点的路径符号连接即为该叶子对应字符的编码例子传输字符串为“ABCACCDAEAE”每个字符概率为0.36、0.1、0.27、0.1、0.18计算该字符串的哈夫曼编码结果。思路统计字符概率作为权重以权重构建哈夫曼树左子树路径标记为0 右子树路径标记为1每个叶子对应的字符编码结果为路径符号连接编程实现classNode:def__init__(self,data,leftNone,rightNone,height1,parentNone):self.datadata self.leftleft self.rightright self.heightheight self.parentparent# 父节点defbuild_huffman(alist):# 初始化只有一个根的二叉树的森林forest[Node(v)forvinalist]origin_leafsforest.copy()whilelen(forest)1:# 升序排序forest.sort(keylambdai:i.data)leftforest.pop(0)rightforest.pop(0)# 合并树root_dataleft.dataright.data rootNode(root_data)root.leftleft root.rightright root.heightmax(left.height,right.height)left.parentroot right.parentroot# 新树入森林forest.append(root)returnforest[0],origin_leafsdefcount_weight(s): 统计每个字符的概率概率越大编码越短 dict_{}nlen(s)forcins:ifcindict_:dict_[c]1else:dict_[c]1char_list[]weights[]fork,vindict_.items():char_list.append(k)weights.append(round(v/n,3))returnchar_list,weightsdefhuffman_encode(leafs,root):numlen(leafs)# 每个叶子节点的编码node_encode[]*numforiinrange(num):nodeleafs[i]whilenodeisnotroot:# 从叶子节点开始向根节点查找ifnode.parent.leftisnode:node_encode[i]0node_encode[i]else:node_encode[i]1node_encode[i]nodenode.parentreturnnode_encodeif__name____main__:sABCACCDAEAEchar_list,weightscount_weight(s)print(char_list)print(weights)# 创建huffman树root,leafsbuild_huffman(weights)preorder_travel(root)# 1.001 0.364 0.182 0.182 0.091 0.091 0.637 0.273 0.364# 获取每个叶子节点对应的符号的 编码resulthuffman_encode(leafs,root)print(\n,result)# 字符 [A, B, C, D, E]# 频数 [4, 1, 3, 1, 2] , 计算树的WPL 时使用频数计算# 权重 [0.364, 0.091, 0.273, 0.091, 0.182]# 先序遍历1.001 0.364 0.182 0.182 0.091 0.091 0.637 0.273 0.364# 编码 [11, 010, 10, 011, 00]计算该huffman树的唯一WPL 2 * 4 3 * 1 2 * 3 3*1 2 * 2 24 即传输该字符串需要的总比特数每个字符的平均码长 W P L 总字符数 \frac {WPL} {总字符数}总字符数WPL​24 11 \frac {24} {11}1124​ 2.18等长编码即每个字符的编码bit 一样长一个bit位可以表示2 1 2^121x xx个bit位可以表示n个字符2 x n 2^xn2xn则x l o g 2 n xlog_2nxlog2​n向上取整压缩率节省率 (等长编码总位数 − 哈夫曼编码总位数) / 等长编码总位数 × 100%。树的性质除了根节点每个节点都有一个前驱节点【一条边】所以 n个节点的树中有n − 1 {n-1}n−1条边度为k的树中第i层最多有k i − 1 {k^{i-1}}ki−1个节点度为k的、高为h的树中至多有( k h − 1 ) / ( k − 1 ) {(k^h - 1) /( k -1)}(kh−1)/(k−1)个节点n个节点的度为k的树中最小高度为l o g k ( n ∗ ( k − 1 ) 1 ) {log_k(n*(k-1) 1) }logk​(n∗(k−1)1)向上取整树的存储双亲表示法每个节点存储数据、父节点的编号或地址便于查找父节点孩子节点表示法每个节点存储数据、孩子的编号或地址便于查找孩子节点数组单链表节点存储数据和链表的头节点链表表示从左到右的孩子节点长子兄弟表示法长子作为左子节点兄弟作为右子节点树与二叉树的转换每个树都可以转为唯一的二叉树基于左孩子右兄弟表示法树转为二叉树二叉树的右子树一定为空以树根为二叉树的根节点最左侧孩子作为左子树每个节点的右兄弟作为自己的右子树 【形成右链】删除线每个父节点只保留最左侧孩子的连线删除与其他孩子的连线加线兄弟之间加右链线递归处理每个孩子节点的转换【从左到右顺序】二叉树还原树以二叉树的根为树根二叉树的左孩子作为树的第一个最左侧的孩子二叉树左孩子的右链中恢复树的其他孩子删除原二叉树中双亲节点与右孩子的连线递归处理二叉树中其他节点的转换【从左到右的顺序】森林与二叉树转换森林转为二叉树将森林中的每棵树转为唯一二叉树将依次转换的每棵二叉树的根连线形成右链即后面的二叉树作为其前面的二叉树的右子树以第一棵二叉树的根为整个二叉树的树根二叉树转为森林将根节点与右孩子、右孩子的右孩子… 之间的连线断开形成多棵二叉树每棵二叉树还原树得到初始的森林B树B树是多路平衡查找树是多叉树所有叶子节点在同一层保证平衡叶子节点不存储信息表示查找失败终端节点表示最后一排具有关键字的节点左子树的值都小于父节点中的值父节点的值都小于右子树的值B树的阶表示每个节点的子节点数中的最大值一般设置为偶数B树的键表示每个节点中存储的数据个数B树用于磁盘的存储、查询如文件系统、数据库索引m阶B树的性质根节点至少一个键至少两个子树最多m个子树m-1个键每个节点中的值升序 或者降序除根以外的节点至少m/2 【向上取整】棵子树至多m棵子树m阶除根以外的节点至少m/2 - 1【向上取整】个键至多m-1个键所有叶子节点在同一层保证平衡树矮磁盘IO少查询效率高中序遍历有序性计算如下B树的阶数注意叶子节点没有画出4阶m阶(如6阶)B树的插入:取一个待插入的值若当前B树为空或仅有一个根节点则直接插入根节点否则就与根中的键比较大小走进对应的子树节点中插入并排序一般升序也可降序若插入后当前节点键数超出上限m-1则触发分裂否则本次插入完成将中间的键值提取到父节点中左边的键值形成左节点右边的键值形成右节点若父节点键值超限则触发分裂同样方式处理分裂如下为1到17之间的序列数值构建的B树m阶B树的查找从根节点中依次比较每个关键字找到则结束未找到 则在关键字区间内的子树中继续查找若走到叶子节点则查找失败m阶(如6阶)B树的删除叶子节点的键删除后若剩余关键字数量大于等于最小阈值则结束否则删除后【键个数不满足节点最少键数】则向左右兄弟借若向左兄弟借则左兄弟最大键值进入父节点父节点中被夹持的键值借给键不足的节点当左右兄弟都不够借时当前节点需要与左或右兄弟进行合并先将父节点中被夹持的键值拉下来在一起合并到兄弟节点中非叶子节点的删除将左边子树的最大值【前驱节点】或者右边子树的最小值【后驱节点】与待删除的值对换然后在页节点中删除该值删除键后不满足最小关键字数则向兄弟节点借。如下为5阶B树尝试删除键3、25删除3【删除后向右兄弟借父下来兄上去】删除25【叶子节点中直接删除】删除 38 非叶子节点B树的python实现pendingB 树B树的根节点至少两个键两个子树m阶 B树的非根非叶子节点的子树返回【m/2 上取整, m】节点关键字与子树数量保持一致叶子节点存储数据并且叶子之间存在链表关系非叶子节点中不存储数据只存储导航信息【数据的索引】练习题答案D, ADADB树构建基于如下的数据以插入方式构建3阶B树画出构建过程{15, 5, 20, 3, 10, 25, 8, 12, 18, 22, 28}1.插入15空树直接创建根节点2.插入5只有一个根节点时直接插入根 [5 | 15]3.插入20[5 | 15 | 20] 关键字超限触发分裂4.插入3 3 15 则到关键字15的左侧子树中插入5.插入10 [3 | 5 | 10] 触发分裂6.插入257.插入88在5-15关键字之间所以到这个区间下的子树中插入8.插入12[8 | 10 | 12] 触发分裂提取中间节点到父节点中再次触发父节点的分裂9.插入18[18 | 20 | 25]10.插入2211.插入28形成最终的B树