第六章作業(yè)解析

1、第六章 作業(yè)解析（部分）作 業(yè)(ch6-1)(要求給出計(jì)算過(guò)程)1、有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)，計(jì)算它的度為1的結(jié)點(diǎn)數(shù)目、葉子結(jié)點(diǎn)的數(shù)目。2、已知完全二叉樹(shù)的第7層上有10個(gè)葉子，則該二叉樹(shù)至多有多少個(gè)結(jié)點(diǎn)?3、已知某度為k的樹(shù)中，其度為0、1、2、k-1的結(jié)點(diǎn)數(shù)分別為n0、n1、n2、nk-1。求該樹(shù)的結(jié)點(diǎn)總數(shù)n，并給出推導(dǎo)過(guò)程。(CH6-1)1、有、有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)，計(jì)算它個(gè)結(jié)點(diǎn)的滿二叉樹(shù)，計(jì)算它的度為的度為1的結(jié)點(diǎn)數(shù)目、葉子結(jié)點(diǎn)的數(shù)目。的結(jié)點(diǎn)數(shù)目、葉子結(jié)點(diǎn)的數(shù)目。設(shè)度為設(shè)度為1的結(jié)點(diǎn)數(shù)目為的結(jié)點(diǎn)數(shù)目為n1，葉子結(jié)點(diǎn)數(shù)目為，葉子結(jié)點(diǎn)數(shù)目為n0，度為度為2的結(jié)點(diǎn)數(shù)目為的結(jié)點(diǎn)數(shù)目為n2；因該二叉

2、樹(shù)為滿二叉樹(shù)，則有因該二叉樹(shù)為滿二叉樹(shù)，則有n1=0，又有，又有n0=n2+1，則，則n=n0+n2=2n0-1，得，得n0=(n+1)/2(CH6-1)2、已知完全二叉樹(shù)的第、已知完全二叉樹(shù)的第7層上有層上有10個(gè)葉子，則該二叉樹(shù)至多有多少個(gè)結(jié)點(diǎn)個(gè)葉子，則該二叉樹(shù)至多有多少個(gè)結(jié)點(diǎn)?該二叉樹(shù)結(jié)點(diǎn)達(dá)到最大值，深度應(yīng)為8，前7層結(jié)點(diǎn)為一棵滿二叉樹(shù)，第7層中的葉子應(yīng)位為本層最右邊，則第8層中的結(jié)點(diǎn)數(shù)應(yīng)為：(27-1-10)*2=108這棵二叉樹(shù)的結(jié)點(diǎn)總數(shù)為：(27-1)+108=235作 業(yè)(ch6-2)1、二叉樹(shù)用二叉鏈表存儲(chǔ)，編寫(xiě)算法采用、二叉樹(shù)用二叉鏈表存儲(chǔ)，編寫(xiě)算法采用先序遍歷查找值為先序遍

3、歷查找值為x的結(jié)點(diǎn)，找到返回其指的結(jié)點(diǎn)，找到返回其指針，否則返回針，否則返回NULL。2、二叉樹(shù)用二叉鏈表存儲(chǔ)，編寫(xiě)算法要求、二叉樹(shù)用二叉鏈表存儲(chǔ)，編寫(xiě)算法要求返回二叉樹(shù)的后序序列中的第一個(gè)結(jié)點(diǎn)的返回二叉樹(shù)的后序序列中的第一個(gè)結(jié)點(diǎn)的指針。指針。3、已知一棵二叉樹(shù)的先序序列和中序序列、已知一棵二叉樹(shù)的先序序列和中序序列分別存儲(chǔ)于兩個(gè)一維數(shù)組分別存儲(chǔ)于兩個(gè)一維數(shù)組pre和和ino中，編中，編寫(xiě)算法建立該二叉樹(shù)的二叉鏈表。寫(xiě)算法建立該二叉樹(shù)的二叉鏈表。(ch6-2)1、二叉樹(shù)用二叉鏈表存儲(chǔ)，編寫(xiě)算法采、二叉樹(shù)用二叉鏈表存儲(chǔ)，編寫(xiě)算法采用先序遍歷查找值為用先序遍歷查找值為x的結(jié)點(diǎn)，找到返回其指針，的結(jié)

4、點(diǎn)，找到返回其指針，否則返回否則返回NULL。BinTree search_x(BinTree t , TreeType x) if(!t) return NULL; /查找失敗 else if(t-data=x) return t; /查找成功 else p= search_x(p-lchild, x); if(p) return p; else /在左子樹(shù)中未找到x return search_x(p-rchild, x); (ch6-2)2、二叉樹(shù)用二叉鏈表存儲(chǔ)，編寫(xiě)算法要求、二叉樹(shù)用二叉鏈表存儲(chǔ)，編寫(xiě)算法要求返回二叉樹(shù)的后序序列中的第一個(gè)結(jié)點(diǎn)的指針。返回二叉樹(shù)的后序序列中的第一個(gè)結(jié)點(diǎn)的

5、指針。BinTree FirstNode(BinTree t)/返回二叉鏈表返回二叉鏈表t的后序遍歷序列中的第一個(gè)結(jié)點(diǎn)的后序遍歷序列中的第一個(gè)結(jié)點(diǎn) p=t; if(p) while(p-lchild|p-rchild) /p有孩子 /找到p的左子樹(shù)中的最左下方的結(jié)點(diǎn) while(p-lchild) p=p-lchild; if(p-rchild) p=p-rchild; return p;(ch6-2)3、已知一棵二叉樹(shù)的先序序列和中序、已知一棵二叉樹(shù)的先序序列和中序序列分別存儲(chǔ)于兩個(gè)一維數(shù)組序列分別存儲(chǔ)于兩個(gè)一維數(shù)組pre和和ino中，編中，編寫(xiě)算法建立該二叉樹(shù)的二叉鏈表。寫(xiě)算法建立該二叉樹(shù)

6、的二叉鏈表。BinTree create(char *pre,char *ino , int n) if(ndata= *pre; /根結(jié)點(diǎn) for(q=ino; qlchild = create(pre+1, ino, k); p-rchild= create(pre+1+k, ino+1,n-1-k); return p; 作作 業(yè)業(yè)(ch6-3)(ch6-3)1 1、已知一棵二叉樹(shù)的中序序列為、已知一棵二叉樹(shù)的中序序列為 B F D H G A E C 先序序列為先序序列為A B D F G H C E， 畫(huà)出該二叉樹(shù)的后序線索二叉樹(shù)（注意畫(huà)出該二叉樹(shù)的后序線索二叉樹(shù)（注意不要漏添和多添

7、線索，線索肯定是不要漏添和多添線索，線索肯定是n+1n+1個(gè)，個(gè)，n n為結(jié)點(diǎn)個(gè)數(shù)。答案略）為結(jié)點(diǎn)個(gè)數(shù)。答案略） (ch6-3)2(ch6-3)2、編寫(xiě)算法在一中序線索化二叉鏈表中、編寫(xiě)算法在一中序線索化二叉鏈表中查詢某個(gè)已知結(jié)點(diǎn)在中序遍歷序列中的前驅(qū)。查詢某個(gè)已知結(jié)點(diǎn)在中序遍歷序列中的前驅(qū)。BinTree prenode(BinThrTree t, BiThrNode p) q= p-lchild; if(p-LTag= Link) /p有左孩子 while(q-RTage=Link) /找到最右下方的結(jié)點(diǎn) q=q-rchild; return q;2022-3-12濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系

8、1、有一份電文中共使用、有一份電文中共使用5個(gè)字符：個(gè)字符：a、b、c、d、e，它們的出現(xiàn)頻率，它們的出現(xiàn)頻率權(quán)值權(quán)值依次為依次為 4、7、5、2、9，試畫(huà)出對(duì)應(yīng)的哈夫曼樹(shù)，并為每個(gè)字符設(shè)，試畫(huà)出對(duì)應(yīng)的哈夫曼樹(shù)，并為每個(gè)字符設(shè)計(jì)哈夫曼編碼。（略）計(jì)哈夫曼編碼。（略）作作 業(yè)（業(yè)（ch6-4）(ch6-4)2(ch6-4)2、假設(shè)二叉樹(shù)用二叉鏈表存儲(chǔ)、假設(shè)二叉樹(shù)用二叉鏈表存儲(chǔ), ,編寫(xiě)一編寫(xiě)一個(gè)算法，求一個(gè)二叉樹(shù)中的最大結(jié)點(diǎn)的值。個(gè)算法，求一個(gè)二叉樹(shù)中的最大結(jié)點(diǎn)的值。/設(shè)max為全局變量，初值為INTMINElemTye maxnode(BinTree t) if(!t-lchild &!t-rchild) return t-data; else if