第五章 樹和二叉樹
一、單項選擇題
1．關于二叉樹的下列說法正確的是 (1)。
(1)：A．二叉樹的度為2 B．二叉樹的度可以小于2
C．每一個結點的度都為2 D．至少有一個結點的度為
2．設深度為h(h>0)的二叉樹中只有度為0和度為2的結點，則此二叉樹中所含的結點總數至少為 （2）。
(2)A．2h B．2h-1 C．2h+1 D．h+1
3．在樹中，若結點A有4個兄弟，而且B是A的雙親，則B的度為 (3) 。
(3)：A．3 B．4 C．5 D．6
4．若一棵完全二叉樹中某結點無左孩子，則該結點一定是 (4) 。
(4)：A.度為1的結點 B．度為2的結點 C．分支結點 D．葉子結點
5．深度為k的完全二叉樹至多有 (5) 個結點，至少有 (6) 個結點。
(5)-(6)：A．2k-1-1 B．2k-1 C．2k-1 D．2k
6．前序序列為ABC的不同二叉樹有 (7) 種不同形態。
(7)：A．3 B．4 C．5 D．6
7．若二叉樹的前序序列為DABCEFG，中序序列為BACDFGE，則其后序序列為 (8) ，層次序列為 (9) 。
(8)-(9)：A．BCAGFED B．DAEBCFG C．ABCDEFG D．BCAEFGD
8．在具有200個結點的完全二叉樹中，設根結點的層次編號為1，則層次編號為60的結點，其左孩子結點的層次編號為 (10) ，右孩子結點的層次編號為 (11) ，雙親結點的層次編號為 (12)。
(10)-(12)：A．30 B．60 C．120 D．121
9．遍歷一棵具有n個結點的二叉樹，在前序序列、中序序列和后序序列中所有葉子結點的相對次序 (13) 。
(13)：A.都不相同 B．完全相同 C．前序和中序相同 D．中序與后序相同
10．在由4棵樹組成的森林中，第一、第二、第三和第四棵樹組成的結點個數分別為30，10，20，5，當把森林轉換成二叉樹后，對應的二叉樹中根結點的左子樹中結點個數為 （14） ，根結點的右子樹中結點個數為 (15) 。
(14)—(15)：A．20 B．29 C．30 D．35
11.具有n個結點(n>1)的二叉樹的前序序列和后序序列正好相反，則該二叉樹中除葉子結點外每個結點 (16) 。
(16)：A.僅有左孩子 B．僅有右孩子 C．僅有一個孩子 D．都有左、右孩子
12．判斷線索二叉樹中p結點有右孩子的條件是 (17) 。
(17)：A.p!=NULL B．p->rchild!=NULL C．p->rtag=0 D．p->rtag=1
13．將一棵樹轉換成二叉樹，樹的前根序列與其對應的二叉樹的 (18) 相等。樹的后根序列與其對應的二叉樹的 (19)相同。
(18)—(19)：A．前序序列 B．中序序列 C．后序序列 D．層次序列
14．設數據結構(D，R)，D={dl，d2，d3，d4，d5，d6}，R={<d4，d2>，<d2，d1>，<d2，d3>，<d4，d6>，<d6，d5>}，這個結構的圖形是 (20) ；用 (21) 遍歷方法可以得到序列{d1，d2，d3，d4，d5，d6}。
(20)：A．線性表 B．二叉樹C．隊列 D．棧
(21)：人前序 B．中序 C．后序 D．層次
15．對于樹中任一結點x，在前根序列中序號為pre(x)，在后根序列中序號為post(x)，若樹中結點x是結點y的祖先，下列 （22） 條件是正確的。
(22)：A.pre(x)<pre(y)且post(x)<post(y)
B．pre(x)<pre(y)且post(x)>post(y)
C. pre(x)>pre(y)且post(x)<post(y)
D．pre(x)>pre(y)且post(x)>post(y)
16．每棵樹都能惟一地轉換成對應的二叉樹，由樹轉換的二叉樹中，一個結點N的左孩子是它在原樹對應結點的 (23) ，而結點N的右孩子是它在原樹里對應結點的 (24) 。
(23)—(24)：A．最左孩子 B．最右孩子 C．右鄰兄弟 D．左鄰兄弟
17．二叉樹在線索化后，仍不能有效求解的問題是 (25) 。
(25)：A．前序線索樹中求前序直接后繼結點
B．中序線索樹中求中序直接前驅結點
C．中序線索樹中求中序直接后繼結點
D．后序線索樹中求后序直接后繼結點
18．一棵具有124個葉子結點的完全二叉樹，最多有 (26)個結點。
(26)：A．247 B．248 C．249 D．250 。
19．實現任意二叉樹的后序遍歷的非遞歸算法而不使用棧結構，最有效的存儲結構是采用 （27） 。
(27)：A. 二叉鏈表 B．孩子鏈表 C．三叉鏈表 D．順序表
二、填空題
1.樹中任意結點允許有 （1）孩子結點，除根結點外，其余結點 （2） 雙親結點。
2.若一棵樹的廣義表表示為A(B(E，F)，C(C(H，I，J，K)，L)，D(M(N)))。則該樹的度為 (3) ，樹的深度為 (4) ，樹中葉子結點個數為 (5) 。
3．若樹T中度為1、2、3、4的結點個數分別為4、3、2、2，則T中葉子結點的個數是 (6) 。
4．一棵具有n個結點的二叉樹，若它有m個葉子結點，則該二叉樹中度為1的結點個數是 (7) 。
5．深度為k(k>0)的二叉樹至多有 (8) 個結點，第i層上至多有 (9) 個結點。
6．已知二叉樹有52個葉子結點，度為1的結點個數為30則總結點個數為 (10) 。
7．已知二叉樹中有30個葉子結點，則二叉樹的總結點個數至少是 （11） 。
8．高度為6的完全二叉樹至少有 (12) 個結點。
9．一個含有68個結點的完全二叉樹，它的高度是 (13) 。
10．已知一棵完全二叉樹的第6層上有6個結點(根結點的層數為1)，則總的結點個數至少是 (14) ，其中葉子結點個數是 （15） 。
11．已知完全二叉樹第6層上有10個葉子結點，則這棵二叉樹的結點總數最多是 （16） 。
12．一棵樹轉換成二叉樹后，這棵二叉樹的根結點一定沒有 (17) 孩子，若樹中有m個分支結點，則與其對應的二叉樹中無右孩子的結點個數為 （18） 。
13．若用二叉鏈表示具有n個結點的二叉樹，則有 （19） 個空鏈域。
14．具有m個葉子結點的哈夫曼樹，共有 （20）個結點。
15．樹的后根遍歷序列與其對應的二叉樹的 （21） 遍歷序列相同。
16．線索二叉樹的左線索指向其 （22） ，右線索指向其 （23） 。
三、應用題
1．具有n個結點的滿二叉樹的葉子結點個數是多少?
2．列出前序遍歷序列是ABC的所有不同的二叉樹。
3．已知二叉樹的層次遍歷序列為ABCDEFGHIJK，中序序列為DBGEHJACIKF，請構造一棵二叉樹。
4．已知二叉樹的中序遍歷序列是ACBDGHFE，后序遍歷序列是ABDCFHEG，請構造一棵二叉樹。
5．已知二叉樹的前序、中序和后序遍歷序列如下，其中有一些看不清的字母用表示，請先填寫處的字母，再構造一棵符合條件的二叉樹，最后畫出帶頭結點的中序線索鏈表。
(1)前序遍歷序列是：BCG
(2)中序遍歷序列是：CBEAGH*
(3)后序遍歷序列是：*EDB**FA
6．將下圖所示的森林轉換成一棵二叉樹，并畫出這棵二叉樹的順序存儲結構。

7．將下圖所示的二叉樹還原成森林。

8．對于給定的一組權值{3，5，6，7，9}，請構造相應的哈夫曼樹，并計算其帶權路徑長度。
四、算法設計題
1．請設計一個算法，求以孩子兄弟鏈表表示的樹中葉子結點個數。
2．請編寫一個算法，實現將以二叉鏈表存儲的二叉樹中所有結點的左、右孩子進行交換。
3．請編寫一個算法，將以二叉鏈表存儲的二叉樹輸出其廣義表表示形式。
4．請編寫一個算法，判斷以二叉鏈表存儲的二叉樹是否為完全二叉樹。
5．假設二叉樹采用鏈接存儲方式存儲，編寫一個二叉樹先序遍歷和后序遍歷的非遞歸算法。…
6．已知一棵二叉樹用二叉鏈表存儲，t指向根結點，p指向樹中任一結點。請編寫一個非遞歸算法，實現求從根結點t到結點p之間的路徑。

參考答案

第五章
一、單項選擇題
(1)-(5)BBCDC (6)-(10)BCABC (11)—(15)DABBD (16)-(19)CCABB
(20)-(24) BBBAC (25)-(27)DBC
二、填空題
（1）有零個或多個 （2）有且僅有一個
（3）根據樹的廣義表表示，可以畫出這棵村，該樹的度為4。
（4）樹的深度為4
(5)樹中葉子結點個數為8
（6）n0=14 (7)n-2m+1 (8)2k-1 (9)2i-1 (10)133 (11)59
(12)25=32 (13)log2(n+1)=log269=7 (14) 25-1+6=37 (15) 19
(16)27-1-20=107 (17)右 （18）m+1 (19)n+1 (20) 2m-1
(21)中序 （22）直接前驅結點 （23）直接后繼結點
三、應用題
1.具有n個結點的滿二叉樹中只有度為2和度為0的結點，故n=2n0-1,n0=(n+1)/2。
5．構造一棵二叉樹應該先確定根結點，由后序序列最后一個字母A確定根結點，可將前序序列的第一個字母改為A。在中序遍歷序列中A的左子樹中含4個字母，右子樹中含3個字母，在后序遍歷序列中左子樹的后序遍歷子序列為EDB，可將左子樹的后序遍歷序列和中序遍歷序列互相補足，分別是CEDB和CBDE。由這兩個子序列可知左子樹的根結點為B，D又為以B為根結點的右子樹的根結點，E為D的右孩子，所以在前序序列中A的左子樹的前序序列為：BCDE，在根結點A的右子樹中，由后序遍歷序列可確定其根結點為F，再確定其中序序列為GHF，進一步確定其前序序列為FGH，補足*處后，三個遍歷序列為：
(1)前序遍歷序列是：ABCDEFGH
(2)中序遍歷序列是：CBDEAGHF
(3)后序遍歷序列是：CEDBHGFA
由前序遍歷序列和中序遍歷序列可構造一棵二叉樹如右圖。

四、算法設計題
1.求葉子結點個數。
算法描述如下：
int leafnum(Csnode *t,int n)
{Gsnode *p;
if(tNULL) return 0;
p=t->fc;
if(pNULL)
n++;
while§
{n=leaf(p,n);
p=p->ns;
}
return n;
}
2.交換左右孩子。算法如下：
void exchange(Btnode *t)
{Btnode *p;
if(t)
{exchange(t->lchild);
exchange(t->rchild);
if(t->lchild||t->rchild)
{p=t->lchild;
t->lchild=t->rchild;
t->rchild=p;}
}
}
3.void printbtree(Btnode *r)
{if?
{printf(“%c”,r->data);
if(r->lchild||r->rchild)
printf(“(”);
printbtree(r->lchild);
if(r->rchild)
printf(“,”);
printbtree(t->rchild);
printf(“)”);
}
}
4. #define MAX 100
int checkt(Btnode t)
{Btnode s[MAX];
int i,n=0;
for(i=0;i<MAX,i++)
s[i]=NULL;
if(t==NULL)
return 0;
i=0;
S[0]=t;
While(I<=n)
{if(!s[i])
return 0;
if(s[i]->lchild)
{n=2i+1;
s[n]=s[i]->lchild;
}
if(s[i]->rchild)
{n=2i+2;
s[n]=s[i]->rchild;
}
i++;
}
return 1;
}
5．(1)前序遍歷二叉樹的非遞歸算法的基本思想是：從二叉樹的根結點開始，沿左支一直走到沒有左孩子的結點為止，在走的過程中訪問所遇結點，并把非空右孩子進棧。當找到沒有左孩子的結點時，從棧頂退出某結點的右孩子，此時該結點的左子樹已遍歷結束，然后按上述過程遍歷該結點的右子樹，如此重復，直到二叉樹中所有結點都訪問完畢為上。算法如下：
void preorder(Btnode *t)
{ int I=0;
Btnode *p,*s[M];
P=t;
Do
{ while§
{printf(“%c\t”,p->data);
if(p->rchild!=NULL)
s[i++]=p->rchild;
p=p->lchild;
}
if(i>0)
p=s[–i];
}while(i>0||p!=NULL);
}
(2)后序遍歷二叉樹的非遞歸算法的基本思想：采用一個棧保存返回的結點，先遍歷根節點的所有結節點并入棧，出棧一個結點，然后遍歷該結點的右結點并入棧，再遍歷該右結點的所有左結點并入棧，當一個結點的左右子樹均訪問后再訪問該結點，如此這樣，直到棧為空為止。其中的難點是如何判斷一個結點t的右結點已訪問過，為此用p保存已訪問過的結點(初值為NULL)，若t->right=p成立（在后序遍歷中，t的右節點一定是在t之前訪問），說明t的左右子樹均已訪問，現在應訪問t。算法如下：
void postorder(Btree *t)
{ Btree s[maxsize];
Btree p;
int flag,top=-1;
Do
{ while(t)
{ top++;
s[top]=t;
t=t->left;
}
p=NULL;
flag=1;
while(top=-1&&flag)
{ t=s[top];
if(t->rightp)
{ printf(“%d””,t->data);
top–;
p=t;
}
else
{ t=t->right;
flag=1;
}
}
}while(top!=-1)
}
6.求二叉樹中從根結點到p結點之間路徑長度的算法描述如下：
#define MAX 100
void path(Btnode *t,Btnode *p)
{ Btnode *s[MAX],*q=t;
int b[MAX],top=-1;
do {
while(q)
{s[++top]=q;
b[top]=0;
q=q->lchild;
}
if(top->-1&&b[top]1)
{q=s[top];
if(qp)
{printf(“根結點到q結點的路徑是：”)；
for(I=0;I<=top;I++)
printf(“%c”,s[I]->data);
return;
}
else top–;
}
if(top>-1)
{ p=s[top]->rchild;
b[top]=1;
}
}while(top>0);
}
7.判斷以二叉鏈表存儲的二叉樹是否為完全二叉樹的算法描述如下：
#define MAX 100
void checkt(BTnode *t)
{ Btnode *s[MAX];
int i,n=0;
for(i=0;i<MAX;i++)
s[i]=MAX;
if(tNULL)
return 0;
s[0]=t;
while(i<=n)
{ if(!s[i])
return 0;
if(s[i]->lchild)
{ n=2i+1;
s[n]=s[i]->lchild;
}
if(s[i]->rchild)
{ n=2i+2;
s[n]=s[i]->rchild;
}
i++;
}
return 1;
}