第6章習(xí)題答案

1、習(xí)題61.樹與二叉樹之間有什么區(qū)別與聯(lián)系？解：樹與二叉樹邏輯上都是樹形結(jié)構(gòu)，區(qū)別有三點：（1）二叉樹的度至多為2，樹無此限制。（2）二叉樹有左右子樹之分，樹無此限制。（3）二叉樹允許為空，樹一般不允許為空。二叉樹不是樹的特例。2.高度為的完全二叉樹至少有多少個結(jié)點？至多有多少個結(jié)點？解：至少有個結(jié)點，至多有個結(jié)點。和結(jié)點數(shù)之間的關(guān)系是ëû+1。3.已知A1.n是一棵順序存儲的完全二叉樹，如何求出Ai和Aj的最近的共同祖先？解：根據(jù)順序存儲的完全二叉樹的性質(zhì)，編號為i的結(jié)點的雙親的編號為ë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é)點，否則共同祖先為i/2。4.已知A1.n是一棵順序存儲的完全二叉樹，求序號最小的葉子結(jié)點的下標。解：根據(jù)完全二叉樹的性質(zhì)，最后一個結(jié)點（編號為n）的雙親結(jié)點的編號是ën/2û，這是最后一個分支結(jié)點，在它之后是第一個葉子結(jié)點，故序號最小的葉子結(jié)點的下標是ën/2û+1。5.一棵深度為L的滿k叉樹有以下性質(zhì)：第L層上的結(jié)點都是葉子結(jié)點，其余各層上每個結(jié)點都有k棵非空子樹，如果按層次順序從1開始對全部結(jié)點進行編號，求：(1)各層的結(jié)點數(shù)是多少？

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

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

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

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

7、個僅包含二元運算符的算術(shù)表達式以鏈表形式存儲在二叉樹T中，寫出計算該算術(shù)表達式值的算法。解：typedef struct Node ElemType data; float val; char optr;/只取+、-、*、/ struct Node *lchild,*rchild BiNode,*BiTree;float PostEval(BiTree t)/以后序遍歷算法求以二叉樹表示的算術(shù)表達式的值 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è)二叉鏈表為二叉樹的存儲結(jié)構(gòu)，編寫判斷給定的二叉樹是否相似的算法。所謂二叉樹t1和t2相似指的是：t1和t2都是空樹；或者t1和t2的根結(jié)點是相似的，以及t1的左子樹和t2的左子樹是相似的且t1的右子樹和t2的右子樹是相似的。解：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è)二叉鏈表為二叉樹的存儲結(jié)構(gòu)，編寫遞歸算法，將二叉樹中所有結(jié)點的左、右子樹相互交換。解：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.編寫求雙親表示法表示的樹的深度的算法。解：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è)二叉鏈表為二叉樹的存儲結(jié)構(gòu)，編寫按層次遍歷方式計算二叉樹結(jié)點個數(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é)點中的空指針域?qū)⑺腥~子結(jié)點鏈接為一個帶有頭

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

13、ead;pre=t;/第一個葉子結(jié)點左鏈指向頭結(jié)點，pre指向當(dāng)前葉子結(jié)點elsepre->rchild=t;t->lchild=pre;pre=t; CreateLeafList(t->rchild);pre->rchild=NULL; 18.假設(shè)二叉鏈表為二叉樹的存儲結(jié)構(gòu)，編寫算法，按照括號表示法輸出二叉樹的所有結(jié)點。解：其過程是：對于非空二叉樹t，先輸出其元素值，當(dāng)存在左孩子結(jié)點或右孩子結(jié)點時，輸出一個“（”符號，然后遞歸處理左子樹，輸出一個“，”符號，遞歸處理右子樹，最后輸出一個“）”符號。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è)二叉鏈表為二叉樹的存儲結(jié)構(gòu)，編寫算法，輸出二叉樹的所有葉子結(jié)點。解：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è)二叉鏈表為二叉樹的存儲結(jié)構(gòu)，編寫算法，輸出值為x的結(jié)點的所有祖先。解：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è)二叉鏈表為二叉樹的存儲結(jié)構(gòu)，編寫算法，輸出所有葉子結(jié)點到根結(jié)點的路徑。解：利用后序非遞歸遍歷的特點，將其中訪問結(jié)點改為判斷結(jié)點是否為葉子結(jié)點，若是，輸出棧中所有結(jié)點值void AllPathAncestor(BiTree t) BiTNode *St100; BiTNode *p; int flag,i,top=-1;/棧指針初始化 if(t)dowhile(t) /t的所有左結(jié)點進棧top+;Sttop=t;t=t->lchild;p=NULL; /p指向棧頂結(jié)點的前一個已訪問的結(jié)點flag=1; /設(shè)置t的訪問標記為已

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

18、!=-1);printf("n"); 22.編寫算法，將二叉樹的順序存儲結(jié)構(gòu)轉(zhuǎn)化為二叉鏈表存儲結(jié)構(gòu)。解：typedef char ElemType;typedef struct /結(jié)點結(jié)構(gòu) ElemType *data;/數(shù)據(jù)元素 int n;/左右孩子指針SqBTree;BiTree Trans(SqBTree a,int i)/數(shù)據(jù)元素放在數(shù)組a的從下標為1開始的單元中 BiTree t; if(i>a.n)return NULL;/當(dāng)i大于a的結(jié)點個數(shù) if(a.datai='#')return NULL;/當(dāng)i對于的結(jié)點為空 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.寫出在中序線索二叉樹中找指定結(jié)點在后序下的前驅(qū)結(jié)點的算法。解：在后序序列中，若結(jié)點p有右子女，則右子女是其前驅(qū)，若無右子女而有左子女，則左子女是其前驅(qū)。若p左右子女均無，設(shè)其中序左線索指向其祖先結(jié)點f（p是f右子樹中按中序遍歷的第一個結(jié)點），若f有左子女，則其右子女是p在后序下的前驅(qū)，若f無左子女，則順其前驅(qū)找雙親的雙親，一直繼續(xù)到雙親有左子女（這時左子女是p的前驅(qū)）。還有一種情況，若p是中序遍歷的第一個結(jié)點

20、，p在中序和后序下均無前驅(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無右子女而有左子女，則左子女是其后序前驅(qū) else if(p->lchild=NULL)q=NULL;/p是中序序列第一個結(jié)點，無后序前驅(qū) else /順左線索向上找p的祖先，若存在，再找祖先的左子女while(p->LTag=1&&p->l

21、child!=NULL)p=p->lchild;if(p->LTag=0)q=p->lchild; /p結(jié)點的祖先的左子女是其后序前驅(qū)else q=NULL; /僅右單支樹（p是葉子），已上到根結(jié)點，p結(jié)點無后序前驅(qū) return q;24.寫出按后序序列遍歷中序線索二叉樹的算法。解：BiThrTree LeftMost(BiThrTree t)/求結(jié)點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é)點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)/后序遍歷中序線索二叉樹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); /訪問結(jié)點if(ISRightChild(p,father)p=father;flag=1; /修改p指向雙親else/p是左孩子，用最右子孫的右線索找雙