树和二叉树数据结构试卷.ppt

3、哈夫曼编码 在数据通信中，经常需要将传送的文字转换为二进制字符0和1组成的二进制字符串，我们称这个过程为编码。显然，希望电文编码的代码长度最短。哈夫曼树可用于构造使电文编码的代码长度最短的编码方案。 具体构造方法如下：设需要编码的字符集合为{d0,d1,…,dn-1},各个字符在电文中出现的次数集合为{W0,W1,…,Wn-l}，以d0,d1,…,dn-1作为叶结点，以w0, W0,W1,…,Wn-l作为各根结点到每个叶结点的权值构造一棵二叉树，规定哈夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的编码称为哈夫曼编码。 实质：就是利用使用频率越高的采用越短的编码。 哈夫曼树的基础要点 1、求具有最小带权外部路径的扩充二叉树的算法成为哈夫曼算法。对于给定的一组权w={10,12,16,21,30}，通过该算法求出扩充二叉树的带权外部路径长度为（ ）。 2、在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。（对/错） 【例11】假定用于通讯的电文仅有a，b，c，d，e，f，g，h8个字母组成，字母在电文中出现的频率为：0.07,0.19,0,02,0.06,0.32,0.03,0.21和0.10。试为这些字母设计哈夫曼编码。 练习 1、一棵左、右子树均不空的二叉树在先序线索化后，其空指针域是多少？ 2、有n个结点并且高度为n的二叉树的数目是多少？ 3、已知完全二叉树的第七层有10个叶子结点，则整个二叉树的结点个数最多是多少？ 4、一棵二叉树的先序、中序和后序序列分别如下，其中一部分未显示出来。试求出空格处的内容，并画出该二叉树。 先序序列：（）B（）F（）ICEH（）G 中序序列：D（）KFIA（）EJC（） 后序序列：（）K（）FBHJ（）G（）A 5.对于如图所示的二叉树： (1)请画出它的顺序存储结构图； (2)请将它转换成森林。 6.设F={T1,T2,T3}是森林，试画出所对应的二叉树，森林如下图所示。 7.如果一棵哈夫曼树T有n0个叶子结点，那么，树T有多少个结点，要求给出求解过程。 8.下表所列的数据表给出了在一篇有19710个词的英文文章中出现最普通的15个单词的出现频度。假定一篇正文仅由上述字符数据表中的词组成，那么它们的最佳编码是什么？平均长度是多少? 9.用一维数组存放一棵完全二叉树：ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。 10.从概念上讲，树、森林和二叉树是三种不同的数据结构，将树、森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。 【解】 其目的是：树和森林采用二叉树的存储结构并利用二叉树的已有算法解决树和森林的有关问题。主要区别是：树中结点的最大度数没有限制，而二叉树结点的最大度数为2；树的结点无左右之分，而二叉树的结点有左右之分。 11.任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点中有(m-1)个结点的度为2，其余度为1。 12.已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？ 13.一棵有n个结点的满二叉树有多少个度为1的结点，有多少个分支(非终端)结点和多少个叶子结点，该满二叉树的深度为多少。 14.将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度是多少？ 15.设森林F对应的二叉树为B,它有m个结点，B的根为p, p的右子树结点个数为n，森林F中第一棵树的结点个数是多少？ 16.在一棵二叉树的先序序列、中序序列和后序序列中,任意两种序列的组合合可以惟一地确定这棵二叉树吗？若可以，有哪些组合，证明之：若不可以，有哪些组合，证明之。 17.对于一个栈，若其入栈序列为1，2, 3,…，n,不同的出入栈操作将产生不同的出栈序列。其出找序列的个数正好等于节点个数为n的二叉树的个数，且与不同形态的二叉树一一对应。请简要叙述一种从栈输入(固定为1, 2, 3,…，n)/输出序列对应一种二叉树形态的方法，并以入栈序列1, 2，3(即n等于3)为例加以说明。 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * 【例】给出如下图所示的二叉树的链式存储结构。 四、二叉树的基本运算及其实现 1、二叉树基本运算概述 （1）创建二叉树：creatree(*b,*str)； （2）找结点：fi