資源描述：
《已知它有m個(gè)葉子結(jié)點(diǎn),證明非葉子結(jié)點(diǎn)中有m-1個(gè)結(jié)點(diǎn)的.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、作業(yè)：1、任意一個(gè)有n個(gè)結(jié)點(diǎn)的二叉樹，已知它有m個(gè)葉子結(jié)點(diǎn)，證明非葉子結(jié)點(diǎn)中有m-1個(gè)結(jié)點(diǎn)的度為2，其余度為1。2、已知二叉樹有50個(gè)葉子結(jié)點(diǎn)，則該二叉樹的總結(jié)點(diǎn)數(shù)至少應(yīng)有多少個(gè)？1、證明：設(shè)度為1的結(jié)點(diǎn)有n1個(gè)，為2的有n2個(gè)，則總結(jié)點(diǎn)為：n=n1+n2+m又：n=B+1B為分支數(shù)B=n1+2n2則：n=n1+2n2+1故：n1+n2+m=n1+2n2+1有：n2=m-12、設(shè)度為0、1、2的結(jié)點(diǎn)數(shù)及總結(jié)點(diǎn)數(shù)分別為n0、n1、n2、n。則：n0=50n=n0+n1+n2n-1=n1+2n2得：n2=49故：n-
2、1=n1+2*49n=n1+99所以當(dāng)n1=0時(shí)，n最少，所以n至少有99個(gè)結(jié)點(diǎn)。10/7/2021作業(yè)：1、假定一棵二叉樹的廣義表表示為(a(b(c),d(e,f)))，分別寫出它的先序、中序、后序和層次遍歷的結(jié)果。2、已知一棵二叉樹的先序和中序序列，求該二叉樹的后序序列。先序：ABCDEFGHIJ中序：CBAEFDIHJG3、已知一棵二叉樹的中根和后根序列，求該二叉樹的深度和度為2、度為1和葉子結(jié)點(diǎn)數(shù)。中根：CBDEAGIHJF后根：CEDBIJHGFA4、一個(gè)二叉樹的先序、中序和后序分別如下，其中一部分未顯
3、示出來，試求出空格處的內(nèi)容，并畫出該二叉樹。先序：__B__F__ICEH__G中序：D__KFIA__EJC__后序：__K__FBHJ__G__A答:ABDFKICEHJGDBKFIAHEJCGDKIFBHJEGCA10/7/2021作業(yè)：1、將二叉樹轉(zhuǎn)換為森林。ABEDCFGHIJ2、將森林轉(zhuǎn)換為二叉樹。12AHIKJCDEFG10/7/20213、已知二叉樹的結(jié)點(diǎn)類型為：typedefstructnode{ElemTypedata;structnode*left,*right;//指向左右孩子}BTree
4、;下面函數(shù)返回二叉樹中值為X的結(jié)點(diǎn)所在的層號(hào)，補(bǔ)充合適內(nèi)容。intNodeLevel(BTree*bt,ElemTypeX){if(bt==NULL)return0;//空樹層號(hào)為0elseif(bt->data==X)return1;//根結(jié)點(diǎn)層號(hào)為1else{intc1=NodeLevel(bt->left,X);if(c1>=1)_____(1)_____;intc2=NodeLevel(bt->right,X);if(c2>=1)_____(2)_______;if____(3)______;elsere
5、turn0;//若樹中不存在X，則返回0}}c1++;c2++;(c1>=1
6、
7、c2>=1)returnc1>c2?c1:c210/7/2021作業(yè)：1、如果一棵Huffman樹T有n0個(gè)葉子結(jié)點(diǎn)，那么，樹T有多少個(gè)結(jié)點(diǎn)？給出求解過程。提示：Huffman樹只有度為2和0的結(jié)點(diǎn)，又n0=n2+1,n=no+n2故：n=2n0-12、有7個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為3，7，8，2，6，10，14，試以它們?yōu)槿~子結(jié)點(diǎn)構(gòu)造一棵Huffman樹，并計(jì)算帶權(quán)路徑長(zhǎng)度。3、在一份電文中共使用了五種字符，即a,b,c,d,e,它們
8、的出現(xiàn)頻率依次為4,7,5,2,9,試畫出對(duì)應(yīng)的Huffman樹，并求出每個(gè)字符的Huffman編碼。10/7/2021練習(xí)：根據(jù)圖的鄰接矩陣畫出圖????????????????????10/7/2021練習(xí)：畫出下圖的關(guān)聯(lián)矩陣BDAC123456ABCD43215610/7/2021作業(yè)：1、用鄰接矩陣存儲(chǔ)圖時(shí)，矩陣元素個(gè)數(shù)與頂點(diǎn)個(gè)數(shù)是否相關(guān)？與邊的條數(shù)是否有關(guān)？（與頂點(diǎn)相關(guān)，與邊無關(guān)）2、在什么情況下，Prim算法和Kruskual算法生成不同的最小生成樹？（具有相同權(quán)的邊時(shí)）3、給出一個(gè)帶權(quán)圖的鄰接矩陣（
9、頂點(diǎn)編號(hào)1~8），如下：????????????????10/7/2021(1)給出在該圖上從頂點(diǎn)1出發(fā)進(jìn)行DFS遍歷的結(jié)果序列，并根據(jù)此判斷該圖是否為連通圖？(2)畫出該圖的鄰接鏈表。(3)畫出按Prim算法構(gòu)造的最小生成樹（森林）。4、給定如下網(wǎng)G（頂點(diǎn)編號(hào)1~6）。(1)畫出該圖的鄰接鏈表存儲(chǔ)結(jié)構(gòu)。(2)根據(jù)該圖的鄰接鏈表存儲(chǔ)結(jié)構(gòu)，從頂點(diǎn)1出發(fā)，調(diào)用BFS和DFS算法遍歷該圖，給出可能經(jīng)過的頂點(diǎn)序列。(3)給出采用Kruskual算法構(gòu)造最小生成樹的過程。164352910561187710/7/2021作
10、業(yè)：1、某帶權(quán)有向圖及其鄰接鏈表如圖。(1)給出深度優(yōu)先搜索順序。(2)將該圖作為AOE網(wǎng)，寫出C的最早開始時(shí)間和活動(dòng)FC的最晚開始時(shí)間。(3)用Dijstral算法計(jì)算源點(diǎn)A到其它各點(diǎn)的最短路徑；BCEADFG12333211151234ACDB5EFG67B1C2D3^C3E1^E2^F3^G1^C1G5^^10/7/2021答案：DFS結(jié)果：ABCEGDFC的最早開
