注：
满二叉树没有度为1的结点，所以分支结点数就是二度结点数。
3.一棵具有257个结点的完全二叉树，它的深度为9。
（注：
用Llog2（n）J+l=L8.xxJ+l=9
4.设一棵完全二叉树有700个结点，则共有个叶子结点。
5.设一棵完全二叉树具有1000个结点,则此完全二叉树有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树,有—个结点只有非空右子树。
另外，最后一结点为2i属于左叶子,右叶子是空的，所以有1个非空左子树。
完全二叉树的特点决定不可能有左空右不空的情况,所以非空右子树数=0.
6.一棵含有n个结点的k叉树，可能达到的最大深度为n,最小深度为2。
答：
当k=l（单叉树）时应该最深，深度=n（层）；当k=n-l（n-1叉树）时应该最浅，深度=2（层），但不包括沪0或1时的特例情况。
教材答案是“完全k叉树”，未定量。
）
7.二叉树的基本组成部分是：
根（N）、左子树（L）和右子树（R）。
因而二叉树的遍历次序有六种。
最常用的是三种：
前序法（即按NLR次序），后序法（即按LRN次序）和中序法（也称对称序法，即按LNR次序）。
这三种方法相互之间有关联。
若已知一棵二叉
树的前序序列是BEFCGDH,中序序列是FEBGCHD,则它的后序序列必是O
解：
法1：
先由已知条件画图，再后序遍历得到结果；
法2：
不画图也能快速得出后序序列，只要找到根的位置特征。
由前序先确定root,由中序先确定左子树。
例如，前序遍历BEFCGDH中，根结点在最前面，是B；则后序遍历中B—定在最后面。
法3：
递归计算。
如B在前序序列中第一，中序中在中间（可知左右子树上有哪些元素）,则在后序中必为最后。
如法对B的左右子树同样处理，则问题得解。
&中序遍历的递归算法平均空间复杂度为0（n）。
答：
即递归最大嵌套层数，即栈的占用单元数。
精确值应为树的深度k+1,包括叶子的空域也递归了一次。
9、用5个权值｛3,2,4,5,1｝构造的哈夫曼（Huffman）树的带权路径长度是_。
解：
先构造哈夫曼树，得到各叶子的路径长度之后便可求出WPL=（4+5+3）X24-（1+2）X3=33
/（15）
/«）；76）注：
两个合并值先后不同会导致编码不同，即哈夫曼编码不唯一）
453/池）（注：
合并值应排在叶子值之后）
12
（注：
原题为选择题:
A.32B.33C.34D.15）
10、N个结点的二叉树釆用二叉链表存放，共有空链域个数为也
11、深度为6（根层次为1）的二叉树至多有才-1个结点。
12、已知一棵完全二叉树的第5层有3个结点，其叶子结点数是_9。
三、单项选择题
（）1.不含任何结点的空树。
（A）是一棵树；（B）是一棵二叉树；
（C）是一棵树也是一棵二叉树；（D）既不是树也不是二叉树
答：
以前的标答是B,因为那时树的定义是nMl
（c）2.二叉树是非线性数据结构，所以o
A、它不能用顺序存储结构存储；B、它不能用链式存储结构存储；
C.顺序存储结构和链式存储结构都能存储；D、顺序存储结构和链式存储结构都不能使
（C）3•具有n（n>0）个结点的完全二叉树的深度为。
（A）「log/n）】（B）Llog2（n）」（C）Llog2（n）J+l（D）「log2（n）+f|
L［
似乎Llog2（n）+1」是对的？
（A）4.把一棵树转换为二叉树后，这棵二叉树的形态是。
（A）唯一的（B）有多种
（C）有多种，但根结点都没有左孩子（D）有多种，但根结点都没有右孩子
5.从供选择的答案中，选出应填入下面叙述_?
内的最确切的解答，把相应编号写
在答卷的对应栏内。
树是结点的有限集合，它L根结点，记为几其余的结点分成为m（mMO）个B的集合Tl,T2,Tm,每个集合又都是树，此时结点T称为的父结点，T：
称为T的子
结点（lWiWm）。
一个结点的子结点个数为该结点的_o
供选择的答案
答案：
ABC=1,1,3
6.从供选择的答案中，选出应填入下面叙述_?
内的最确切的解答,把相应编号写在
答卷的对应栏内。
二叉树Ao在完全的二叉树中，若一个结点没有_,则它必定是叶结点。
每棵树都能惟一地转换成与它对应的二叉树。
由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的C,而N的右子女是它在原树里对应结点的—o
供选择的答案
A：
①是特殊的树②不是树的特殊形式③是两棵树的总称④有是只有二个根结点的树形结构
B:
①左子结点②右子结点③左子结点或者没有右子结点④兄弟
C〜D：
①最左子结点②最右子结点③最邻近的右兄弟④最邻近的左兄弟
⑤最左的兄弟⑥最右的兄弟
答案：
A=B=C=D=
7、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1,则编号为49的结点的左孩子的编号为（A）
A、98B、99
答案：
ABCDE=2,1,1,3
8、设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为Ml、M2和M3。
与森林F对应的二叉树根结点的右子树上的结点个数是（D）
A）MlB）M1+M2C）M3D）M2+M3
9、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编
号，根结点编号为1,则编号最大的非叶结点的编号为（C）
A、48B、49C、50D、51
10、某二叉树结点的中序序列为A、B、C、D、E、F、G,后序序列为B、D、C、A、F、G、E,则其左子树中结点数目为（C）
A）3B）2C）4D）5
四、简答题（每小题4分，共20分）
1.一棵度为2的树与一棵二叉树有何区别?
答：
度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。
即,在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即
2.设如下图所示的二叉树B的存储结构为二叉链表，root为根指针，结点结构为:
C的结点类型定义如下：
struetnode{chardata;
struetnode
*lchild,rchild;
（lchild,data,rchild）o其中lchild,rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题：
1.对下列二叉树B,执行下列算法traversal（root）,试指出其输出结果；
2.
假定二叉树B共有n个结点，试分析算法traversal（root）的时间复杂度。
（共8分）
解：
这是“先根再左再根再右”，比前序遍历多打印各结点一次，输出结果为：
ABCCEEBADFFDGG特点：
①每个结点肯定都会被打印两次；②但出现的顺序不同，其规律是：
凡是有左子树的结点，必间隔左子树的全部结点后再重复出现；如A,B,D等结点。
反之马上就会重复出现。
如C,E,F,G等结点。
时间复杂度以访问结点的次数为主，精确值为2杓，时间渐近度为0（n）.
3.给定二叉树的两种遍历序列，分别是：
前序遍历序列：
D,A,C,E,B,H,F,G,I；中序遍历序列：
D,C,B,E,H,A,G,I,F,试画出二叉树B,并简述由任意二叉树B的前序
遍历序列和中序遍历序列求二叉树B的思想方法。
解：
方法是：
由前序先确定root,由中序可确定root的左、右子树。
然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。
将他们分别作为新的root,不断递归，则所有元素都将被唯一确定，问题得解。
28
A
25
AA
33
AA
A40
60•“08
“54
4.给定如图所示二叉树T,请画出与其对应的中序线索二叉树解：
要遵循中序遍历的轨迹来画出每个前驱和后继。
中序遍历序列：
5540256028083354
55
5、已知一棵二叉树，其中序序列DBCAFGE,后序序列DCBGFEA,构造该二叉树。
解：
A
DCF
6、已知叶子结点值2,3,5,6,9,11,构造哈夫曼树，计算其带权路径长度。
解：
7、给定权值{8,12,4,5,26,16,9},构造一棵带权路径长度最短的二叉树，并计算其带权路径长度。
解：
17
Ifi
17
或:
WPL=8X3+4X4+5X4+16X2+9X3+12X3+26X2=207
［注］:
哈夫曼树的左右子树可以互换。
8.
答：
（P604-26）试写出如图所示的二叉树分别按先序、
DLR：
ABDFJGKCEHILM
LDR：
BFJDGKACHELIM
LRD：
JFKGDBHLMIECA
中序、后序遍历时得到的结点序列。
（把如图所示的树转化成二叉树。
M
答：
i
并注意原有连线结点一律归入左子树，新添连线结点一律归入右子树。
g弋/HD
L/G卫
MJ
10画出和下列二叉树相应的森林。
答：
注意根右边的子树肯定是森林,而孩子结点的右子树均为兄弟。
11.假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07,0.19,
0.02,0.06,0.32,0.03,0.21,0.10。
试为这8个字母设计哈夫曼编码。
使用0〜7的二进制表示形式是另一种编码方案。
对于上述实例，比较两种方案的优缺点。
方案比较:
方案1的WPL=
2（0.19+0.32+0.21）+4（0.07+0.06+0.10）+5（0.02+0.03）=1.44+0.92+0.25=2.61
方案2的WPL=3（0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03）=3
结论：
哈夫曼编码优于等长二进制编码
六、算法设计题
1.编写递归算法，计算二叉树中叶子结点的数目。
解：
思路：
输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。
法一：
核心部分为：
法二：
intLeafCount_BiTree（BitreeT）//求二叉树中叶子结点的数目
{
辻（!
T）return0;〃空树没有叶子
elseif（!
T->lchild&&!
T->rchild）return1;〃叶子结点
elsereturnLeaf_Count（T->lchild）+Leaf_Count（T->rchild）;//左子树的叶子数加
上右子树的叶子数
}//LeafCount_BiTree
2.写出求二叉树深度的算法，先定义二叉树的抽象数据类型。
解：
intdepth（1iuyu*root）/*统计层数*/
{intd,p;/*注意每一层的局部变量d,p都是各自独立的*/
P=0；
if（root==NULL）return（p）;/*找到叶子之后才开始统计*/
else{
d=depth（root->lchild）;
if（d>p）p=d;/*向上回朔时，要挑出左右子树中的相对大的那个深度值*/
d=depth（root->rchild）;
if（d>p）p=d;
}
return（p）;
}
intGet_Depth（BitreeT）//求子树深度的递归算法
{
if（!
T）return0;
else
{
m=Get_Depth（T->lch订d）;
n=Get_Depth（T->rch订d）;
return（m>n?
m:
n）+l;
}
}//Get_Depth
3、求二叉树中以元素值为x的结点为根的子树的深度。
解：
intGet_Sub_Depth（BitreeT,intx）〃求二叉树中以值为x的结点为根的子树深度{辻（T->data==x）
{printf（"%d\n",GetJ）epth（T））;〃找到了值为x的结点，求其深度
exit1;
}}
else{
if（T->lch订d）Get_Sub_Depth（T->lchild,x）;
辻（T->rchild）Get_Sub_Depth（T->rch订d,x）;〃在左右子树中继续寻找
}}//Get_Sub_Depth4•编写按层次顺序（同一层自左至右）遍历二叉树的算法。
解：
思路：
既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。
这是一个循环算法，用wh订e语句不断循环，直到队空之后自然退出该函数。
技巧之处：
当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，……以此产生了按层次输出的效果。
假设max已知*/
/*置空队*/
/*根结点进队★/
/*队列不空权
法二：
voidLayerOrder（BitreeT）〃层序遍历二叉树
{
InitQueue（Q）;//建立工作队列
EnQueue（Q,T）;
while（!
QueueEmpty（Q））
{
DeQueue（Q,p）;
visit（p）;
if（p->lchild）EnQueue（Q,p->lchild）;
if（p->rchild）EnQueue（Q,p->rchild）;
}
}//LayerOrder
5.编写算法判别给定二叉树是否为完全二叉树。
答：
intIsFull.Bitree（BitreeT）//判断二叉树是否完全二叉树，是则返回1,否则返回0{InitQueue（Q）;
flag=O;
EnQueue（Q,T）;//建立工作队列
while（!
QueueEmpty（Q））
{{
DeQueue（Q,p）;
辻（!
p）flag=l;
elseif（flag）return0;
else
{EnQueue（Q,p->lchild）;
EnQueue（Q,p->rchild）;〃不管孩子是否为空，都入队列
}}//whi.le
return1;
}//IsFull_Bitree
分析:
该问题可以通过层序遍历的方法来解决.与6.47相比，作了一个修改,不管当前结点是否有左右孩子，都入队列.这样当树为完全二叉树时，遍历时得到是一个连续的不包含空指针的序列.反之，则序列中会含有空指针.
6、阅读下列算法，若有错，改正之。
7、阅读下面程序，并回答有关问题。
其中BSTtee为用二叉链表表示的二叉排序树类型。
（1）简要说明程序功能。
（5分）
（2）n个结点的满二叉树的深度h是多少？
（3分）
（3）假设二叉排序树*bst是有n个结点的满二叉树，给出算法的时间复杂度。
（2分）intProc（BSTree*bst,KeyTJpeK）
{BSTreef,q,s;
s=（BSTree）malloc（sizeof（BSTNode））;
s->key=K;s->Ichild=NULL;s->rchild=NULL;
if（*bst==NULL）{*bst=s;return1;}
f=NULL;q=*bst;
while（q!
=NULL）
{if（Kkey）
{f=q;q=q・>Ichild;}
else
{f=q;q=q・>rchild;}
}
if（Kkey）f->Ichild=s;
elsef->rchild=s;
return1;
}
解：
（1）在二叉排序树中插入关键字为K的结点
（2）h=Iog2（n+1）或h=[Iog2n]+1（方括号表示向下取整）
（3）O（logz（n+1））或0（log2n）
8、试设计算法计算一棵给定二叉树上所有结点数目。
假设二叉树的存储结构描述如下:
typedefstructBiTNode{
TElemTypedata;
structBiTNode*lchild;*rchild;/*左右孩子指针*/
}BiTNode,*BiTree；
解：
intCountNode（BinTreebt）{
if（bt==Null）
return（0）;
else{
numl=CountNode（root->lchild）;
num2=CountNode（root->rchild）;
return（numl+num2+l）;
}
}
9、计算二叉树上单分支结点数目。
假设二叉树的存储结构描述如下：
typedefstructBiTNode（
TElemTypedata;
structBiTNode*lchild;*rchiId;/*左右孩子指针*/
}BiTNode,*BiTree；
解：
FUNCnodesl（t:
bitre）:
integer;
ift=Nullthennodesl:
=0
elseif（t->lchikl=Null）and（t->rchild=Null）thennodesl:
=0
elseif（t->lchild=Null）or（t->rchild=Null）
thennodesl:
=l+nodesl（t->lchild）+nodesl（t->rchild）
elsenodesl:
=nodesl（t->lchil（I）+nodesl（t->rchild）
ENDF;
升级会员 