數(shù)據(jù)結(jié)構(gòu)課后習(xí)題和解析

...wd......wd......wd...第六章習(xí)題1．試分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。2．對題1所得各種形態(tài)的二叉樹，分別寫出前序、中序和后序遍歷的序列。3．一棵度為k的樹中有n1個度為1的結(jié)點，n2個度為2的結(jié)點，……，nk個度為k的結(jié)點，則該樹中有多少個葉子結(jié)點并證明之。4.假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請畫出該二叉樹。5．二叉樹有50個葉子結(jié)點，則該二叉樹的總結(jié)點數(shù)至少應(yīng)有多少個6．給出滿足以下條件的所有二叉樹：①前序和后序一樣②中序和后序一樣③前序和后序一樣7．n個結(jié)點的K叉樹，假設(shè)用具有k個child域的等長鏈結(jié)點存儲樹的一個結(jié)點，則空的Child域有多少個8．畫出與以下序列對應(yīng)的樹Ｔ：樹的先根次序訪問序列為GFKDAIEBCHJ；樹的后根次序訪問序列為DIAEKFCJHBG。9．假設(shè)用于通訊的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10請為這8個字母設(shè)計哈夫曼編碼。10．二叉樹采用二叉鏈表存放,要求返回二叉樹T的后序序列中的第一個結(jié)點指針,是否可不用遞歸且不用棧來完成?請簡述原因.11.畫出和以下樹對應(yīng)的二叉樹：12．二叉樹按照二叉鏈表方式存儲，編寫算法，計算二叉樹中葉子結(jié)點的數(shù)目。13．編寫遞歸算法：對于二叉樹中每一個元素值為x的結(jié)點，刪去以它為根的子樹，并釋放相應(yīng)的空間。14．分別寫函數(shù)完成：在先序線索二叉樹T中，查找給定結(jié)點*p在先序序列中的后繼。在后序線索二叉樹T中，查找給定結(jié)點*p在后序序列中的前驅(qū)。15．分別寫出算法，實現(xiàn)在中序線索二叉樹中查找給定結(jié)點*p在中序序列中的前驅(qū)與后繼。16．編寫算法，對一棵以孩子-兄弟鏈表表示的樹統(tǒng)計其葉子的個數(shù)。17．對以孩子-兄弟鏈表表示的樹編寫計算樹的深度的算法。18．二叉樹按照二叉鏈表方式存儲，利用棧的根本操作寫出后序遍歷非遞歸的算法。19．設(shè)二叉樹按二叉鏈表存放，寫算法判別一棵二叉樹是否是一棵正則二叉樹。正則二叉樹是指：在二叉樹中不存在子樹個數(shù)為1的結(jié)點。20．計算二叉樹最大寬度的算法。二叉樹的最大寬度是指：二叉樹所有層中結(jié)點個數(shù)的最大值。21．二叉樹按照二叉鏈表方式存儲，利用棧的根本操作寫出先序遍歷非遞歸形式的算法。22.證明：給定一棵二叉樹的前序序列與中序序列，可唯一確定這棵二叉樹；給定一棵二叉樹的后序序列與中序序列，可唯一確定這棵二叉樹；23.二叉樹按照二叉鏈表方式存儲，編寫算法，計算二叉樹中葉子結(jié)點的數(shù)目。24.二叉樹按照二叉鏈表方式存儲，編寫算法，將二叉樹左右子樹進展交換。實習(xí)題1.[問題描述]建設(shè)一棵用二叉鏈表方式存儲的二叉樹，并對其進展遍歷〔先序、中序和后序〕，打印輸出遍歷結(jié)果。[根本要求]從鍵盤承受輸入先序序列，以二叉鏈表作為存儲構(gòu)造，建設(shè)二叉樹〔以先序來建設(shè)〕并對其進展遍歷〔先序、中序、后序〕，然后將遍歷結(jié)果打印輸出。要求采用遞歸和非遞歸兩種方法實現(xiàn)。[測試數(shù)據(jù)]ABCффDEфGффFффф〔其中ф表示空格字符〕輸出結(jié)果為：先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA2．二叉樹按照二叉鏈表方式存儲，編寫算法，要求實現(xiàn)二叉樹的豎向顯示〔豎向顯示就是二叉樹的按層顯示〕。3．如題1要求建設(shè)好二叉樹，按凹入表形式打印二叉樹構(gòu)造，如以以下圖所示。2.按凹入表形式打印樹形構(gòu)造，如以以下圖所示。第六章答案6．1分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。【解答】具有3個結(jié)點的樹具有3個結(jié)點的二叉樹6.3一棵度為k的樹中有n1個度為1的結(jié)點，n2個度為2的結(jié)點，……，nk個度為k的結(jié)點，則該樹中有多少個葉子結(jié)點【解答】設(shè)樹中結(jié)點總數(shù)為n,則n=n0+n1+……+nk樹中分支數(shù)目為B,則B=n1+2n2+3n3+……+knk因為除根結(jié)點外，每個結(jié)點均對應(yīng)一個進入它的分支，所以有n=B+1即n0+n1+……+nk=n1+2n2+3n3+……+knk+1由上式可得葉子結(jié)點數(shù)為：n0=n2+2n3+……+(k-1)nk+16.5二叉樹有50個葉子結(jié)點，則該二叉樹的總結(jié)點數(shù)至少應(yīng)有多少個【解答】n0表示葉子結(jié)點數(shù)，n2表示度為2的結(jié)點數(shù)，則n0=n2+1所以n2=n0–1=49，當(dāng)二叉樹中沒有度為1的結(jié)點時，總結(jié)點數(shù)n=n0+n2=996.6試分別找出滿足以下條件的所有二叉樹:(1)前序序列與中序序列一樣;(2)中序序列與后序序列一樣;(3)前序序列與后序序列一樣?！窘獯稹?/p>

(1)前序與中序一樣：空樹或缺左子樹的單支樹；

(2)中序與后序一樣：空樹或缺右子樹的單支樹；

(3)前序與后序一樣：空樹或只有根結(jié)點的二叉樹。6.9

假設(shè)通訊的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10請為這8個字母設(shè)計哈夫曼編碼?！窘獯稹繕?gòu)造哈夫曼樹如下：哈夫曼編碼為：I1：11111I5：1100I2：11110I6：10I3：1110I7：01I4：1101I8：006.11畫出如以以下圖所示樹對應(yīng)的二叉樹?！窘獯稹?.15分別寫出算法，實現(xiàn)在中序線索二叉樹T中查找給定結(jié)點*p在中序序列中的前驅(qū)與后繼。在先序線索二叉樹T中，查找給定結(jié)點*p在先序序列中的后繼。在后序線索二叉樹T中，查找給定結(jié)點*p在后序序列中的前驅(qū)?！?〕找結(jié)點的中序前驅(qū)結(jié)點BiTNode

*InPre(BiTNode

*p)/*在中序線索二叉樹中查找p的中序前驅(qū)結(jié)點，并用pre指針返回結(jié)果*/{if(p->Ltag==1)

pre=p->LChild;

/*直接利用線索*/

else

{/*在p的左子樹中查找“最右下端〞結(jié)點*/

for(q=p->LChild;q->Rtag==0;q=q->RChild);

pre=q;

}

return(pre);

}〔2〕找結(jié)點的中序后繼結(jié)點BiTNode

*InSucc(BiTNode

*p)/*在中序線索二叉樹中查找p的中序后繼結(jié)點，并用succ指針返回結(jié)果*/{if(p->Rtag==1)

succ=p->RChild;

/*直接利用線索*/

else

{/*在p的右子樹中查找“最左下端〞結(jié)點*/

for(q=p->RChild;q->Ltag==0;q=q->LChild);

succ=q;

}

return(succ);

}(3)找結(jié)點的先序后繼結(jié)點BiTNode

*PreSucc(BiTNode

*p)/*在先序線索二叉樹中查找p的先序后繼結(jié)點，并用succ指針返回結(jié)果*/{if(p->Ltag==0)

succ=p->LChild;

else

succ=p->RChild;

return(succ);

}(4)找結(jié)點的后序前驅(qū)結(jié)點BiTNode

*SuccPre(BiTNode

*p)/*在后序線索二叉樹中查找p的后序前驅(qū)結(jié)點，并用pre指針返回結(jié)果*/{if(p->Ltag==1)

pre=p->LChild;

else

pre=p->RChild;

return(pre);

}6.21二叉樹按照二叉鏈表方式存儲，利用棧的根本操作寫出先序遍歷非遞歸形式的算法?！窘獯稹縑oid

PreOrder(BiTree

root)

/*先序遍歷二叉樹的非遞歸算法*/{

InitStack(&S);

p=root;

while(p!=NULL||!IsEmpty(S))

{if(p!=NULL)

{Visit(p->data);push(&S,p);p=p->Lchild;

}else

{

Pop(&S,&p);

p=p->RChild;}}}6.24二叉樹按照二叉鏈表方式存儲，編寫算法，將二叉樹左右子樹進展交換。【解答】算法(一)

Void

exchange(BiTree

root){

p=root;

if(p->LChild!=NULL||p->RChild!=NULL)

{

temp=p->LChild;p->LChild=p->RChild;

p->RChild=temp;

exchange(p->LChild);

exchange(p->RChild);

}

}

算法(二)

Void

exchange(BiTree

root){

p=root;

if(p->LChild!=NULL||p->RChild!=NULL)

{

exchange(p->LChild);

exchange(p->RChild);

temp=p->LChild;p->LChild=p->RChild;

p->RChild=temp;

}

}

第六章習(xí)題解析1．試分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。2．對題1所得各種形態(tài)的二叉樹，分別寫出前序、中序和后序遍歷的序列。3．一棵度為k的樹中有n1個度為1的結(jié)點，n2個度為2的結(jié)點，……，nk個度為k的結(jié)點，則該樹中有多少個葉子結(jié)點[提示]：參考P.116性質(zhì)3∵n=n0+n1+……+nkB=n1+2n2+3n3+……+knkn=B+1∴

n0+n1+……+nk=n1+2n2+3n3+……+knk+1∴

n0=n2+2n3+……+(k-1)nk+14.假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請畫出該二叉樹。[提示]：參考P.148

6．二叉樹有50個葉子結(jié)點，則該二叉樹的總結(jié)點數(shù)至少應(yīng)有多少個[提示]：[方法1]〔1〕一個葉子結(jié)點，總結(jié)點數(shù)至多有多少個結(jié)論：可壓縮一度結(jié)點?！?〕滿二叉樹或完全二叉樹具有最少的一度結(jié)點〔3〕可能的最大滿二叉樹是幾層有多少葉結(jié)點如何增補25<50<26可能的最大滿二叉樹是6層有25=32個葉結(jié)點假設(shè)將其中x個變?yōu)?度結(jié)點后，總?cè)~結(jié)點數(shù)目為50則：2x+(32–x)=50得：x=18此時總結(jié)點數(shù)目=(26–1)+18×2[方法2]假設(shè)完全二叉樹的最大非葉結(jié)點編號為m，則最大葉結(jié)點編號為2m+1,(2m+1)-m=50m=49總結(jié)點數(shù)目=2m+1=99[方法3]由性質(zhì)3：n0=n2+1即：50=n2+1所以：n2=49令n1=0得：n=n0+n2=997．給出滿足以下條件的所有二叉樹：a)前序和中序一樣b)中序和后序一樣c)前序和后序一樣[提示]：去異存同。a)DLR與LDR的一樣點：DR，如果無L，則完全一樣,如果無LR，…。b)LDR與LRD的一樣點：LD，如果無R，則完全一樣。c)DLR與LRD的一樣點：D，如果無LR，則完全一樣?！踩绻，則為空樹〕7．n個結(jié)點的K叉樹，假設(shè)用具有k個child域的等長鏈結(jié)點存儲樹的一個結(jié)點，則空的Child域有多少個[提示]：參考P.1198．畫出與以下序列對應(yīng)的樹Ｔ：樹的先根次序訪問序列為GFKDAIEBCHJ；樹的后根次序訪問序列為DIAEKFCJHBG。[提示]：〔1〕先畫出對應(yīng)的二叉樹〔2〕樹的后根序列與對應(yīng)二叉樹的中序序列一樣9．假設(shè)用于通訊的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10〔1〕請為這8個字母設(shè)計哈夫曼編碼，〔2〕求平均編碼長度。10．二叉樹采用二叉鏈表存放,要求返回二叉樹T的后序序列中的第一個結(jié)點的指針,是否可不用遞歸且不用棧來完成?請簡述原因.[提示]：無右子的“左下端〞11.畫出和以下樹對應(yīng)的二叉樹：12．二叉樹按照二叉鏈表方式存儲，編寫算法，計算二叉樹中葉子結(jié)點的數(shù)目。13．編寫遞歸算法：對于二叉樹中每一個元素值為x的結(jié)點，刪去以它為根的子樹，并釋放相應(yīng)的空間。[提示]：[方法1]：〔1〕按先序查找；〔2〕超前查看子結(jié)點〔3〕按后序釋放；voidDelSubTree(BiTree

*bt,

DataTypex){if(*bt!=NULL&&(*bt)->data==x){

FreeTree(*bt);*bt=NULL;}else

DelTree(*bt,

x)voidDelTree(BiTreebt,

DataTypex){if(bt){if(bt->LChild&&bt->LChild->data==x){FreeTree(bt->LChild);bt->LChild=NULL;}if(bt->RChild&&bt->RChild->data==x){FreeTree(bt->RChild);bt->RChild=NULL;}DelTree(bt->LChild,

x);DelTree(bt->RChild,

x);}}[方法2]：〔1〕先序查找；〔2〕直接查看當(dāng)前根結(jié)點〔3〕用指針參數(shù)；[方法3]：〔1〕先序查找；〔2〕直接查看當(dāng)前根結(jié)點〔3〕通過函數(shù)值，返回刪除后結(jié)果；〔參例如程序〕14．分別寫函數(shù)完成：在先序線索二叉樹T中，查找給定結(jié)點*p在先序序列中的后繼。在后序線索二叉樹T中，查找給定結(jié)點*p在后序序列中的前驅(qū)。[提示]：〔1〕先查看線索，無線索時用下面規(guī)律：〔2〕結(jié)點*p在先序序列中的后繼為其左子或右子；〔3〕結(jié)點*p在后序序列中的前驅(qū)也是其左子或右子。15．分別寫出算法，實現(xiàn)在中序線索二叉樹中查找給定結(jié)點*p在中序序列中的前驅(qū)與后繼?！矃⒗}〕16．編寫算法，對一棵以孩子-兄弟鏈表表示的樹統(tǒng)計其葉子的個數(shù)。[提示]：〔1〕可將孩子-兄弟鏈表劃分為根、首子樹、兄弟樹，遞歸處理?！?〕可利用返回值，或全局變量。17．對以孩子-兄弟鏈表表示的樹編寫計算樹的深度的算法。18