一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分）

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

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

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

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

（ × ）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。   （应当是二叉排序树的特点）

（ × ）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1）  

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

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

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

（正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。）即有后继链接的指针仅n-1个。

（ √ ）10. 〖01年计算机系研题〗具有12个结点的完全二叉树有5个度为2的结点。

最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5 

 

二、填空（每空1分，共15分）

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

 

2.  【计算机研2000】 一棵深度为6的满二叉树有 n1+n2=0+ n2= n0-1=31  个分支结点和 26-1 =32  个叶子。

注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。

 

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

（ 注：用ë log2(n) û+1= ë 8.xx û+1=9

4. 【全国专升本统考题】设一棵完全二叉树有700个结点，则共有  350  个叶子结点。

答：最快方法：用叶子数＝[n/2]＝350 

 

5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 500  个叶子结点，有  499   个度为2的结点，有   1   个结点只有非空左子树，有  0    个结点只有非空右子树。

答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。 另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0.

 

6. 【严题集6.7③】 一棵含有n个结点的k叉树，可能达到的最大深度为  n  ，最小深度为 2 。

答：当k=1(单叉树)时应该最深，深度＝n（层）；当k=n-1（n-1叉树）时应该最浅，深度＝2（层），但不包括n=0或1时的特例情况。教材答案是“完全k叉树”，未定量。)

 

7. 【96程试题1】  二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按    L R N     次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是       F E G H D C B         。 解：法1：先由已知条件画图，再后序遍历得到结果；

法2：不画图也能快速得出后序序列，只要找到根的位置特征。由前序先确定root，由中序先确定左子树。例如，前序遍历BEFCGDH中，根结点在最前面，是B；则后序遍历中B一定在最后面。

法3：递归计算。如B在前序序列中第一，中序中在中间（可知左右子树上有哪些元素），则在后序中必为最后。如法对B的左右子树同样处理，则问题得解。

 

8.【全国专升本统考题】中序遍历的递归算法平均空间复杂度为    O(n)   。

答：即递归最大嵌套层数，即栈的占用单元数。精确值应为树的深度k+1，包括叶子的空域也递归了一次。

 

9. 【计算机研2001】 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是    33   。

解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出WPL＝（4＋5＋3）×2＋（1＋2）×3=33

         (15)

(9)        (6)               （注：两个合并值先后不同会导致编码不同，即哈夫曼编码不唯一）

 4    5    3     (3)             （注：合并值应排在叶子值之后）

1        2

（注：原题为选择题：Ａ．32            Ｂ．33         Ｃ．34       Ｄ．15）

 

 

三、单项选择题（每小题1分，共11分）

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

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

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

答：以前的标答是B，因为那时树的定义是n≥1

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

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

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

 

（ C ）3. 〖01年计算机研题〗 具有n(n>0)个结点的完全二叉树的深度为         。

(Ａ) élog2(n)ù   (Ｂ) ë log2(n)û   (Ｃ) ë log2(n) û+1     (Ｄ) élog2(n)+1ù

注1：éx ù表示不小于x的最小整数；ë xû表示不大于x的最大整数，它们与[ ]含义不同！

注2：选（A）是错误的。例如当n为2的整数幂时就会少算一层。似乎ë log2(n) +1û是对的？

 

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

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

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

 

 

5. 【94程P11】  从供选择的答案中，选出应填入下面叙述   ？   内的最确切的解答，把相应编号写在答卷的对应栏内。

树是结点的有限集合，它A  根结点，记为T。其余的结点分成为m（m≥0）个  B   

的集合T1，T2，…，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。一个结点的子结点个数为该结点的  C    。

供选择的答案

A：  ①有0个或1个    ②有0个或多个      ③有且只有1个      ④有1个或1个以上 

B:   ①互不相交      ② 允许相交         ③ 允许叶结点相交    ④ 允许树枝结点相交

C： ①权            ② 维数             ③ 次数（或度）      ④ 序

答案：ABC＝1，1，3

 

6. 【95程P13】  从供选择的答案中，选出应填入下面叙述   ？   内的最确切的解答，把相应编号写在答卷的对应栏内。

二叉树 A  。在完全的二叉树中，若一个结点没有  B   ，则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的  C   ，而N的右子女是它在原树里对应结点的  D    。

供选择的答案

A： ①是特殊的树   ②不是树的特殊形式   ③是两棵树的总称   ④有是只有二个根结点的树形结构 

B:   ①左子结点   ② 右子结点  ③ 左子结点或者没有右子结点    ④ 兄弟

C～D： ①最左子结点         ② 最右子结点    ③ 最邻近的右兄弟        ④ 最邻近的左兄弟

       ⑤ 最左的兄弟     ⑥ 最右的兄弟

答案：A=           B=         C=          D＝           

答案：ABCDE＝2，1，1，3

 

 

四、简答题（每小题4分，共20分）

1. 【严题集6.2①】一棵度为2的树与一棵二叉树有何区别？

答：度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。

 

2.〖01年计算机研题〗设如下图所示的二叉树B的存储结构为二叉链表，root为根指针，结点结构为：（lchild,data,rchild）。其中lchild，rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题：

1. 对下列二叉树B，执行下列算法traversal(root)，试指出其输出结果；

2. 假定二叉树B共有n个结点，试分析算法traversal(root)的时间复杂度。（共8分）

 

 

二叉树B

 

解：这是“先根再左再根再右”，比前序遍历多打印各结点一次，输出结果为：A B C C E E B A D F F D G G

特点：①每个结点肯定都会被打印两次；②但出现的顺序不同，其规律是：凡是有左子树的结点，必间隔左子树的全部结点后再重复出现；如A，B，D等结点。反之马上就会重复出现。如C，E，F，G等结点。

时间复杂度以访问结点的次数为主，精确值为2*n，时间渐近度为O(n).

3. 〖01年计算机研题〗【严题集6.27③】给定二叉树的两种遍历序列，分别是：

前序遍历序列：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，不断递归，则所有元素都将被唯一确定，问题得解。

 

         D

         A

        C                  F

E           G

B      H           I

 

4.【计算机研2000】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。

解：要遵循中序遍历的轨迹来画出每个前驱和后继。

中序遍历序列：55  40  25  60  28  08  33  54

                         28

25 33

 

        40      60    08        54

  

55

 

 

 

五、阅读分析题（每题5分，共20分）

1. （P60 4-26）试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。

答：DLR：A B D F J G K C E H I L M

LDR:  B F J D G K A C H E L I M

LRD：J F K G D B H L M I E C A

 

 

 

 

2. （P60 4-27）把如图所示的树转化成二叉树。

答：注意全部兄弟之间都要连线（包括度为2的兄弟）,并注意原有连线结点一律归入左子树，新添连线结点一律归入右子树。

                 A

             B

      E            C

 K       F     H        D

    L      G  I

        M        J

3.【严题集6.17③】阅读下列算法，若有错，改正之。

 

 

 

4.【严题集6.21②】画出和下列二叉树相应的森林。

答：注意根右边的子树肯定是森林，

而孩子结点的右子树均为兄弟。

 

 

 

六、算法设计题（前5题中任选2题，第6题必做，每题8分，共24分）

1.【严题集6.42③】编写递归算法，计算二叉树中叶子结点的数目。

解：思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。

法一：核心部分为：

DLR(li *root)     

{if(root!=NULL)

 {if((root->lchild==NULL)&&(root->rchild==NULL)){sum++; printf("%d\n",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 <stdio.h>

#include <stdlib.h>

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

liuyu *root;

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

 

void insert_data(int x)        

{ 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(x<p->data)p=p->lchild;  else p=p->rchild;

  }

if(x<q->data)q->lchild=s;

else q->rchild=s;

}

 

DLR(liuyu *root)     

{if(root!=NULL)

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

  DLR(root->lchild);

  DLR(root->rchild); }

 return(0);

}

 main()            

{int i,x;

i=1; 

root=NULL;            

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

i++;

scanf("%d",&x);           

if(x==-9999){ 

   DLR(root);

   printf("\nNow output count value:%d\n",sum);

   return(0);  }

   else insert_data(x);}           

while(x!=-9999);        

return(0);}

 

执行结果：

 

若一开始运行就输入-9999，则无叶子输出，sum=0。

 

2.【全国专升本统考题】写出求二叉树深度的算法，先定义二叉树的抽象数据类型。   （10分）

或【严题集6.44④】编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。

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

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

int depth(li*root)     

{int 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("%d\n",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 

 

附：上机调试过程

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

 

     

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

完整程序如下：

#include <stdio.h>

#include <stdlib.h>

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

liuyu *root;

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

 

void insert_data(int x)        

{ 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(x<p->data)p=p->lchild;  else p=p->rchild;

  }

if(x<q->data)q->lchild=s;

else q->rchild=s;

}

 

int depth(liuyu*root)     

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

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

i++;

scanf("%d",&x);           

if(x==-9999){ 

     printf("\nNow output depth value=%d\n", depth (root)); return; }

   else insert_data(x);}           

while(x!=-9999);        

return;}

执行结果：

 

 

3. 【严题集6.47④】编写按层次顺序（同一层自左至右）遍历二叉树的算法。

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

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

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

技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，……以此产生了按层次输出的效果。

level(liuyu*T)

 

{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 <stdio.h>

#include <stdlib.h>

#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)        

{ 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(x<p->data)p=p->lchild;  else p=p->rchild;

  }

if(x<q->data)q->lchild=s;

else q->rchild=s;

}

 

level(liuyu*T)

 

{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;            

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

i++;

scanf("%d",&x);           

if(x==-9999){ 

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

   else insert_data(x);}           

while(x!=-9999);        

return;}

 

4. 已知一棵具有n个结点的完全二叉树被顺序存储于一维数组A中，试编写一个算法打印出编号为i的结点的双亲和所有的孩子。

答：首先，由于是完全二叉树，不必担心中途会出现孩子为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.【严题集6.49④】编写算法判别给定二叉树是否为完全二叉树。

答：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. 【严题集6.26③】假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用0～7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。

解：方案1；哈夫曼编码

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

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

（100）

（40）      （60）

19     21     32   （28）

（17） （11）

   7     10  6    （5）

                 2     3

 

 

方案比较：

 

 

 

 

 

 

 

 

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

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