單元4一、選擇題12345ACDDC678910DBBAC1112131415CBBBD1617181920BCCAB2122232425DCAAD二、簡答題1．什么是滿二叉樹？什么是完全二叉樹？k2k?1在一棵二叉樹中，除了最后一層，都是滿的，并且最后一層或者是滿的，或者是右邊缺少連續(xù)若干結(jié)點(diǎn)，成為完全二叉樹。2．非空二叉樹中葉子結(jié)點(diǎn)與度為２結(jié)點(diǎn)的關(guān)系是什么？對任何一棵非空二叉樹，如果其葉子結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的非葉子結(jié)點(diǎn)個(gè)數(shù)為n2，則n0=n2+1。簡述二叉樹的先序遍歷、中序遍歷、后序遍歷。先序遍歷：若二叉樹為空，則退出，否則進(jìn)行下面操作：訪問根結(jié)點(diǎn)、先序遍歷左子樹、先序遍歷右子樹。中序遍歷：若二叉樹為空，則退出，否則進(jìn)行下面操作：中序遍歷左子樹、訪問根結(jié)點(diǎn)、中序遍歷右子樹。后序遍歷：若二叉樹為空，則退出，否則進(jìn)行下面操作：后序遍歷左子樹、后序遍歷右子樹、訪問根結(jié)點(diǎn)。三、分析題1.已知一顆二叉樹的先序序列：ABDGJEHCFIKL；中序序列：DJGBEHACKILF。請畫出二叉樹的形態(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。請為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。四、算法設(shè)計(jì)題1.以二叉鏈表作存儲結(jié)構(gòu)，請編寫求二叉樹深度的算法。//二叉樹的深度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.有一二叉鏈表，試編寫按層次順序遍歷二叉樹的算法。 //二叉樹的層次遍歷 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對象用于讀取用戶輸入Scannerscanner=newScanner(System.in);//讀取完全二叉樹的節(jié)點(diǎn)個(gè)數(shù)Nintn=scanner.nextInt();//創(chuàng)建一個(gè)長度為n的數(shù)組，用于存儲每個(gè)節(jié)點(diǎn)的權(quán)值long[]values=newlong[n];//循環(huán)讀取每個(gè)節(jié)點(diǎn)的權(quán)值，并存儲到values數(shù)組中for(inti=0;i<n;i++){values[i]=scanner.nextLong();}//計(jì)算完全二叉樹的深度。根據(jù)公式：深度=log?(N)+1，這里通過數(shù)學(xué)庫函數(shù)計(jì)算intdepth=(int)(Math.log(n)/Math.log(2))+1;//初始化最大權(quán)值和為Long類型的最小值，用于后續(xù)比較更新longmaxSum=Long.MIN_VALUE;//遍歷每一層for(intd=0;d<depth;d++){//計(jì)算當(dāng)前層節(jié)點(diǎn)在數(shù)組中的起始索引。對于第d層（d從0開始），起始索引為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)可能不滿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()