发布时间 : 星期日 文章第6章 树和二叉树习题更新完毕开始阅读1a95c46748d7c1c708a145f7
37. 非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子√ 39．度为二的树就是二叉树。×
42. 在中序线索二叉树中，每一非空的线索均指向其祖先结点。√ 43. 线索二叉树的优点是便于是在中序下查找前驱结点和后继结点。√ 44. 二叉树中序线索化后，不存在空指针域。× 45．霍夫曼树的结点个数不能是偶数。√
46. 一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。× 47. 哈夫曼树无左右子树之分。×
48．当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。×
49．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。√
50. 用链表（llink-rlink）存储包含n个结点的二叉树时，结点的2n个指针区域中有n+1
个空指针。( ) √ 三、填空题
1．二叉树由_(1)__，__(2)_，_(3)__三个基本单元组成。 2．树在计算机内的表示方式有_(1)__，_(2)__，_(3)__。
3．在二叉树中，指针p所指结点为叶子结点的条件是______。
4．中缀式a+b*3+4*（c-d）对应的前缀式为__(1)_，若a=1，b=2，c=3，d=4，则后缀式db/cc*a-b*+的运算结果为_(2)__。
6．具有256个结点的完全二叉树的深度为______。
7．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶子结点。
8．深度为k的完全二叉树至少有___(1)____个结点，至多有___(2)____个结点。
9．深度为H 的完全二叉树至少有_(1)__个结点；至多有_(2)__个结点；H和结点总数N之间的关系是 (3)__。
12．一棵有n个结点的满二叉树有__(1)_个度为1的结点、有__(2)_个分支 （非 终端）结点和__(3)_个叶子，该满二叉树的深度为_(4)__。
13．假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是______。 14．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =______ 15．设只含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为______,最小结点数为______。
17．高度为K的完全二叉树至少有______个叶子结点。 18．高度为8的完全二叉树至少有______个叶子结点。
19．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是______。 20．一个有2001个结点的完全二叉树的高度为______。
23．如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为______。
24．如果结点A有 3个兄弟，而且B是A的双亲，则B的度是______。
26．完全二叉树中，结点个数为n，则编号最大的分支结点的编号为______。
27．设一棵完全二叉树叶子结点数为k,最后一层结点数>2，则该二叉树的高度为______。 28．对于一个具有n个结点的二元树，当它为一棵_(1)_二元树时具有最小高度，当它为一棵_(2)_时，具有最大高度。
29．具有N个结点的二叉树，采用二叉链表存储，共有______个空链域。
30．8层完全二叉树至少有______个结点，拥有100个结点的完全二叉树的最大层数为
______。
31．含4个度为2的结点和5个叶子结点的二叉树，可有______个度为1的结点。
32．一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为______。
33． n（n大于1）个结点的各棵树中，其深度最小的那棵树的深度是_(1)__。它共有_(2)__个叶子结点和_(3)__个非叶子结点，其中深度最大的那棵树的深度是_(4)__，它共有_(5)__个叶子结点和_(6)__个非叶子结点。
34． 每一棵树都能唯一的转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，对称序列是FEBGCHD，则它的后序序列是_(1)__。设上述二叉树是由某棵树转换而成，则该树的先根次序序列是_(2)__。 35．先根次序周游树林正好等同于按_(1)__周游对应的二叉树，后根次序周游树林正好等同于按__(2)_周游对应的二叉树。
36．二叉树结点的对称序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E,则该二叉树结点的前序序列为_(1)__,则该二叉树对应的树林包括_(2)__棵树。 7．二叉树的先序序列和中序序列相同的条件是______。
38．已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahfcg，则该二叉树的根为_(1)__，左子树中有_(2)__， 右子树中有_(3)__。
39．设二叉树中每个结点均用一个字母表示，若一个结点的左子树或右子树为空，用 ．表示，现前序遍历二叉树，访问的结点的序列为ABD.G...CE.H..F．．，则中序遍历二叉树时，访问的结点序列为_(1)__;后序遍历二叉树时，访问的结点序列为_(2)__。 40．已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是____。
41．现有按中序遍历二叉树的结果为abc，问有_(1)__种不同的二叉树可以得到这一遍历结果，这些二叉树分别是_(2)__。
43．利用树的孩子兄弟表示法存储，可以将一棵树转换为______。 44．若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的______序列中的最后一个结点。 45．先根次序周游树林正好等同于按______周游对应的二叉树；后根次序周游树林正好等同于______周游对应的二叉树。
46. 在一棵存储结构为三叉链表的二叉树中，若有一个结点是它的双亲的左子女，且它的双亲有右子女，则这个结点在后序遍历中的后继结点是______。
47．一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为：______。 48．具有n个结点的满二叉树，其叶结点的个数是______。
50．线索二元树的左线索指向其______，右线索指向其______。 52．哈夫曼树是______。
53．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______。 54．有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是_(1)__，带权路径长度WPL为_(2)__。
55．有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为_(1)__，字符c的编码是_(2)__。
四、应用题
1．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。
2．树和二叉树之间有什么样的区别与联系？
5．将算术表达式（（a+b）+c*(d+e)+f）*(g+h)转化为二叉树。
11．已知完全二叉树的第七层有10个叶子结点，则整个二叉树的结点数最多是多少？ 12．高度为10的二叉树，其结点最多可能为多少？
23．已知完全二叉树有30个结点，则整个二叉树有多少个度为0的结点？ 30．假设高度为H的二叉树上只有度为0和度为2的结点，问此类二叉树中的结点数可能达到的最大值和最小值各为多少？
40. 由二叉树的中序序列及前序序列能唯一的建立二叉树，试问中序序列及后序序列是否也能唯一的建立二叉树，不能则说明理由，若能对中序序列DBEAFGC和后序序列DEBGFCA构造二叉树。
41. 设一棵二叉树的前序序列为ABDGECFH，中序序列为：DGBEAFHC 。试画出该二叉树。 (2) 假定某二叉树的前序遍历序列为ABCDEFGHIJ,后序遍历序列为CEFDBJIHGA,据此两个序列能否唯一确定此二叉树? 若不能,试画出两样具有同样上述遍历序列的二叉树.
43. ① 试找出满足下列条件的二叉树
1）先序序列与后序序列相同 2）中序序列与后序序列相同
3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同 ② 已知一棵二叉树的中序序列和后序序列分别为DBEAFIHCG和DEBHIFGCA，画出
这棵二叉树。
44．将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果） D G A J H I E B C L M K N O F
P 46．设一棵二叉树的先序、中序遍历序列分别为
先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C （1）画出这棵二叉树。
（2）画出这棵二叉树的后序线索树。 （3）将这棵二叉树转换成对应的树（或森林）。 47．已知一棵二叉树的对称序和后序序列如下： 对称序：GLDHBEIACJFK 后序： LGHDIEBJKFCA (1) 给出这棵二叉树： (2) 转换为对应的森林：
48．设某二叉树的前序遍历序列为:ABCDEFGGI，中序遍历序列为:BCAEDGHFI： （1）试画出该二叉树；
类似本题的另外叙述有： （1）已知二叉树的先序序列: CBHEGAF, 中序序列: HBGEACF, 试构造该二叉树 （2）已知二叉树按中序排列为BFDAEGC，按前序排列为ABDFCEG，要求画出该二叉树。 （3）已知一棵二叉树的前序序列 A,B,D,C,E,F，中序序列B,D,A,E,F,C. 画出这棵二叉树。
（4）已知一棵二叉树的前序遍历结果是：ABCDEFGHIJ,中序遍历的结果是：BCEDAGHJIF,试画出这棵二叉树。
（5）已知二叉树BT各结点的先序、中序遍历序列分别为ABCDEGF和CBAEDF，试画出该二叉树。
49. 假设一棵二叉树的前序序列为ABCD,它的中序序列可能是DABC吗?
类似本题的另外叙述有： （1）一棵前序序列为1，2，3，4，的二叉树，其中序序列可能是4，1，2，3吗？设一棵二叉树的前序序列为1，2，3，4，5，6，7，8，9，其中序序列为2，3，1，5，4，7，8，6，9，试画出该二叉树。
50．一棵非空的二叉树其先序序列和后序序列正好相反，画出这棵二叉树的形状。 51．已知一棵二叉树的后序遍历序列为EICBGAHDF，同时知道该二叉树的中序遍历序列为CEIFGBADH，试画出该二叉树。
类似本题的另外叙述有： （1）已知二叉树ＢＴ各结点的中序和后序序列分别为ＤＦＢＡＣＥＧ和ＦＤＢＧＥＣＡ，试构造出该二叉树ＢＴ，并作简要说明。
（2）已知二叉树的中序遍历序列为G F B E A N H M，后序遍历的结点序列为G E B F H N M A ，画出此二叉树的形态。
（3）已知二叉树的后序序列为ABCDEFG 和中序序列为ACBGEDF，构造出该二叉树。 （4）已知某二叉树的后序遍历和中序遍历如下，构造出该二叉树。
后序遍历序列： G D B E I H F C A 中序遍历序列：D G B A E C H I F （5）已知一个二分树的中序序列和后序序列如下：
中序：A B C D E F G H I J 后序：A C D B H J I G F E 试画出此二分树的结构。
52．假设一棵二叉树的层次序列为ABCDEFGHIJ，中序序列DBGEHJACIF。请画出这棵二叉树。
67．按下面要求解下图中二叉树的有关问题：
(1)对此二叉树进行后序后继线索化 ；(2)将此二叉树变换为森林； (3)用后根序遍历该森林，；写出遍历后的结点序列。
类似本题的另外叙述有： （1）已知一棵二叉树的先序遍历序列为：AEFBGCDHIKJ，中序遍历序列为：EFAGBCHKIJD。试写出此二叉树的后序遍历序列，并用图画出它的后序线索二叉树。
68．对下图所示二叉树分别按前序﹑中序﹑后序遍历，
A 给出相应的结点序列，同时给二叉树加上中序线索。
E B C K F D I G L J M H O N P 第67题图
69. 假设一个二叉树的两种遍历如下：
前序：ABFGCHDEIJLK 中序：FGBHCDILJKEA （1）画出这棵二叉树以及它的中序线索树；
70．已知一棵二叉树的中序（或中根）遍历结点排列为DGBAECHIF，后序（或后根）遍历结点排列为GDBEIHFCA， （1）试画出该二叉树；
（2）试画出该二叉树的中序穿线（或线索）树； （3）试画出该二叉树（自然）对应的森林； 71．设二叉树BT的存储结构如下:
1 2 3 4 5 6 7 8 9 10
Lchild Data Rchild 0 0 J H 0 0 2 F 0 3 D 7 B 5 A 8 C 0 10 1 I 0 0 E G 9 4 0 0 0 其中BT为树根结点的指针，其值为6,Lchild,Rchild分别为结点的左、右孩子指针域,data为结点的数据域。试完成下列各题:
（l）画出二叉树BT的逻辑结构;
（2）写出按前序、中序、后序遍历该二叉树所得到的结点序列; （3）画出二叉树的后序线索树。
73．一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为多少？ 77. 已知一棵二叉树的前序遍历为ABECDFGHIJ，中序遍历为EBCDAFHIGJ。
78. 试画出这棵树和它的中序线索树。假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计哈夫曼编码树。
（1）假设用于通讯的电文由8个字符组成，其出现的频率为5,29,7,8,14,23,3,11。试为这8个字符设计哈夫曼编码。 （2）试构造一棵二叉树,包含权为1,4,9,16,25,36,49,64,81,100等10个终端结点,且具有最小的加权路径长度WPL。
（9）带权结点为{5,6,7,8,9}，构造Huffman树，计算带权路径长度。
（10）以数据集{2,5,7,9,13}为权值构造一棵哈夫曼树，并计算其带权路径长度。
（11）假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为7,19,2,6,32,3，21,10。试为这8个字母设计哈夫曼编码。使用0∽7的二进制表示形式是另一 种编码方案。对于上述实例，比较两种方案的优缺点。
（12）设用于通讯的电文仅由8个字母组成，他们在电文中出现的频率分别为0.30，0.07，0.10，0.03，0.20，0.06,0.22，0.02，试设计哈夫曼树及其编码。使用0---7的二进制表示形式是另一种编码方案。给出两种编码的对照表、带权路径长度WPL值并比较两种方案的优缺点。
(13) 给定一组权值2,3,5,7,11,13,17,19,23,29，31，37，41，试画出用Huffman算法建造的Huffman树。
(14) 以数据集{3,4,5,8,12,18,20,30}为叶结点，构造一棵哈夫曼树，并求其带权路径长度。