二叉树练习题

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

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

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

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

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

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

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

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

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

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

二、填空

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

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

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

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

5.  二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按           次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是                    。  6. 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是         。

7.一个深度为h的二叉树最多有      结点，最少有      结点。

三、选择题

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

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

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

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

(Ａ) log2(n)   (Ｂ)  log2(n)   (Ｃ)  log2(n) +1     (Ｄ) log2(n)+1

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

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

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

4.  树是结点的有限集合，它  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： ①权               ② 度             ③ 次数              ④ 序

答案：A=           B=         C=         

四、简答题

1. 给定如图所示二叉树T，请画出与其对应的中序线索二叉树。

2.  把如图所示的树转化成二叉树，分别按先序、中序、后序遍历时得到的结点序列。

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

4.叙述二叉树的性质3，并证明

五、算法

1.写出对二叉树的先序，中序，后序遍历的算法。

2.编写求一棵二叉树叶子结点个数的算法。

3. 编写求一棵二叉树深度的算法

六．算法填空题

1.下面是对二叉树进行中序线索化，请填充落掉的语句

typedef  struct node

{   int  data;

     int lt, rt;

     struct node *lc, *rc;

} *JD;

status  midindex(JD bt)

{    p=bt ;  pr=NULL;

     if (!p) return 0;

     initstack(S);

     while (           )

      {      if (p) 

            {           push(S,p);   

p=p->lchild; }

    else 

           {          p=pop(S);        

if(p->lc= =NULL)

{                   

                     }

if(pr&&pr->rc==NULL)

{              

              }

                      pr=p;     

             ;     

}//endelse

      }//endwhile

pr->rt=1 ;

   return 1;

}