第7章 樹(shù)與二叉樹(shù)

《第7章 樹(shù)與二叉樹(shù)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、第七章習(xí)題參考答案一、簡(jiǎn)答題1．【參考答案】：無(wú)序樹(shù)：如果樹(shù)中任意結(jié)點(diǎn)的各孩子結(jié)點(diǎn)的排列沒(méi)有嚴(yán)格次序，可交換位置，則稱該樹(shù)為無(wú)序樹(shù)。有序樹(shù)：如果樹(shù)中任意結(jié)點(diǎn)的各孩子結(jié)點(diǎn)的排列有嚴(yán)格的次序，不可交換位置，則稱該樹(shù)為有序樹(shù)。2．【參考答案】：滿二叉樹(shù)：若深度為h的二叉樹(shù)，恰好具有-1個(gè)結(jié)點(diǎn)，則稱為滿二叉樹(shù)。完全二叉樹(shù)：若一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)的邏輯結(jié)構(gòu)與滿二叉樹(shù)的前n個(gè)結(jié)點(diǎn)的邏輯結(jié)構(gòu)完全相同，則稱該二叉樹(shù)為完全二叉樹(shù)。3．【參考答案】：最多-1個(gè)結(jié)點(diǎn)，最少-1個(gè)結(jié)點(diǎn)。4．【參考答案】：存儲(chǔ)二叉樹(shù)時(shí)，同時(shí)存儲(chǔ)結(jié)點(diǎn)在遍歷序列中的前驅(qū)和后繼信息，使

2、在對(duì)二叉樹(shù)進(jìn)行各種操作時(shí)就會(huì)更加地方便。5．【參考答案】：如下圖：ABFCGDEH6．【參考答案】：如右圖107ABHECIKFGDJLNMO此二叉樹(shù)有6層7．【參考答案】：（1）如右圖7923512161052238帶權(quán)路徑：7*2+9*2+12*2+5*3+2*4+3*4=91哈夫曼編碼：A：1000B：1001C：101D：00E：01F：11二、實(shí)驗(yàn)題1．【參考答案】：publicvoidSearchTree(TreeNoderoot){java.util.Queueq=newjava.util.LinkedLi

3、st();if(root==null)return;TreeNodetn;q.add(root);while(!q.isEmpty()){tn=q.remove();System.out.print(tn.getData());107if(tn.getLeft()!=null)q.add(tn.getLeft());if(tn.getRight()!=null)q.add(tn.getRight());}}2．【參考答案】：publicintObtainDeep(TreeNoderoot){if(root==null)r

4、eturn0;intileft=1,iright=1,ideep=1;TreeNodetn=root;if(tn!=null){ileft+=ObtainDeep(tn.getLeft());iright+=ObtainDeep(tn.getRight());if(ileft>=iright)ideep=ileft;elseideep=iright;}returnideep;}3．【參考答案】：publicbooleanisFullTree(TreeNoderoot){if(root==null)returnfalse;TreeNodetn

5、=root;if(tn!=null){if(tn.getLeft()==null){if(tn.getRight()!=null)returnfalse;returntrue;}else{if(this.hasChildNode(tn)){if(tn.getRight()==null)returnfalse;}}returnisFullTree(tn.getLeft());}returnfalse;}4．107【參考答案】：publicbooleanequals(TreeNoder1,TreeNoder2){if(r1==r2)return

6、true;if(r1==null&&r2==null)returntrue;if(r1==null

7、

8、r2==null)returnfalse;booleanrflag,lflag;if(r1.equals(r2)){lflag=equals(r1.getLeft(),r2.getLeft());rflag=equals(r1.getRight(),r2.getRight());}elsereturnfalse;returnlflag&&rflag;}5．【參考答案】：該程序的功能為求二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)。6．【參考答案】：該程序的功能將二叉樹(shù)

9、中左、右全部結(jié)點(diǎn)進(jìn)行交換。7．【參考答案】：參考P147。三、思考題1．【參考答案】：（1）能（2）能（3）能2．【參考答案】：根據(jù)二叉排序樹(shù)的概念可知，當(dāng)遇到相同元素時(shí)，后面插入的元素進(jìn)入到前面元素的右子樹(shù)中，但是具體位置要看目前二叉排序樹(shù)該結(jié)點(diǎn)的右子樹(shù)狀態(tài)而定。107