《数据结构与算法》第六章-树与二叉树习题

《数据结构与算法》第二部分 习题精选

一、下面是有关二叉树的叙述，请判断正误

（ ）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空

指针域。

（ ）2.二叉树中每个结点的两棵子树的高度差等于1。

（ ）3.二叉树中每个结点的两棵子树是有序的。

（ ）4.二叉树中每个结点有两棵非空子树或有两棵空子树。

（ ）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字

值，且小于其右非空子树（若存在的话）所有结点的关键字值。

（ ）6.二叉树中所有结点个数是2

k-1

-1，其中k是树的深度。

（ ）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。

（ ）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2

i

—1个

结点。

（ ）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有

n+1个为空指针。

（ √ ）10. 具有12个结点的完全二叉树有5个度为2的结点。

二、填空

1． 由３个结点所构成的二叉树有 种形态。

2. 一棵深度为6的满二叉树有 个分支结点和 个叶子。

3． 一棵具有２５７个结点的完全二叉树，它的深度为 。

4.设一棵完全二叉树有700个结点，则共有 个叶子结点。

5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 个叶子结点，有 个

度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。

6.一棵含有n个结点的k叉树，可能达到的最大深度为 ，最小深度为 。

7. 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次

序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按 次序）和

中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉

树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必

是 。

8.中序遍历的递归算法平均空间复杂度为 。

9.用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是 。

三、单项选择题

（ ）1． 不含任何结点的空树 。

（Ａ）是一棵树; （Ｂ）是一棵二叉树;

（Ｃ）是一棵树也是一棵二叉树; （Ｄ）既不是树也不是二叉树

（ ）2．二叉树是非线性数据结构，所以 。

（Ａ）它不能用顺序存储结构存储; （Ｂ）它不能用链式存储结构存储;

（Ｃ）顺序存储结构和链式存储结构都能存储;

（Ｄ）顺序存储结构和链式存储结构都不能使用

（ ）3. 具有n(n>0)个结点的完全二叉树的深度为 。

(Ａ) log

2

(n) (Ｂ)  log

2

(n) (Ｃ)  log

2

(n) +1 (Ｄ) log

2

(n)+1

（ ）4．把一棵树转换为二叉树后，这棵二叉树的形态是 。

（Ａ）唯一的 （Ｂ）有多种

（Ｃ）有多种，但根结点都没有左孩子 （Ｄ）有多种，但根结点都没有右孩子

四、算法设计题

1.编写递归算法，计算二叉树中叶子结点的数目。

2.写出求二叉树深度的算法，先定义二叉树的抽象数据类型。

或编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。

3.编写按层次顺序（同一层自左至右）遍历二叉树的算法。

或：按层次输出二叉树中所有结点；

4. 已知一棵具有n个结点的完全二叉树被顺序存储于一维数组A中，试编写一个算法打印

出编号为i的结点的双亲和所有的孩子。

5.编写算法判别给定二叉树是否为完全二叉树。

6、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，

0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用0～7的二进制

表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。

习题精选答案

一、

1.（√）2.（×） 3.（√） 4.（×） 5.（×）

6.（×） 7.（×） 8.（×）9.（ √ ）。10.（ √ ）

二

1．5 2. 31 32 3．9 4. 350 5. 500 499 1 0

6. n 2 7. L R N F E G H D C B 8. O(n) 9. 33

三、单项选择题

1．（C）2．（C） 3.（C）4．（A）

四、1. 解：思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空

者，则为叶子，将其打印出来。

法一：核心部分为：

DLR(liuyu *root) /*中序遍历 递归函数*/

{if(root!=NULL)

{if((root->lchild==NULL)&&(root->rchild==NULL)){sum++; printf("%dn",root->data);}

DLR(root->lchild);

DLR(root->rchild); }

return(0);

}

法二：

int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目

{

if(!T) return 0; //空树没有叶子

else if(!T->lchild&&!T->rchild) return 1; //叶子结点

else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加

上右子树的叶子数

}//LeafCount_BiTree

① 打印叶子结点值（并求总数）

思路：先建树，再从遍历过程中打印结点值并统计。

步骤1 键盘输入序列12，8，17，11，16，2，13，9，21，4，构成一棵二叉排序树。叶子

结点值应该是4，9, 13, 21, 总数应该是4.

12

7 17

2 11 16 21

4 9 13

编程： 生成二叉树排序树之后，再中序遍历排序查找结点的完整程序如下：

说明部分为：

#include

#include

typedef struct liuyu{int data;struct liuyu *lchild,*rchild;}test;

liuyu *root;

int sum=0;int m=sizeof(test);

void insert_data(int x) /*如何生成二叉排序树？参见教材P43C程序*/

{ liuyu *p,*q,*s;

s=(test*)malloc(m);

s->data=x;

s->lchild=NULL;

s->rchild=NULL;

if(!root){root=s; return;}

p=root;

while(p) /*如何接入二叉排序树的适当位置*/

{q=p;

if(p->data==x){printf("data already exist! n");return;}

else if(xdata)p=p->lchild; else p=p->rchild;

}

if(xdata)q->lchild=s;

else q->rchild=s;

}

DLR(liuyu *root) /*中序遍历 递归函数*/

{if(root!=NULL)

{if((root->lchild==NULL)&&(root->rchild==NULL)){sum++; printf("%dn",root->data);}

DLR(root->lchild);

DLR(root->rchild); }

return(0);

}

main() /*先生成二叉排序树，再调用中序遍历递归函数进行排序输出*/

{int i,x;

i=1;

root=NULL; /*千万别忘了赋初值给root!*/

do{printf("please input data%d:",i);

i++;

scanf("%d",&x); /*从键盘采集数据，以-9999表示输入结束*/

if(x==-9999){

DLR(root);

printf("nNow output count value:%dn",sum);

return(0); }

else insert_data(x);} /*调用插入数据元素的函数*/

while(x!=-9999);

return(0);}

2. 答；设计思路：只查后继链表指针，若左或右孩子的左或右指针非空，则层次数加1；否

则函数返回。

但注意，递归时应当从叶子开始向上计数，否则不易确定层数。

int depth(liuyu*root) /*统计层数*/

{int d,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;

}

p=p+1;

return(p);

}

法二：

int Get_Sub_Depth(Bitree T,int x)//求二叉树中以值为x的结点为根的子树深度

{

if(T->data==x)

{

printf("%dn",Get_Depth(T)); //找到了值为x的结点,求其深度

exit 1;

}

}

else

{

if(T->lchild) Get_Sub_Depth(T->lchild,x);

if(T->rchild) Get_Sub_Depth(T->rchild,x); //在左右子树中继续寻找

}

}//Get_Sub_Depth

int Get_Depth(Bitree T)//求子树深度的递归算法

{

if(!T) return 0;

else

{

m=Get_Depth(T->lchild);

n=Get_Depth(T->rchild);

return (m>n?m:n)+1;

}

}//Get_Depth

步骤2： 执行求深度的函数，并打印统计出来的深度值。

完整程序如下：

#include

#include

typedef struct liuyu{int data;struct liuyu *lchild,*rchild;}test;

liuyu *root;

int sum=0;int m=sizeof(test);

void insert_data(int x) /*如何生成二叉排序树？参见教材P43C程序*/

{ liuyu *p,*q,*s;

s=(test*)malloc(m);

s->data=x;

s->lchild=NULL;

s->rchild=NULL;

if(!root){root=s; return;}

p=root;

while(p) /*如何接入二叉排序树的适当位置*/

{q=p;

if(p->data==x){printf("data already exist! n");return;}

else if(xdata)p=p->lchild; else p=p->rchild;

}

if(xdata)q->lchild=s;

else q->rchild=s;

}

int depth(liuyu*root) /*统计层数*/

{int d,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;

}

p=p+1;

return(p);

}

void main() /*先生成二叉排序树，再调用深度遍历递归函数进行统计并输出

*/

{int i,x;

i=1;

root=NULL; /*千万别忘了赋初值给root!*/

do{printf("please input data%d:",i);

i++;

scanf("%d",&x); /*从键盘采集数据，以-9999表示输入结束*/

if(x==-9999){

printf("nNow output depth value=%dn", depth (root)); return; }

else insert_data(x);} /*调用插入数据元素的函数*/

while(x!=-9999);

return;}

3. 解：思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办

法。

这是一个循环算法，用while语句不断循环，直到队空之后自然退出该函数。

技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使

得它的左右孩子结点入队，……以此产生了按层次输出的效果。

level(liuyu*T)

/* liuyu *T,*p,*q[100]; 假设max已知*/

{int f,r;

f=0; r=0; /*置空队*/

r=(r+1)%max;

q[r]=T; /*根结点进队*/

while(f!=r) /*队列不空*/

{f=(f+1%max);

p=q[f]; /*出队*/

printf("%d",p->data); /*打印根结点*/

if(p->lchild){r=(r+1)%max; q[r]=p->lchild;} /*若左子树不空，则左子树进队*/

if(p->rchild){r=(r+1)%max; q[r]=p->rchild;} /*若右子树不空，则右子树进队*/

}

return(0);

}

法二：

void LayerOrder(Bitree T)//层序遍历二叉树

{

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

可以用前面的函数建树，然后调用这个函数来输出。

完整程序如下（已上机通过）

#include

#include

#define max 50

typedef struct liuyu{int data;struct liuyu *lchild,*rchild;}test;

liuyu *root,*p,*q[max];

int sum=0;int m=sizeof(test);

void insert_data(int x) /*如何生成二叉排序树？参见教材P43C程序*/

{ liuyu *p,*q,*s;

s=(test*)malloc(m);

s->data=x;

s->lchild=NULL;

s->rchild=NULL;

if(!root){root=s; return;}

p=root;

while(p) /*如何接入二叉排序树的适当位置*/

{q=p;

if(p->data==x){printf("data already exist! n");return;}

else if(xdata)p=p->lchild; else p=p->rchild;

}

if(xdata)q->lchild=s;

else q->rchild=s;

}

level(liuyu*T)

/* liuyu *T,*p,*q[100]; 假设max已知*/

{int f,r;

f=0; r=0; /*置空队*/

r=(r+1)%max;

q[r]=T; /*根结点进队*/

while(f!=r) /*队列不空*/

{f=(f+1%max);

p=q[f]; /*出队*/

printf("%d",p->data); /*打印根结点*/

if(p->lchild){r=(r+1)%max; q[r]=p->lchild;} /*若左子树不空，则左子树进队*/

if(p->rchild){r=(r+1)%max; q[r]=p->rchild;} /*若右子树不空，则右子树进队*/

}

return(0);

}

void main() /*先生成二叉排序树，再调用深度遍历递归函数进行统计并输出

*/

{int i,x;

i=1;

root=NULL; /*千万别忘了赋初值给root!*/

do{printf("please input data%d:",i);

i++;

scanf("%d",&x); /*从键盘采集数据，以-9999表示输入结束*/

if(x==-9999){

printf("nNow output data value:n", level(root)); return; }

else insert_data(x);} /*调用插入数据元素的函数*/

while(x!=-9999);

return;}

4. 答：首先，由于是完全二叉树，不必担心中途会出现孩子为null的情况。

其次分析：结点i的左孩子为2i，右孩子为2i+1;直接打印即可。

Printf(“Left_child=”, %d, v[2*i].data; “Right_child=”, %d, v[2*i+1].data;);

但其双亲是i/2，需先判断i为奇数还是偶数。若i为奇数，则应当先i-- ，然后再除以

2。

If(i/2!=0)i--;

Printf(“Parents=”, %d, v[i/2].data;);

5. 答：int IsFull_Bitree(Bitree T)//判断二叉树是否完全二叉树,是则返回1,否则返回0

{

InitQueue(Q);

flag=0;

EnQueue(Q,T); //建立工作队列

while(!QueueEmpty(Q))

{

{

DeQueue(Q,p);

if(!p) flag=1;

else if(flag) return 0;

else

{

EnQueue(Q,p->lchild);

EnQueue(Q,p->rchild); //不管孩子是否为空,都入队列

}

}//while

return 1;

}//IsFull_Bitree

分析:该问题可以通过层序遍历的方法来解决.与6.47相比,作了一个修改,不管当前结点

是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空

指针的序列.反之,则序列中会含有空指针.

6、解：方案1；哈夫曼编码

先将概率放大100倍，以方便构造哈夫曼树。

w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ……19, 21, 32

（100）

0 1

（40） （60）

0 1 0 1

19 21 32 （28）

19 21 32

（17） （11）

0 1

7 10 6 （5）

0 1 0 1

2 3

7 10 6

0 1

2 3

方案比较：

字母编号 对应编码 出现频率 字母编号 对应编码 出现频率

1 1100 0.07 1 000 0.07

2 00 0.19 2 001 0.19

3 11110 0.02 3 010 0.02

4 1110 0.06 4 011 0.06

10 0.32 5 100 0.32

5

11111 0.03 6 101 0.03

6

7 110 0.21

方案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

结论：哈夫曼编码优于等长二进制编码