第六章 树和二叉树
一．选择题
1．如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（  ）
A. 栈            B. 队列       C. 树             D. 图
2．设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1  则T中的叶子数为（  ）
A．5            B．6          C．7           D．8
3．已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（  ）
A. 0            B. 1          C. 48          D. 49
4．树的先根序列等同于与该树对应的二叉树的（  ）
A．先序序列     B．中序序列   C．后序序列     D．层序序列
5. 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为（  ）
A．n-1          B．n          C．n+l         D．2n
6. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（  ）
A．m-n          B．m-n-1      C．n+1         D．条件不足，无法确定
7. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，则T中的叶子数为（  ）
A．5            B．6          C．7           D．8
8．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（  ）
A．M1           B．M1+M2       C．M3         D．M2+M3
9．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）
A． 250         B． 500        C．254        D．505      E．以上答案都不对   
10．有n个叶子的哈夫曼树的结点总数为（  ）
A．不确定       B．2n          C．2n+1       D．2n-1
11．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有(  )结点
A．2h           B．2h-1        C．2h+1       D．h+1
12．将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（  ）
A．4            B．5           C．6          D．7
13．若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（  ）
A．n-1     B．n/m-1       C．(n-1)/(m-1)     D． n/(m-1)-1   E．(n+1)/(m+1)-1
14．若下面几个符号串编码集合中，不是前缀编码的是（  ）。
A．{0,10,110,1111}             B．{11,10,001,101,0001}   
C．{00,010,0110,1000}          D．{b,c,aa,ac,aba,abb,abc}
15．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（  ）
A．CABDEFG      B．ABCDEFG     C．DACEFBG    D．ADCFEG
16．线索二叉树是一种（  ）结构。
A． 逻辑    B． 逻辑和存储   C． 物理     D．线性
17．引入二叉线索树的目的是（  ）
A．加快查找结点的前驱或后继的速度   B．为了能在二叉树中方便的进行插入与删除
C．为了能方便的找到双亲             D．使二叉树的遍历结果唯一
18．n个结点的线索二叉树上含有的线索数为（  ）
A．2n      B．n－l       C．n＋l         D．n
19．若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为(  )
A.X的双亲                   B.X的右子树中最左的结点  
C.X的左子树中最右结点       D.X的左子树中最右叶结点
20．某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（  ）的二叉树
A．空或只有一个结点          B．任一结点无左子树   
C．高度等于其结点数          D．任一结点无右子树
二．填空题
1．假定一棵树的嵌套括号表示法为 A （ B （ E ）， C （ F （ H ， I ， J ）， G ）， D ），则该树的度为______，树的深度为_____，终端点的个数为____，但分支结点的个数为_____，双分支结点为_____，三分支结点的个数为______， C 结点的双亲结点为_________，其孩子结点为__________和为_________结点。
2．一棵深度为 K 的满二叉树结点总数为___________ ，一棵深度为 K 的完全二叉树的结点总数的最小值为________，最大值为____________。
3．由三个结点构成的二叉树，共有_____________种不同的形态。
4．具有100个叶子结点的完全二叉树的深度为   
5．高为h（h>0）的满二叉树对应森林的由    棵树构成。
三．已知一个二叉树的中序序列为CBEDAHGIJF,后序序列为CEDBHJIGFA。
1．画出该二叉树。
2．画出该二叉树的先序线索二叉树。
四．试找出分别满足下列条件的所有二叉树：
1．先序序列和中序序列相同。
2．中序序列和后序序列相同。
3．先序序列和后序序列相同。
五．设二叉树用二叉链表表示，设计算法求二叉树的高度。
六．设用于通信的电文由字符集｛a,b,c,d,e,f,g｝中的字母构成，它们在电文中出现的频率分别为｛0.31,0.16,0.10,0.08,0.11,0.20,0.04｝，回答下列问题：
⑴为这7个字母设计哈夫曼编码
⑵若对这7个字母进行等长编码，至少需要几位二进制数？
七．设计算法以输出二叉树中先序序列的前k（k>0）个结点的值。
八．编写算法，对一棵二叉树统计叶子的个数





参 考 答 案
树和二叉树
一．选择题
1．C  2．D  3．D  4．A  5．C  6．A  7．D  8．D  9．E  10．D  11．B  12．C
13．C   14．B  15．B  16．C  17．A  18．C  19．C  20．C
二．填空题
1．3  4  6  4  1  2  A  F  G
2．2K-1  2K-1  2K-1
3．5
4．8
5．h
三．
1．二叉树：         
 
2．先序线索二叉树
四．
①空二叉树，或任意结点无左子树的二叉树。                  
②空二叉树，或任意结点无右子树的二叉树。                  
③空二叉树，或只含根结点的二叉树。                        
五．
int Depth(BiTree t)
{   
if(t==NULL)
       d=0；
    else
    {
dl=Depth(t->lchild);
      dr=Depth(t->rchild);
      d=1+(dl>dr?dl:dr);   
}
   return d;
}
六．
（1）a:11    b:101    c:010    d:1001     e:011   f:00     g:1000
（2）3位
七．
void  preintraverse(BiTree T, int &n，int k)
{  
if(T!=NULL)
{
n++;
if(n<=k)
{
cout<<T->data;
intraverse(T->lchild,n,k);
intraverse(T->rchild,n,k);
}
}
}
八、
int leaf（BiTree T）
  ｛
if (T==NULL) return 0;
if (T->lchild==null&&T->rchile==null) return 1;
return(leaf(T->lchild)+leaf(T->rchild));
}