数据结构与算法应用教程课件作者高佳琴第7章节完树与二叉树.ppt

1.哈夫曼树的定义 1)路径。2)路径长度。3)树结点的权。4)树的带权路径长度。 1.哈夫曼树的定义 图7-11　带权二叉树 5)哈夫曼树。 2.哈夫曼树的构造方法 1)给定n个权值{W1,W2,W3,…,Wi,…,Wn}，构成n棵二叉树的初始集合F={T1,T2,T3,…,Ti,…,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。2)在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。3)从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。4)重复2)、3)，直到集合F中只有一棵二叉树为止。 3.哈夫曼树的应用 1)为方便计算，将所有字符的出现频率乘以100，使其转化为整形数值集合，得到{5,29,7,8,14,23,3,11}。2)以此集合中的数值作为叶子结点的权值构造一棵哈夫曼树，如图7-12所示。 图7-12　构造哈夫曼树 3.哈夫曼树的应用 3)将左分支置为“0”，右分支置为“1”，由此哈夫曼树生成哈夫曼编码，如图7-13所示。 图7-13　生成哈夫曼编码 7.3　树、森林和二叉树的转换 7.3.1　树的存储结构7.3.2　树与二叉树的转换7.3.3　森林转换为二叉树7.3.4　二叉树转换为树和森林7.3.5　树和森林的遍历 7.3.1　树的存储结构 1.双亲表示法2.孩子表示法3.孩子兄弟表示法 1.双亲表示法 图7-14　树及其双亲表示法的存储结构a)树　b)树的双亲表示法示意图 2.孩子表示法 图7-15　树的孩子链表表示法示意图 3.孩子兄弟表示法 图7-16　树的孩子兄弟表示法示意图 7.3.2　树与二叉树的转换 1)在所有兄弟结点之间加一连线。2)对每个结点，除了保留与其长子的连线外，去掉该结点与其他孩子的连线。3)以根结点为轴心，将整棵树顺时针旋转一定的角度，使之层次分明。1)由于树的根结点无兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。2)一般树转换为二叉树以后，将使树的深度增加。 7.3.2　树与二叉树的转换 图7-17　一般树示意图 7.3.2　树与二叉树的转换 表格 表格 3)以根结点为轴心，将整棵树顺时针旋转一定的角度，使之层次分明。 图7-19　树转换为二叉树示例a)一棵树　b)相邻兄弟加连线　c)删除除长子外其他孩子的边线　d)转换后的二叉树 7.3.3　森林转换为二叉树 1)将森林中的每一棵树转换成相应的二叉树。2)因为转换所得的二叉树的根结点的右子树均为空，使第n棵树接入到第n-1棵的右边并成为它的右子树，第n-1棵二叉树接入到第n-2棵的右边并成为它的右子树，……第2棵二叉树接入到第1棵的右边并成为它的右子树，直到最后剩下一棵二叉树为止，就可得到一棵二叉树。 图7-20　森林转换为二叉树示意图a)森林　b)将森林中的各棵树转换成二叉树　c)转换后得到的二叉树 7.3.3　森林转换为二叉树 7.3.4　二叉树转换为树和森林 1)若结点x是双亲y的左孩子，则把x的右孩子、右孩子的右孩子、……直到最后一个右孩子都与y结点连起来。2)删掉原二叉树中所有的父结点与右孩子结点的连线。3)整理得到的各棵树，使之层次分明，显示出树或森林的形状。 3)整理得到的各棵树，使之层次分明，显示出树或森林的形状。 图7-21　二叉树还原为森林示意图a)二叉树　b)添加边线　c)去掉与右孩子的边线　d)还原后的森林 7.3.5　树和森林的遍历 1.树的遍历2.森林的遍历1.填空题2.简答题3.算法设计题1.实验目的2.实验内容3.实验步骤 1.树的遍历 (1)先根遍历　若树非空，则先访问根结点，然后从左到右依次先根遍历每棵子树。 图7-22　树的遍历 1.树的遍历 (2)后根遍历　若树非空，则依次后序遍历各子树，最后访问根结点。(3)按层遍历　先访问第一层结点(即树根结点)，再从左到右访问第二层结点，以此按层访问，直到全树中的所有结点都被访问为止，或者说直到访问完最深一层结点为止。 2.森林的遍历 (1)先序遍历　若森林非空，则先访问森林中第一棵树的根结点，再先序遍历第一棵树各子树，接着先序遍历第二棵树、第三棵树、……直到最后一棵树。(2)后序遍历　若森林非空，则先访问森林中第一棵树的根结点的子树，再访问森林中第一棵树的根结点，接着后序遍历第二棵树、第三棵树、……直到最后一棵树，依次后序遍历森林中的每一棵树。 1.填空题 (1)一棵深度为4的完全二叉树结点数的取值范围为。(2)树的基本存储方法有、、。(3)具有64个结点的完全二叉树的深度为。(4)设一棵二叉树共有50个叶子结点(终端结点)，则它共有个度为2的结点。(5