版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、第六章習(xí)題1試分別畫出具有3個(gè)結(jié)點(diǎn)的樹和3個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。2對(duì)題1所得各種形態(tài)的二叉樹,分別寫出前序、中序和后序遍歷的序列。3已知一棵度為k的樹中有n1個(gè)度為1的結(jié)點(diǎn),n2個(gè)度為2的結(jié)點(diǎn),nk個(gè)度為k的結(jié)點(diǎn),則該樹中有多少個(gè)葉子結(jié)點(diǎn)并證明之。4.假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ,中序序列為ABCDEFGHIJK,請(qǐng)畫出該二叉樹。5已知二叉樹有50個(gè)葉子結(jié)點(diǎn),則該二叉樹的總結(jié)點(diǎn)數(shù)至少應(yīng)有多少個(gè)?6給出滿足下列條件的所有二叉樹: 前序和后序相同 中序和后序相同 &
2、#160; 前序和后序相同7 n個(gè)結(jié)點(diǎn)的K叉樹,若用具有k個(gè)child域的等長鏈結(jié)點(diǎn)存儲(chǔ)樹的一個(gè)結(jié)點(diǎn),則空的Child域有多少個(gè)?8畫出與下列已知序列對(duì)應(yīng)的樹:樹的先根次序訪問序列為GFKDAIEBCHJ;樹的后根次序訪問序列為DIAEKFCJHBG。9假設(shè)用于通訊的電文僅由8個(gè)字母組成,字母在電文中出現(xiàn)的頻率分別為:0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10請(qǐng)為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。10已知二叉樹采用二叉鏈表存放,要求返回二叉樹T的后序序列中的第一個(gè)結(jié)點(diǎn)指針,是否可不用遞歸且不用棧來完成?請(qǐng)簡述原因.11. 畫出和下列樹對(duì)應(yīng)的二
3、叉樹:12已知二叉樹按照二叉鏈表方式存儲(chǔ),編寫算法,計(jì)算二叉樹中葉子結(jié)點(diǎn)的數(shù)目。13編寫遞歸算法:對(duì)于二叉樹中每一個(gè)元素值為x的結(jié)點(diǎn),刪去以它為根的子樹,并釋放相應(yīng)的空間。14分別寫函數(shù)完成:在先序線索二叉樹T中,查找給定結(jié)點(diǎn)*p在先序序列中的后繼。在后序線索二叉樹T中,查找給定結(jié)點(diǎn)*p在后序序列中的前驅(qū)。15分別寫出算法,實(shí)現(xiàn)在中序線索二叉樹中查找給定結(jié)點(diǎn)*p在中序序列中的前驅(qū)與后繼。16編寫算法,對(duì)一棵以孩子-兄弟鏈表表示的樹統(tǒng)計(jì)其葉子的個(gè)數(shù)。17對(duì)以孩子-兄弟鏈表表示的樹編寫計(jì)算樹的深度的算法。18已知二叉樹按照二叉鏈表方式存儲(chǔ),利用棧的基本操作寫出后序遍歷非遞歸的算法。 19設(shè)二叉樹按
4、二叉鏈表存放,寫算法判別一棵二叉樹是否是一棵正則二叉樹。正則二叉樹是指:在二叉樹中不存在子樹個(gè)數(shù)為1的結(jié)點(diǎn)。20計(jì)算二叉樹最大寬度的算法。二叉樹的最大寬度是指:二叉樹所有層中結(jié)點(diǎn)個(gè)數(shù)的最大值。21已知二叉樹按照二叉鏈表方式存儲(chǔ),利用棧的基本操作寫出先序遍歷非遞歸形式的算法。22. 證明:給定一棵二叉樹的前序序列與中序序列,可唯一確定這棵二叉樹;給定一棵二叉樹的后序序列與中序序列,可唯一確定這棵二叉樹;23. 二叉樹按照二叉鏈表方式存儲(chǔ),編寫算法,計(jì)算二叉樹中葉子結(jié)點(diǎn)的數(shù)目。24. 二叉樹按照二叉鏈表方式存儲(chǔ),編寫算法,將二叉樹左右子樹進(jìn)行交換。 實(shí)習(xí)題1.
5、160; 問題描述 建立一棵用二叉鏈表方式存儲(chǔ)的二叉樹,并對(duì)其進(jìn)行遍歷(先序、中序和后序),打印輸出遍歷結(jié)果?;疽?從鍵盤接受輸入先序序列,以二叉鏈表作為存儲(chǔ)結(jié)構(gòu),建立二叉樹(以先序來建立)并對(duì)其進(jìn)行遍歷(先序、中序、后序),然后將遍歷結(jié)果打印輸出。要求采用遞歸和非遞歸兩種方法實(shí)現(xiàn)。測試數(shù)據(jù) ABCDEGF(其中表示空格字符) 輸出結(jié)果為: 先序:ABCDEGF
6、160; 中序:CBEGDFA 后序:CGBFDBA2已知二叉樹按照二叉鏈表方式存儲(chǔ),編寫算法,要求實(shí)現(xiàn)二叉樹的豎向顯示(豎向顯示就是二叉樹的按
7、層顯示)。3如題1要求建立好二叉樹,按凹入表形式打印二叉樹結(jié)構(gòu),如下圖所示。2. 按凹入表形式打印樹形結(jié)構(gòu),如下圖所示。 第六章答案 6 1分別畫出具有3個(gè)結(jié)點(diǎn)的樹和3個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)?!窘獯稹烤哂?個(gè)結(jié)點(diǎn)的樹
8、0; 具有3個(gè)結(jié)點(diǎn)的二叉樹 6.3已知一棵度為k的樹中有n1個(gè)度為1的結(jié)點(diǎn),n2個(gè)度為2的結(jié)點(diǎn),nk個(gè)度為k的結(jié)點(diǎn),則該樹中有多少個(gè)葉子結(jié)點(diǎn)?【解答】設(shè)樹中結(jié)點(diǎn)總數(shù)為n,則n=n0 + n1 + + nk樹中分支數(shù)目為B,則B=n1 + 2n2 + 3n3 + + knk因?yàn)槌Y(jié)點(diǎn)外,每個(gè)結(jié)點(diǎn)均對(duì)應(yīng)一個(gè)進(jìn)入它的分支,所以有n= B + 1即n0 + n1 + + nk = n1 + 2n2 + 3n3 + + knk + 1由上式可得葉子結(jié)點(diǎn)數(shù)為:n0 = n2 + 2n3 + + (
9、k-1)nk + 16.5已知二叉樹有50個(gè)葉子結(jié)點(diǎn),則該二叉樹的總結(jié)點(diǎn)數(shù)至少應(yīng)有多少個(gè)?【解答】n0表示葉子結(jié)點(diǎn)數(shù),n2表示度為2的結(jié)點(diǎn)數(shù),則n0 = n2+1 所以n2= n0 1=49,當(dāng)二叉樹中沒有度為1的結(jié)點(diǎn)時(shí),總結(jié)點(diǎn)數(shù)n=n0+n2=99 6.6 試分別找出滿足以下條件的所有二叉樹:(1) 前序序列與中序序列相同;(2) 中序序列與后序序列相同;(3) 前序序列與后序序列相同?!窘獯稹?#160; (1) 前序與中序相同:空樹或缺左子樹的單支樹;
10、60; (2) 中序與后序相同:空樹或缺右子樹的單支樹; (3) 前序與后序相同:空樹或只有根結(jié)點(diǎn)的二叉樹。6.9 假設(shè)通訊的電文僅由8個(gè)字母組成,字母在電文中出現(xiàn)的頻率分別為:0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10請(qǐng)為這8個(gè)字母設(shè)計(jì)哈夫曼編碼?!窘獯稹?#160; 構(gòu)造哈夫曼樹如下: 哈夫曼編碼為:I1:11111
11、160; I5:1100 I2:11110 I6: 10I3:1110 I7: 01 I4:1101
12、0; I8: 00 6.11畫出如下圖所示樹對(duì)應(yīng)的二叉樹。【解答】 6.15分別寫出算法,實(shí)現(xiàn)在中序線索二叉樹T中查找給定結(jié)點(diǎn)*p在中序序列中的前驅(qū)與后繼。在先序線索二叉樹T中,查找給定結(jié)點(diǎn)*p在先序序列中的后繼。在后序線索二叉樹T中,查找給定結(jié)點(diǎn)*p在后序序列中的前驅(qū)。 (1)找結(jié)點(diǎn)的中序前驅(qū)結(jié)點(diǎn)BiTNode *InPre (BiTNode *p)/*在中序線索二叉樹中查找p的中序前驅(qū)結(jié)點(diǎn),并用pre指針返回結(jié)果*/ if (p->Ltag= =1) pre
13、= p->LChild; /*直接利用線索*/ else /*在p的左子樹中查找“最右下端”結(jié)點(diǎn)*/ for ( q=p->LChild; q->Rtag= =0; q=q->RChild); pre = q; return (pre); (2)找結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)BiTNode *InSucc (BiTNode
14、; *p)/*在中序線索二叉樹中查找p的中序后繼結(jié)點(diǎn),并用succ指針返回結(jié)果*/ if (p->Rtag= =1) succ = p->RChild; /*直接利用線索*/ else /*在p的右子樹中查找“最左下端”結(jié)點(diǎn)*/ for ( q=p->RChild; q->Ltag= =0; q=q->LChild); succ= q; r
15、eturn (succ); (3) 找結(jié)點(diǎn)的先序后繼結(jié)點(diǎn)BiTNode *PreSucc (BiTNode *p)/*在先序線索二叉樹中查找p的先序后繼結(jié)點(diǎn),并用succ指針返回結(jié)果*/ if (p->Ltag= =0) succ = p->LChild; else succ= p->RChild; return (succ); (4) 找結(jié)點(diǎn)的后序前驅(qū)結(jié)點(diǎn)BiTNode *SuccPre (BiTNode
16、60; *p)/*在后序線索二叉樹中查找p的后序前驅(qū)結(jié)點(diǎn),并用pre指針返回結(jié)果*/ if (p->Ltag= =1) pre = p->LChild; else pre= p->RChild; return (pre); 6.21已知二叉樹按照二叉鏈表方式存儲(chǔ),利用棧的基本操作寫出先序遍歷非遞歸形式的算法?!窘獯稹縑oid PreOrder(BiTree root) /*先序遍歷二叉樹的非遞歸算法*/
17、; 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已知二叉樹按照二叉鏈表方式存儲(chǔ),編寫算法,將二叉樹左右
18、子樹進(jìn)行交換?!窘獯稹?#160; 算法(一) Void exchange ( BiTree root ) p=root; if ( p->LChild != NULL | p->RChild != NULL ) &
19、#160; temp = p->LChild;p->LChild = p->RChild; p->RChild = temp;
20、60; exchange ( p->LChild ); exchange ( p->RChild );
21、60; 算法(二) Void exchange ( BiTree root ) p=root;
22、0; if ( p->LChild != NULL | p->RChild != NULL ) exchange ( p->LChild );
23、60; exchange ( p->RChild ); temp = p->LChild;p->LChild = p->RChild;
24、; p->RChild = temp; 第六章 習(xí)題解析1試分別畫出具有3個(gè)結(jié)點(diǎn)的樹和3個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。2對(duì)題1所得各種形態(tài)的二叉樹,分別寫出前序、中序和后序遍歷的序列。3已知一棵度為k的樹中有n1個(gè)度為1的結(jié)點(diǎn),n2個(gè)度為2
25、的結(jié)點(diǎn),nk個(gè)度為k的結(jié)點(diǎn),則該樹中有多少個(gè)葉子結(jié)點(diǎn)?提示:參考 P.116 性質(zhì)3n=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,請(qǐng)畫出該二叉樹。提示:參考 P.148 6 已知二叉樹有50個(gè)葉子結(jié)點(diǎn),則該二
26、叉樹的總結(jié)點(diǎn)數(shù)至少應(yīng)有多少個(gè)?提示:方法1 (1)一個(gè)葉子結(jié)點(diǎn),總結(jié)點(diǎn)數(shù)至多有多少個(gè)?結(jié)論:可壓縮一度結(jié)點(diǎn)。(2)滿二叉樹或完全二叉樹具有最少的一度結(jié)點(diǎn)(3)可能的最大滿二叉樹是幾層?有多少葉結(jié)點(diǎn)?如何增補(bǔ)?25<50<26可能的最大滿二叉樹是6層有 25 = 32個(gè)葉結(jié)點(diǎn)假設(shè)將其中x個(gè)變?yōu)?度結(jié)點(diǎn)后,總?cè)~結(jié)點(diǎn)數(shù)目為50則:2x + (32 x) = 50得:x = 18此時(shí)總結(jié)點(diǎn)數(shù)目= ( 26 1) + 18×2方法2假設(shè)完全二叉樹的最大非葉結(jié)點(diǎn)編號(hào)為m,則最大葉結(jié)點(diǎn)編號(hào)為2m+1,(2m+1)-m=50m=49總結(jié)點(diǎn)數(shù)
27、目=2m+1=99方法3由性質(zhì)3:n0=n2+1即:50=n2+1所以:n2=49令n1=0得:n= n0 + n2=997 給出滿足下列條件的所有二叉樹:a) 前序和中序相同b) 中序和后序相同c) 前序和后序相同提示:去異存同。a) D L R 與L D R 的相同點(diǎn):D R,如果無 L,則完全相同, 如果無 LR,。b) L D R 與L
28、R D 的相同點(diǎn):L D,如果無 R,則完全相同。c) D L R 與L R D 的相同點(diǎn):D,如果無 L R,則完全相同。(如果去D,則為空樹)7 n個(gè)結(jié)點(diǎn)的K叉樹,若用具有k個(gè)child域的等長鏈結(jié)點(diǎn)存儲(chǔ)樹的一個(gè)結(jié)點(diǎn),則空的Child域有多少個(gè)?提示:參考 P.119 8畫出與下列已知序列對(duì)應(yīng)的樹:樹的先根次序訪問序列為GFKDAIEBCHJ;樹的后根次序訪問序列為DIAEKFCJHBG。提示:(1)先畫出對(duì)應(yīng)的二叉樹(2)樹的后根序列與對(duì)應(yīng)二叉樹的中序序列相同9假設(shè)用于通訊的電文僅由8個(gè)字母組成,字母在電文中出現(xiàn)的頻率分別為:0.07,0.19,0.02
29、,0.06,0.32,0.03,0.21,0.10(1)請(qǐng)為這8個(gè)字母設(shè)計(jì)哈夫曼編碼,(2)求平均編碼長度。10已知二叉樹采用二叉鏈表存放,要求返回二叉樹T的后序序列中的第一個(gè)結(jié)點(diǎn)的指針,是否可不用遞歸且不用棧來完成?請(qǐng)簡述原因.提示:無右子的“左下端” 11. 畫出和下列樹對(duì)應(yīng)的二叉樹:12已知二叉樹按照二叉鏈表方式存儲(chǔ),編寫算法,計(jì)算二叉樹中葉子結(jié)點(diǎn)的數(shù)目。13編寫遞歸算法:對(duì)于二叉樹中每一個(gè)元素值為x的結(jié)點(diǎn),刪去以它為根的子樹,并釋放相應(yīng)的空間。提示:方法1:(1)按先序查找;(2)超前查看子結(jié)點(diǎn)(3)按后序釋放;void DelSubTree(BiTree *bt
30、, DataType x) if ( *bt != NULL && (*bt) ->data=x ) FreeTree(*bt);*bt =NULL;else DelTree( *bt, x) void DelTree(BiTree bt, DataType x) if ( bt ) if (bt->LChild && bt->LChild->data=x) FreeTree(bt->LChild); bt->LChi
31、ld=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é)點(diǎn)(3)用指針參數(shù);方法3:(1)先序查找;(2)直接查看當(dāng)前根結(jié)點(diǎn)(3)通過函數(shù)值,返回刪除后結(jié)果;(參示例程序)14分別寫
32、函數(shù)完成:在先序線索二叉樹T中,查找給定結(jié)點(diǎn)*p在先序序列中的后繼。在后序線索二叉樹T中,查找給定結(jié)點(diǎn)*p在后序序列中的前驅(qū)。提示:(1)先查看線索,無線索時(shí)用下面規(guī)律:(2)結(jié)點(diǎn)*p在先序序列中的后繼為其左子或右子;(3)結(jié)點(diǎn)*p在后序序列中的前驅(qū)也是其左子或右子。15分別寫出算法,實(shí)現(xiàn)在中序線索二叉樹中查找給定結(jié)點(diǎn)*p在中序序列中的前驅(qū)與后繼。(參例題) 16編寫算法,對(duì)一棵以孩子-兄弟鏈表表示的樹統(tǒng)計(jì)其葉子的個(gè)數(shù)。提示:(1)可將孩子-兄弟鏈表劃分為根、首子樹、兄弟樹,遞歸處理。(2)可利用返回值,或全局變量。 17對(duì)以孩子-兄弟鏈表表示的樹編寫計(jì)算樹的深度的算法。18已知二叉樹按照二叉鏈表方式存儲(chǔ),利用棧的基本操作寫出后序遍歷非遞歸的算法。 (參課本) 19設(shè)二叉樹按二叉鏈表存放,寫算法判別一棵二叉樹是否是一棵正則二叉樹。正則二叉樹是指:在
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 鐵路供電系統(tǒng)設(shè)備運(yùn)行與檢修考核試卷
- 灌溉設(shè)備與水管理機(jī)械考核試卷
- 寵物飼養(yǎng)員寵物飼養(yǎng)場所突發(fā)事件應(yīng)急預(yù)案考核試卷
- 稻谷種植農(nóng)業(yè)產(chǎn)業(yè)鏈協(xié)同創(chuàng)新考核試卷
- 蘇教版小學(xué)數(shù)學(xué)新教材解讀會(huì)
- 我在北師大高一英語教學(xué)中的成長
- 蘇教版小學(xué)語文六下第七單元練習(xí)題及解析
- 一年級(jí)數(shù)學(xué)下冊(cè)玉米收集的發(fā)現(xiàn)
- 七年級(jí)下冊(cè)地理人教版教案一本通
- 蘇教版小學(xué)語文一年級(jí)練習(xí)題
- web前端開發(fā)教案
- 12KW移動(dòng)電站培訓(xùn)教材《柴油發(fā)電機(jī)》
- 保險(xiǎn)機(jī)構(gòu)公司治理評(píng)價(jià)表
- 高危藥品分級(jí)管理的分類及目錄
- 滿堂腳手架搭設(shè)規(guī)范方案
- 國家重點(diǎn)保護(hù)野生植物采集許可證
- 車險(xiǎn)查勘運(yùn)作規(guī)范及技術(shù)指引
- 醫(yī)藥行業(yè)專題研究:GLP-1藥物蓬勃發(fā)展產(chǎn)業(yè)鏈機(jī)遇全景梳理
- 傳承和弘揚(yáng)中華優(yōu)秀傳統(tǒng)文化
- 數(shù)字經(jīng)濟(jì)學(xué)導(dǎo)論-完整全套課件
- 食品生產(chǎn)企業(yè)6s管理培訓(xùn)
評(píng)論
0/150
提交評(píng)論