第6章習(xí)題答案

1、習(xí)題61.樹(shù)與二叉樹(shù)之間有什么區(qū)別與聯(lián)系？解：樹(shù)與二叉樹(shù)邏輯上都是樹(shù)形結(jié)構(gòu)，區(qū)別有三點(diǎn)：（1）二叉樹(shù)的度至多為2，樹(shù)無(wú)此限制。（2）二叉樹(shù)有左右子樹(shù)之分，樹(shù)無(wú)此限制。（3）二叉樹(shù)允許為空，樹(shù)一般不允許為空。二叉樹(shù)不是樹(shù)的特例。2.高度為的完全二叉樹(shù)至少有多少個(gè)結(jié)點(diǎn)？至多有多少個(gè)結(jié)點(diǎn)？解：至少有個(gè)結(jié)點(diǎn)，至多有個(gè)結(jié)點(diǎn)。和結(jié)點(diǎn)數(shù)之間的關(guān)系是ëû+1。3.已知A1.n是一棵順序存儲(chǔ)的完全二叉樹(shù)，如何求出Ai和Aj的最近的共同祖先？解：根據(jù)順序存儲(chǔ)的完全二叉樹(shù)的性質(zhì)，編號(hào)為i的結(jié)點(diǎn)的雙親的編號(hào)為ëi/2û，故Ai和Aj的最近的共同祖先可如下求出：while(i/2

2、!j/2)if(i>j)i=i/2;else j=j/2;退出while后，若i/2=0，則最近共同祖先為根結(jié)點(diǎn)，否則共同祖先為i/2。4.已知A1.n是一棵順序存儲(chǔ)的完全二叉樹(shù)，求序號(hào)最小的葉子結(jié)點(diǎn)的下標(biāo)。解：根據(jù)完全二叉樹(shù)的性質(zhì)，最后一個(gè)結(jié)點(diǎn)（編號(hào)為n）的雙親結(jié)點(diǎn)的編號(hào)是ën/2û，這是最后一個(gè)分支結(jié)點(diǎn)，在它之后是第一個(gè)葉子結(jié)點(diǎn)，故序號(hào)最小的葉子結(jié)點(diǎn)的下標(biāo)是ën/2û+1。5.一棵深度為L(zhǎng)的滿k叉樹(shù)有以下性質(zhì)：第L層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹(shù)，如果按層次順序從1開(kāi)始對(duì)全部結(jié)點(diǎn)進(jìn)行編號(hào)，求：(1)各層的結(jié)點(diǎn)數(shù)是多少？

3、(2)編號(hào)為n的結(jié)點(diǎn)的雙親結(jié)點(diǎn)(若存在)的編號(hào)是多少？(3)編號(hào)為n的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)(若存在)的編號(hào)是多少？(4)編號(hào)為n的結(jié)點(diǎn)有左右兄弟結(jié)點(diǎn)的條件是什么？如果有，其右兄弟結(jié)點(diǎn)的編號(hào)是多少？解：(1)kh-1(h為層數(shù))。(2)因?yàn)樵摌?shù)上每層上均有kh-1個(gè)結(jié)點(diǎn)，從根開(kāi)始編號(hào)為1，則結(jié)點(diǎn)i的從右向左數(shù)第2個(gè)孩子的結(jié)點(diǎn)編號(hào)為ki。設(shè)n為結(jié)點(diǎn)i的子女，則關(guān)系式(i-1)*k+2ni*k+1成立，因i是整數(shù)，故結(jié)點(diǎn)n的雙親i的編號(hào)為ën/kû+1。(3)結(jié)點(diǎn)(n>1)的前一結(jié)點(diǎn)編號(hào)為n-1（其最右邊子女編號(hào)是(n-1)*k+1），故結(jié)點(diǎn)n的第i個(gè)孩子的編號(hào)是(n-1)

4、*k+1+i。(4)根據(jù)以上分析，結(jié)點(diǎn)n有右兄弟的條件是，它不僅雙親的從右邊的第一個(gè)子女，即(n-1)%k!=0，其右兄弟編號(hào)是n+1。6.試證明，在具有n(n1)個(gè)結(jié)點(diǎn)的m叉樹(shù)中，有n(m-1)+1個(gè)指針域是空的。解：具有n個(gè)結(jié)點(diǎn)的m叉樹(shù)共用n*m個(gè)指針。除根結(jié)點(diǎn)外，其余n-1個(gè)結(jié)點(diǎn)均有指針?biāo)?，故空指針?shù)為n*m-(n-1)=n*(m-1)+1。7.試找出滿足下列條件的二叉樹(shù)：(1)先序序列與后序序列相同；(2)中序序列與后序序列相同；(3)先序序列與中序序列相同；(4)中序序列與層次遍歷序列相同。解：(1)若先序序列與后序序列相同，則或?yàn)榭諛?shù)，或?yàn)橹挥懈Y(jié)點(diǎn)的二叉樹(shù)。(2)若中序序列與后

5、序序列相同，則或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有左子樹(shù)的二叉樹(shù)。(3)若先序序列與中序序列相同，則或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹(shù)的二叉樹(shù)。(4)若中序序列與層次遍歷序列相同，則或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹(shù)的二叉樹(shù)。8.設(shè)有一棵二叉樹(shù)的層次遍歷序列為ABCDEFGHIJ，中序遍歷序列為DBGEHJACIF。請(qǐng)畫出這棵二叉樹(shù)。解：按層次遍歷，第一個(gè)結(jié)點(diǎn)（樹(shù)不空）為根，該結(jié)點(diǎn)在中序序列中把序列分成左右兩部分左子樹(shù)和右子樹(shù)。若左子樹(shù)不空，層次序列中第二個(gè)結(jié)點(diǎn)為左子樹(shù)的根；若左子樹(shù)為空，則層次序列中第二個(gè)結(jié)點(diǎn)為右子樹(shù)的根。對(duì)右子樹(shù)分析類似。層次序列的特點(diǎn)是：從左到右每個(gè)結(jié)點(diǎn)或是當(dāng)前情況下子樹(shù)的

6、根或是葉子。9.用一維數(shù)組存放一棵完全二叉樹(shù)：ABCDEFGHIJKL。請(qǐng)寫出后序遍歷該二叉樹(shù)的訪問(wèn)結(jié)點(diǎn)序列。解：HIDJKEBLFGCA。10.已知一棵二叉樹(shù)的中序遍歷序列為DGBAECHIF，后序遍歷序列為：GDBEIHFCA。(1)試畫出該二叉樹(shù)；(2)試畫出該二叉樹(shù)的中序線索樹(shù)；(3)試畫出該二叉樹(shù)對(duì)應(yīng)的森林。解：（1）（2）略（3）11.設(shè)有正文AADBAACACCDACACAAD，字符集為A、B、C、D，設(shè)計(jì)一套二進(jìn)制編碼，使得上述正文的編碼最短。解：字符A、B、C、D出現(xiàn)的次數(shù)為9、1、5、3。其哈夫曼編碼如下：A：1，B：000，C：01，D：001。其哈夫曼樹(shù)為：12.假設(shè)一

7、個(gè)僅包含二元運(yùn)算符的算術(shù)表達(dá)式以鏈表形式存儲(chǔ)在二叉樹(shù)T中，寫出計(jì)算該算術(shù)表達(dá)式值的算法。解：typedef struct Node ElemType data; float val; char optr;/只取+、-、*、/ struct Node *lchild,*rchild BiNode,*BiTree;float PostEval(BiTree t)/以后序遍歷算法求以二叉樹(shù)表示的算術(shù)表達(dá)式的值 float lv,rv; if(t!=NULL) lv=PostEval(t->lchild);/ rv=PostEval(t->rchild);/ switch(t->op

8、tr) case '+': value=lv+rv;break; case '-':value=lv-rv;break; case '*':value=lv*rv;break; case '/':value=lv/rv;break; return value;13.假設(shè)二叉鏈表為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，編寫判斷給定的二叉樹(shù)是否相似的算法。所謂二叉樹(shù)t1和t2相似指的是：t1和t2都是空樹(shù)；或者t1和t2的根結(jié)點(diǎn)是相似的，以及t1的左子樹(shù)和t2的左子樹(shù)是相似的且t1的右子樹(shù)和t2的右子樹(shù)是相似的。解：int Like(BiTree t1,

9、 BiTree t2) int like1,like2; if(t1=NULL&&t2=NULL)return 1; else if(t1=NULL|t2=NULL)return 0; elselike1=Like(t1->lchild,t2->lchild);like2=Like(t1->rchild,t2->rchild);return (like1 & like2); 14.假設(shè)二叉鏈表為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，編寫遞歸算法，將二叉樹(shù)中所有結(jié)點(diǎn)的左、右子樹(shù)相互交換。解：void Exchange(BiTree &t) if(t) BiTr

10、ee s; s=t->lchild;t->lchild=t->rchild;t->rchild=s; Exchange(t->lchild);Exchange(t->rchild);15.編寫求雙親表示法表示的樹(shù)的深度的算法。解：int Depth(PTree t) int maxdepth=0,i,temp,f; for(i=0;i<t.n;i+)temp=0;f=i;while(f>-1)temp+;f=t.nodesf.parent;if(temp>maxdepth)maxdepth=temp; return maxdepth;16.

11、假設(shè)二叉鏈表為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，編寫按層次遍歷方式計(jì)算二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)的算法。解：int Level(BiTree t) int num=0; LinkQueue Q; BiTree p; if(t)InitQueue(Q);EnQueue(Q,t);while(!QueueEmpty(Q)DeQueue(Q,p);num+;if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);/while /if return num;17.編寫算法，利用葉子結(jié)點(diǎn)中的空指針域?qū)⑺腥~子結(jié)點(diǎn)鏈接為一個(gè)帶有頭

12、結(jié)點(diǎn)的雙向鏈表，算法返回頭結(jié)點(diǎn)的指針。解：BiTree head,pre;/全局變量鏈表頭指針head，prevoid CreateLeafList(BiTree t) if(t)CreateLeafList(t->lchild);/中序遍歷左子樹(shù)if(t->lchild=NULL&&t->rchild=NULL)/葉子結(jié)點(diǎn)if(head=NULL)/第一個(gè)葉子結(jié)點(diǎn)head=new BiTNode; /生成頭結(jié)點(diǎn)head->lchild=NULL; head->rchild=t;/頭結(jié)點(diǎn)的左鏈為空，右鏈指向第一個(gè)葉子結(jié)點(diǎn)t->lchild=h

13、ead;pre=t;/第一個(gè)葉子結(jié)點(diǎn)左鏈指向頭結(jié)點(diǎn)，pre指向當(dāng)前葉子結(jié)點(diǎn)elsepre->rchild=t;t->lchild=pre;pre=t; CreateLeafList(t->rchild);pre->rchild=NULL; 18.假設(shè)二叉鏈表為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，編寫算法，按照括號(hào)表示法輸出二叉樹(shù)的所有結(jié)點(diǎn)。解：其過(guò)程是：對(duì)于非空二叉樹(shù)t，先輸出其元素值，當(dāng)存在左孩子結(jié)點(diǎn)或右孩子結(jié)點(diǎn)時(shí)，輸出一個(gè)“（”符號(hào)，然后遞歸處理左子樹(shù)，輸出一個(gè)“，”符號(hào)，遞歸處理右子樹(shù)，最后輸出一個(gè)“）”符號(hào)。void DispBiTree(BiTree t) if(t)print

14、f("%c",t->data);if(t->lchild!=NULL|t->rchild!=NULL)printf("(");DispBiTree(t->lchild);if(t->rchild!=NULL) printf(",");DispBiTree(t->rchild);printf(")"); 19.假設(shè)二叉鏈表為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，編寫算法，輸出二叉樹(shù)的所有葉子結(jié)點(diǎn)。解：void DispLeaf(BiTree t) if(t) if(t->lchild=NULL&

15、amp;&t->rchild=NULL)printf("%c ",t->data); DispLeaf(t->lchild); DispLeaf(t->rchild); 20.假設(shè)二叉鏈表為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，編寫算法，輸出值為x的結(jié)點(diǎn)的所有祖先。解：int Ancestor(BiTree t,ElemType x) if(t=NULL)return 0; if(t->data=x)return 1; if(Ancestor(t->lchild,x)|Ancestor(t->rchild,x)printf("%c &

16、quot;,t->data);return 1; 21.假設(shè)二叉鏈表為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，編寫算法，輸出所有葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。解：利用后序非遞歸遍歷的特點(diǎn)，將其中訪問(wèn)結(jié)點(diǎn)改為判斷結(jié)點(diǎn)是否為葉子結(jié)點(diǎn)，若是，輸出棧中所有結(jié)點(diǎn)值void AllPathAncestor(BiTree t) BiTNode *St100; BiTNode *p; int flag,i,top=-1;/棧指針初始化 if(t)dowhile(t) /t的所有左結(jié)點(diǎn)進(jìn)棧top+;Sttop=t;t=t->lchild;p=NULL; /p指向棧頂結(jié)點(diǎn)的前一個(gè)已訪問(wèn)的結(jié)點(diǎn)flag=1; /設(shè)置t的訪問(wèn)標(biāo)記為已

17、訪問(wèn)過(guò)while(top!=-1&&flag)t=Sttop; /出棧if(t->rchild=p)if(t->lchild=NULL&&t->rchild=NULL) /若為葉子結(jié)點(diǎn)for(i=top;i>0;i-) printf("%c->",Sti->data); /輸出棧中所有結(jié)點(diǎn)printf("%cn",St0->data);top-;p=t;/p指向剛訪問(wèn)過(guò)的結(jié)點(diǎn)elset=t->rchild; /t指向右孩子結(jié)點(diǎn)flag=0; /設(shè)置未訪問(wèn)標(biāo)記while(top

18、!=-1);printf("n"); 22.編寫算法，將二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)轉(zhuǎn)化為二叉鏈表存儲(chǔ)結(jié)構(gòu)。解：typedef char ElemType;typedef struct /結(jié)點(diǎn)結(jié)構(gòu) ElemType *data;/數(shù)據(jù)元素 int n;/左右孩子指針SqBTree;BiTree Trans(SqBTree a,int i)/數(shù)據(jù)元素放在數(shù)組a的從下標(biāo)為1開(kāi)始的單元中 BiTree t; if(i>a.n)return NULL;/當(dāng)i大于a的結(jié)點(diǎn)個(gè)數(shù) if(a.datai='#')return NULL;/當(dāng)i對(duì)于的結(jié)點(diǎn)為空 t=new BiT

19、Node; t->data=a.datai; t->lchild=Trans(a,2*i); t->rchild=Trans(a,2*i+1); return t;23.寫出在中序線索二叉樹(shù)中找指定結(jié)點(diǎn)在后序下的前驅(qū)結(jié)點(diǎn)的算法。解：在后序序列中，若結(jié)點(diǎn)p有右子女，則右子女是其前驅(qū)，若無(wú)右子女而有左子女，則左子女是其前驅(qū)。若p左右子女均無(wú)，設(shè)其中序左線索指向其祖先結(jié)點(diǎn)f（p是f右子樹(shù)中按中序遍歷的第一個(gè)結(jié)點(diǎn)），若f有左子女，則其右子女是p在后序下的前驅(qū)，若f無(wú)左子女，則順其前驅(qū)找雙親的雙親，一直繼續(xù)到雙親有左子女（這時(shí)左子女是p的前驅(qū)）。還有一種情況，若p是中序遍歷的第一個(gè)結(jié)點(diǎn)

20、，p在中序和后序下均無(wú)前驅(qū)。BiThrTree InPostPre(BiThrTree t,BiThrTree p)BiThrNode *q; if(p->RTag=0)q=p->rchild;/若p有右子女，則右子女是其后序前驅(qū) else if(p->LTag=0)q=p->lchild; /若p無(wú)右子女而有左子女，則左子女是其后序前驅(qū) else if(p->lchild=NULL)q=NULL;/p是中序序列第一個(gè)結(jié)點(diǎn)，無(wú)后序前驅(qū) else /順左線索向上找p的祖先，若存在，再找祖先的左子女while(p->LTag=1&&p->l

21、child!=NULL)p=p->lchild;if(p->LTag=0)q=p->lchild; /p結(jié)點(diǎn)的祖先的左子女是其后序前驅(qū)else q=NULL; /僅右單支樹(shù)（p是葉子），已上到根結(jié)點(diǎn)，p結(jié)點(diǎn)無(wú)后序前驅(qū) return q;24.寫出按后序序列遍歷中序線索二叉樹(shù)的算法。解：BiThrTree LeftMost(BiThrTree t)/求結(jié)點(diǎn)t的最左子孫的左線索BiThrTree p=t; while(p->LTag=0)p=p->lchild; if(p->lchild!=NULL&&p->lchild!=t)return

22、(p->lchild); else return NULL;BiThrTree RightMost(BiThrTree t)/求結(jié)點(diǎn)t的最右子孫的右線索 BiThrTree p=t; while(p->RTag=0)p=p->rchild; if(p->rchild!=NULL&&p->rchild!=t)return(p->rchild); else return NULL;int ISRightChild(BiThrTree t,BiThrTree &father)/若t是father的右孩子，返回1，否則返回0 father=L

23、eftMost(t); if(father&&father->rchild=t)return 1; else return 0;void PostOrderInThr(BiThrTree t)/后序遍歷中序線索二叉樹(shù)t BiThrTree father,p=t->lchild; int flag; while(p!=t)while(p->LTag=0)p=p->lchild;/沿左分子向下if(p->RTag=0)flag=0;/左孩子為線索，右孩子為鏈，相當(dāng)從左返回，p為葉子，相當(dāng)從右返回else flag=1;while(flag=1)printf("%c",p->data); /訪問(wèn)結(jié)點(diǎn)if(ISRightChild(p,father)p=father;flag=1; /修改p指向雙親else/p是左孩子，用最右子孫的右線索找雙