單元4一、選擇題12345ACDDC678910DBBAC1112131415CBBBD1617181920BCCAB2122232425DCAAD二、簡(jiǎn)答題1．什么是滿(mǎn)二叉樹(shù)？什么是完全二叉樹(shù)？k2k?1在一棵二叉樹(shù)中，除了最后一層，都是滿(mǎn)的，并且最后一層或者是滿(mǎn)的，或者是右邊缺少連續(xù)若干結(jié)點(diǎn)，成為完全二叉樹(shù)。2．非空二叉樹(shù)中葉子結(jié)點(diǎn)與度為２結(jié)點(diǎn)的關(guān)系是什么？對(duì)任何一棵非空二叉樹(shù)，如果其葉子結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的非葉子結(jié)點(diǎn)個(gè)數(shù)為n2，則n0=n2+1。簡(jiǎn)述二叉樹(shù)的先序遍歷、中序遍歷、后序遍歷。先序遍歷：若二叉樹(shù)為空，則退出，否則進(jìn)行下面操作：訪(fǎng)問(wèn)根結(jié)點(diǎn)、先序遍歷左子樹(shù)、先序遍歷右子樹(shù)。中序遍歷：若二叉樹(shù)為空，則退出，否則進(jìn)行下面操作：中序遍歷左子樹(shù)、訪(fǎng)問(wèn)根結(jié)點(diǎn)、中序遍歷右子樹(shù)。后序遍歷：若二叉樹(shù)為空，則退出，否則進(jìn)行下面操作：后序遍歷左子樹(shù)、后序遍歷右子樹(shù)、訪(fǎng)問(wèn)根結(jié)點(diǎn)。三、分析題1.已知一顆二叉樹(shù)的先序序列：ABDGJEHCFIKL；中序序列：DJGBEHACKILF。請(qǐng)畫(huà)出二叉樹(shù)的形態(tài)。2．假設(shè)用于通訊電文僅有8個(gè)字母A、B、C、D、E、F、G、H組成，字母在電文出現(xiàn)的頻率分別為：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。請(qǐng)為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。四、算法設(shè)計(jì)題1.以二叉鏈表作存儲(chǔ)結(jié)構(gòu)，請(qǐng)編寫(xiě)求二叉樹(shù)深度的算法。//二叉樹(shù)的深度publicintheight(){ returnheight(this.root); } publicintheight(BinaryNode<T>p){ if(p==null){ return0; } intlh=height(p.lchild); intlr=height(p.rchild); return(lh>lr)?lh+1:lr+1; }2.有一二叉鏈表，試編寫(xiě)按層次順序遍歷二叉樹(shù)的算法。 //二叉樹(shù)的層次遍歷 publicvoidlevelOrder(){ System.out.println("層次遍歷:"); LinkedQueue<BinaryNode<T>>que=newLinkedQueue<BinaryNode<T>>(); BinaryNode<T>p=this.root; while(p!=null){ System.out.print(p.data+""); if(p.lchild!=null){ que.enqueue(p.lchild); } if(p.rchild!=null){ que.enqueue(p.rchild); } p=que.dequeue(); } System.out.println(); }3.publicclassWeight{publicstaticvoidmain(String[]args){//創(chuàng)建Scanner對(duì)象用于讀取用戶(hù)輸入Scannerscanner=newScanner(System.in);//讀取完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)Nintn=scanner.nextInt();//創(chuàng)建一個(gè)長(zhǎng)度為n的數(shù)組，用于存儲(chǔ)每個(gè)節(jié)點(diǎn)的權(quán)值long[]values=newlong[n];//循環(huán)讀取每個(gè)節(jié)點(diǎn)的權(quán)值，并存儲(chǔ)到values數(shù)組中for(inti=0;i<n;i++){values[i]=scanner.nextLong();}//計(jì)算完全二叉樹(shù)的深度。根據(jù)公式：深度=log?(N)+1，這里通過(guò)數(shù)學(xué)庫(kù)函數(shù)計(jì)算intdepth=(int)(Math.log(n)/Math.log(2))+1;//初始化最大權(quán)值和為L(zhǎng)ong類(lèi)型的最小值，用于后續(xù)比較更新longmaxSum=Long.MIN_VALUE;//遍歷每一層for(intd=0;d<depth;d++){//計(jì)算當(dāng)前層節(jié)點(diǎn)在數(shù)組中的起始索引。對(duì)于第d層（d從0開(kāi)始），起始索引為2^d-1intstart=(int)Math.pow(2,d)-1;//計(jì)算當(dāng)前層節(jié)點(diǎn)在數(shù)組中的結(jié)束索引。取2^(d+1)-1和n中的較小值，因?yàn)樽詈笠粚庸?jié)點(diǎn)可能不滿(mǎn)intend=Math.min((int)Math.pow(2,d+1)-1,n);//初始化當(dāng)前層節(jié)點(diǎn)權(quán)值之和為0longsum=0;//計(jì)算當(dāng)前層節(jié)點(diǎn)權(quán)值之和for(inti=start;i<end;i++){sum+=values[i];}//更新最大權(quán)值和。比較當(dāng)前層權(quán)值和sum與已記錄的最大權(quán)值和maxSum，取較大值maxSum=Math.max(maxSum,sum);}//輸出所有層中的最大權(quán)值和System.out.println(maxSum);scanner.close()