12信管實(shí)驗(yàn)報(bào)告(樹與二叉樹的基本操作)

管理學(xué)院信管專業(yè)12（1）班學(xué)號3112004734姓名協(xié)作者：無 教師評定_________________實(shí)驗(yàn)題目樹與二叉樹的基本操作實(shí)驗(yàn)評分表指導(dǎo)教師評分標(biāo)準(zhǔn)序號評分項(xiàng)目評分標(biāo)準(zhǔn)滿分打分1完成度按要求獨(dú)立完成實(shí)驗(yàn)準(zhǔn)備、程序調(diào)試、實(shí)驗(yàn)報(bào)告撰寫。202實(shí)驗(yàn)內(nèi)容完成功能需求分析、存儲結(jié)構(gòu)設(shè)計(jì)；程序功能完善、可正常運(yùn)行；測試數(shù)據(jù)正確，分析正確，結(jié)論正確。303實(shí)驗(yàn)報(bào)告內(nèi)容齊全，符合要求，文理通順，排版美觀。404總結(jié)對實(shí)驗(yàn)過程遇到的問題能初步獨(dú)立分析，解決后能總結(jié)問題原因及解決方法，有心得體會。10下述代碼盡管輸入eclipse或者JC驗(yàn)證，絕無弄虛作假實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)?zāi)康呐c要求本實(shí)驗(yàn)通過對線性表各種操作的算法設(shè)計(jì)，理解和掌握線性表的概念、存儲結(jié)構(gòu)及操作要求，體會順序和鏈?zhǔn)絻煞N存儲結(jié)構(gòu)的特點(diǎn)；根據(jù)操作的不同要求，選擇合適的存儲結(jié)構(gòu)，設(shè)計(jì)并實(shí)現(xiàn)算法，對算法進(jìn)行時間復(fù)雜度分析，從而達(dá)到掌握數(shù)據(jù)結(jié)構(gòu)的研究方法、算法設(shè)計(jì)和分析方法的目的。實(shí)驗(yàn)內(nèi)容在一棵二叉鏈表表示的二叉樹中,實(shí)現(xiàn)以下操作，并說明采用哪種遍歷算法,其他遍歷算法是否可行。輸出葉子結(jié)點(diǎn)//求二叉樹葉子結(jié)點(diǎn)個數(shù)的遞歸算法publicclassleaf{//輸出葉子結(jié)點(diǎn) publicstatic<T>voidleaf(BinaryTree<T>bitree){ leaf(bitree.root); } publicstatic<T>voidleaf(BinaryNode<T>p){ if(p!=null){ if(p.left==null&&p.right==null){ System.out.println(p.data+""); } leaf(p.left); leaf(p.right); } } publicstaticvoidmain(Stringargs[]){ Stringprelist[]={"A","B","D",null,"G",null,null,null,"C","E",null,null,"F","G"};//先根遍歷序列 BinaryTree<String>bitree=newBinaryTree<String>(prelist);//以先根遍歷序列構(gòu)造的一棵二叉樹 bitree.preOrder();//先根次序遍歷的遞歸算法 leaf(bitree); Stringprelist2[]={"A","B",null,null,"C"};//先根遍歷序列 BinaryTree<String>bitree2=newBinaryTree<String>(prelist2);//以先根遍歷序列構(gòu)造的一棵二叉樹 bitree2.preOrder();//先根次序遍歷的遞歸算法 leaf(bitree2); } }運(yùn)算結(jié)果：(2)求二叉樹中葉子節(jié)點(diǎn)的個數(shù)//求二叉樹中葉子結(jié)點(diǎn)的個數(shù)的遞歸算法publicclassgetLeaves{ publicstatic<T>intgetLeaves(BinaryTree<T>bitree){ returngetLeaves(bitree.root); }publicstatic<T>intgetLeaves(BinaryNode<T>p){ inti=0; if(p!=null) { if(p.left==null&&p.right==null){ i++; } getLeaves(p.left); getLeaves(p.right); } System.out.println(i); return0;}publicstaticvoidmain(Stringargs[]){Stringprelist[]={"A","B","D",null,"G",null,null,null,"C","E",null,null,"F","E"};BinaryTree<String>bitree=newBinaryTree<String>(prelist);bitree.preOrder();getLeaves(bitree);Stringprelist2[]={"A","B",null,null,"C"};BinaryTree<String>bitree2=newBinaryTree<String>(prelist2);bitree2.preOrder();getLeaves(bitree2);}}運(yùn)算結(jié)果：(3)將每個結(jié)點(diǎn)的左子樹和右子樹交換//將二叉樹的每個結(jié)點(diǎn)的左右子樹交換的遞歸算法//交換二叉樹的左右子樹的遞歸算法的實(shí)現(xiàn)publicclassBitree_revolute{ publicstatic<T>voidBitree_revolute(BinaryTree<T>bitree){ Bitree_revolute(bitree.root);//從bitree樹的根結(jié)點(diǎn)開始遍歷 }publicstatic<T>voidBitree_revolute(BinaryNode<T>p){ if(p!=null){ p.setLeftChild(p.getRightChild());//交換左右子樹 p.setRightChild(p.getLeftChild());//交換左右子樹 System.out.println(p.data.toString()); if(p.getLeftChild()!=null){ Bitree_revolute(p.getLeftChild()); } if(p.getRightChild()!=null){ Bitree_revolute(p.getRightChild()); } }} publicstaticvoidmain(Stringargs[]){ Stringprelist[]={"A","B","D",null,"G",null,null,null,"C","E",null,null,"F","E"}; BinaryTree<String>bitree=newBinaryTree<String>(prelist); bitree.preOrder();//先根次序遍歷 Bitree_revolute(bitree); Stringprelist2[]={"A","B",null,null,"C"}; BinaryTree<String>bitree2=newBinaryTree<String>(prelist2); bitree2.preOrder();//先根次序遍歷 Bitree_revolute(bitree2); }}運(yùn)算結(jié)果：(4)驗(yàn)證二叉樹的性質(zhì)3：n0=n2+1//驗(yàn)證二叉樹的性質(zhì)3的遞歸算法publicclassProperty3<T>{//驗(yàn)證二叉樹的性質(zhì)3,n0=n2+1privatestaticintn0=0,n2=0;//聲明并初始化2度結(jié)點(diǎn)數(shù)n2,0度結(jié)點(diǎn)數(shù)n0(0度結(jié)點(diǎn)數(shù)即是葉子結(jié)點(diǎn)數(shù))publicstatic<T>voidcount(BinaryTree<T>bitree){//統(tǒng)計(jì)二度結(jié)點(diǎn)數(shù)n2和葉子結(jié)點(diǎn)數(shù)n0 n0=0;n2=0; count(bitree.root); System.out.println("驗(yàn)證二叉樹的性質(zhì)3,n0="+n0+",n2="+n2+",n0==n2+1?"+(n0==n2+1));}privatestatic<T>voidcount(BinaryNode<T>p){//統(tǒng)計(jì)二度結(jié)點(diǎn)數(shù)n2和葉子結(jié)點(diǎn)數(shù)n0//以p結(jié)點(diǎn)為根的子樹的結(jié)點(diǎn)數(shù)if(p!=null){ if(p.left==null&&p.right==null)//葉子結(jié)點(diǎn) n0++;// if(p.left!=null&&p.right!=null)//2度結(jié)點(diǎn) n2++; count(p.left); count(p.right);}}publicstaticvoidmain(Stringargs[]){//測試 Stringprelist[]={"A","B","D",null,"G",null,null,null,"C","E",null,null,"F","E"};//以一維數(shù)組Stringprelist[]存儲二叉樹的標(biāo)明空子樹的先根遍歷序列 BinaryTree<String>bitree=newBinaryTree<String>(prelist);//以先根遍歷序列prelist構(gòu)造二叉樹bitree bitree.preOrder();//先根次序遍歷的遞歸算法 count(bitree); Stringprelist2[]={"A","B",null,null,"C"};//以一維數(shù)組Stringprelist2[]存儲二叉樹的標(biāo)明空子樹的先根遍歷序列2 BinaryTree<String>bitree2=newBinaryTree<String>(prelist2);//以先根遍歷序列構(gòu)造二叉樹bitree2 bitree2.preOrder();//先根次序遍歷的遞歸算法 count(bitree);}}運(yùn)算結(jié)果：(5)判斷一棵二叉樹bitree是否與當(dāng)前二叉樹的一棵子樹匹配。方法一：publicclassBoolIsSubTree_1{ publicstaticvoidmain(Stringargs[]){ Stringprelist[]={"A","B","D",null,"G",null,null,null,"C","E",null,null,"F","E"}; BinaryTree<String>bitree=newBinaryTree<String>(prelist); Stringprestr=bitree.preOrder();Stringinstr=bitree.inOrder(); Stringprelist2[]={"C","E","F"};Stringinlist[]={"E","C","F"};BinaryTree<String>bitree2=newBinaryTree<String>(prelist2,inlist);if(inlist.toString().indexOf(instr)!=-1&&(prelist.toString().indexOf(prestr)!=-1)){ System.out.println("bitree2是bitree的子樹");}else System.out.println("bitree2不是bitree的子樹");} }運(yùn)算結(jié)果：方法二：//判斷一棵二叉樹是否為另一顆二叉樹的子樹的遞歸算法publicclassBoolIsSubTree{publicstaticvoidmain(Stringargs[]){ Stringprelist[]={"A","B","D",null,"G",null,null,null,"C","E",null,null,"F","E"};//先根遍歷序列 BinaryTree<String>bitree=newBinaryTree<String>(prelist);//以先根遍歷序列構(gòu)造一棵二叉樹 Stringinlist[]={"E","C","F"};//中根遍歷序列 Stringprelist2[]={"C","E","F"};//先根遍歷序列 BinaryTree<String>bitree2=newBinaryTree<String>(prelist2,inlist);//以中根遍歷序列和先根遍歷序列構(gòu)造一棵子樹 BinaryNode<String>p=null; BinaryNode<String>q=null; bitree.postOrder(p,q,bitree2);}}運(yùn)算結(jié)果：輔助類：BinaryNodepublicclassBinaryNode<T>{//二叉樹的二叉鏈表結(jié)點(diǎn)類publicTdata;//數(shù)據(jù)域publicBinaryNode<T>left,right;//鏈域,分別指向左右孩子結(jié)點(diǎn)//構(gòu)造結(jié)點(diǎn),參數(shù)分別指定元素和左右孩子結(jié)點(diǎn)publicBinaryNode(Tdata,BinaryNode<T>left,BinaryNode<T>right){//構(gòu)造二叉樹結(jié)點(diǎn) this.data=data; this.left=left; this.right=right;} /** *@paramargs */publicBinaryNode(Tdata){//調(diào)用二叉樹結(jié)點(diǎn)的構(gòu)造方法 this(data,null,null);//構(gòu)造指定值的葉子結(jié)點(diǎn)}publicBinaryNode(){//調(diào)用二叉樹結(jié)點(diǎn)的構(gòu)造方法 this(null,null,null);//空的結(jié)點(diǎn)} publicbooleanisLeaf(){ //TODOAuto-generatedmethodstub BinaryNode<T>p=null; if(p.left==null&&p.right==null) returntrue; else returnfalse; } publicBinaryNode<T>getRightChild(){//獲取當(dāng)前結(jié)點(diǎn)的右孩子結(jié)點(diǎn) returnthis.left; } publicBinaryNode<T>getLeftChild(){//獲取當(dāng)前節(jié)點(diǎn)的左孩子結(jié)點(diǎn) returnthis.right; } publicvoidsetLeftChild(BinaryNode<T>rightChild){//設(shè)置當(dāng)前節(jié)點(diǎn)的右孩子結(jié)點(diǎn) this.left=rightChild; } publicvoidsetRightChild(BinaryNode<T>leftChild){//設(shè)置當(dāng)前結(jié)點(diǎn)的左孩子結(jié)點(diǎn) this.right=leftChild; }}輔助類：BinaryTreeimportjava.util.LinkedList;//線性鏈表importjava.util.Stack;//棧publicclassBinaryTree<T>implementsBinaryTTree<T>{publicBinaryNode<T>root;//根結(jié)點(diǎn),結(jié)點(diǎn)結(jié)構(gòu)為二叉鏈表publicBinaryTree(){ this.root=null;}//構(gòu)造空的二叉樹 /** *@paramargs */ publicbooleanisEmpty(){ returnthis.root==null; }//判斷二叉樹是否為空 @Override publicintcount(){//返回一棵二叉樹(子樹)的結(jié)點(diǎn)數(shù) //TODOAuto-generatedmethodstub returncount(root);//返回二叉樹的結(jié)點(diǎn)個數(shù) } publicintcount(BinaryNode<T>p){//返回以p結(jié)點(diǎn)為根的子樹的的結(jié)點(diǎn)個數(shù) if(p==null) return0; else return1+count(p.left)+count(p.right); } @Override publicintheight(){ //TODOAuto-generatedmethodstub return0; } @Override publicStringpreOrder(){//先根次序遍歷二叉樹 //TODOAuto-generatedmethodstub System.out.print("先根次序遍歷二叉樹:"); preOrder(root);//調(diào)用先根次序遍歷二叉樹的遞歸方法 /*System.out.println();*/ Stringprestr=""; returnprestr; } publicStringpreOrder(BinaryNode<T>p){//先根次序遍歷以p結(jié)點(diǎn)為根結(jié)點(diǎn)的子二叉樹,遞歸方法 Stringprestr=""; if(p!=null){//如果二叉樹不為空 /*System.out.println(p.data.toString()+"");//訪問當(dāng)前結(jié)點(diǎn) preOrder(p.left);//按照先根次序遍歷訪問當(dāng)前結(jié)點(diǎn)的左子樹,遞歸調(diào)用 preOrder(p.right);//按照先根次序遍歷訪問當(dāng)前結(jié)點(diǎn)的右子樹,遞歸調(diào)用*/ prestr+=p.data.toString(); preOrder(p.left); preOrder(p.right); } returnprestr; } @Override publicStringinOrder(){//中根遍歷二叉樹 //TODOAuto-generatedmethodstub System.out.print("中根次序遍歷二叉樹:"); inOrder(root); Stringinstr=""; /*System.out.println();*/returninstr; } publicStringinOrder(BinaryNode<T>p){//中根次序遍歷以p結(jié)點(diǎn)為根結(jié)點(diǎn)的子二叉樹,遞歸方法 Stringinstr=""; if(p!=null)//若二叉樹不空 { /*inOrder(p.left); System.out.print(p.data.toString()+""); inOrder(p.right);*/ inOrder(p.left); instr+=p.data.toString(); inOrder(p.right); } returninstr; } @Override publicvoidpostOrder(){//后根次序遍歷二叉樹 //TODOAuto-generatedmethodstub System.out.print("后根次序遍歷二叉樹:"); postOrder(root); System.out.println(); }publicvoidpostOrder(BinaryNode<T>p,BinaryNode<T>q,BinaryTree<T>bitree2){// if(p!=null&&q!=null)//如果二叉樹不為空 { postOrder(p.left); postOrder(p.right); //System.out.println(p.data.toString()+""); /*if(p.data==q.data&&p.left==q.left&&p.right==q.right){ postOrder(p.left);postOrder(q.left); postOrder(p.right); postOrder(q.right);//遍歷bitree2 }*/ //if(p.data==q.data){ //returnpostOrder(p.left,q.left,bitree2)&&postOrder(p.right,q.right,bitree2); //} if(p.data==bitree2.root){ if(p.data==q.data) postOrder(p.left,q.left,bitree2); postOrder(p.right,q.right,bitree2); if((p.isLeaf()==true)&&(q.isLeaf()==true)&&(p.data==q.data)){ System.out.println("bitree2是bitree的子樹"); }} } } /*publicbooleanpostOrder(BinaryNode<T>p,BinaryTree<T>bitree2){ BinaryNode<T>q=bitree2.root; postOrder(p.left); postOrder(p.right); if(p.data==q.data){ returnpostOrder(p.) }*/ publicvoidpostOrder(BinaryNode<T>p){//后根次序遍歷以p結(jié)點(diǎn)為根結(jié)點(diǎn)的子二叉樹,遞歸方法 if(p!=null)//如果二叉樹不為空 { postOrder(p.left); postOrder(p.right); System.out.print(p.data.toString()+""); } } @Override publicvoidlevelorder(){ //TODOAuto-generatedmethodstub } @Override publicBinaryNode<T>search(Tkey){//查找并返回首次出現(xiàn)的關(guān)鍵字為key的元素結(jié)點(diǎn) //TODOAuto-generatedmethodstub returnsearch(root,key); }publicBinaryNode<T>search(BinaryNode<T>p,Tkey){ if(p==null||key==null)//如果p為空或者key為空則此算法無法實(shí)現(xiàn) returnnull;if(p.data.equals(key)){ returnp;//查找成功,返回找到的結(jié)點(diǎn)}BinaryNode<T>find=search(p.left,key);//在左子樹中查找,遞歸調(diào)用if(find==null){//若在左子樹中未找到 find=search(p.right,key);}//則繼續(xù)在右子樹中查找,遞歸調(diào)用 returnfind;//返回查找的結(jié)果} @Override publicBinaryNode<T>getParent(BinaryNode<T>node){ //TODOAuto-generatedmethodstub returnnull; } @Override publicvoidinsertRoot(){ //TODOAuto-generatedmethodstub } @Override publicBinaryNode<T>insertChild(BinaryNode<T>p,Tx,booleanleftChild){ //TODOAuto-generatedmethodstub returnnull; } @Override publicvoidremoveChild(BinaryNode<T>p,booleanleftChild){ //TODOAuto-generatedmethodstub } @Override publicvoidremoveAll(){ //TODOAuto-generatedmethodstub } publicvoidinOrderTraverse(){//中根次序遍歷的非遞歸算法 System.out.print("中根次序遍歷(非遞歸):"); LinkedStack<BinaryNode<T>>stack=newLinkedStack();//創(chuàng)造空的鏈?zhǔn)綏４鎯Χ鏄浣Y(jié)點(diǎn)BinaryNode<T> BinaryNode<T>p=this.root;//p指向當(dāng)前二叉樹的根結(jié)點(diǎn) while(p!=null||!stack.isEmpty())//當(dāng)p不為空或者棧不為空時開始執(zhí)行 if(p!=null)//如果p不為空,則表示剛剛到達(dá)p結(jié)點(diǎn) { stack.push(p);//p結(jié)點(diǎn)入棧 p=p.left;//進(jìn)入左子樹 } else//若p為空且棧不空,表示已經(jīng)走完了一條路徑,則需返回尋找下一條路徑。而返回的結(jié)點(diǎn)就是剛剛經(jīng)過的最后一個結(jié)點(diǎn),即是根結(jié)點(diǎn)root,使指針p指向它,訪問p結(jié)點(diǎn),再進(jìn)入p的右子樹。 { p=stack.pop();// System.out.print(p.data+""); p=p.right;//進(jìn)入右子樹 } System.out.println(); }publicvoidpreOrderTraverse(){//先根次序遍歷的非遞歸算法 LinkedStack<BinaryNode<T>>stack=newLinkedStack();//創(chuàng)造空的鏈?zhǔn)綏４鎯Χ鏄浣Y(jié)點(diǎn)BinaryNode<T> }publicvoidpostOrderTraverse(){//后根次序遍歷的非遞歸算法 LinkedStack<BinaryNode<T>>stack=newLinkedStack();//創(chuàng)造空的鏈?zhǔn)綏４鎯Χ鏄浣Y(jié)點(diǎn)BinaryNode<T> }publicvoidleaf(){//遍歷輸出葉子結(jié)點(diǎn) leaf(root);}publicvoidleaf(BinaryNode<T>p){//先根次序遍歷,輸出葉子結(jié)點(diǎn),3種遍歷次序的結(jié)果都一樣 if(p!=null){ if(p.isLeaf()) System.out.print(p.data+""); leaf(p.left); leaf(p.right); }}publicintgetLeaves(){//求一棵二叉樹中所有葉子結(jié)點(diǎn)的個數(shù) returngetLeaves(root);}publicintgetLeaves(BinaryNode<T>p){//求一棵二叉樹葉子結(jié)點(diǎn)的個數(shù) if(p==null) return0; if(p.isLeaf()) return1;returngetLeaves(p.left)+getLeaves(p.right);}//以先根和中根次序遍歷序列構(gòu)造二叉樹publicBinaryTree(T[]prelist,T[]inlist)//以先根和中根次序遍歷序列構(gòu)造二叉樹{ this.root=create(prelist,inlist,0,0,prelist.length);}//以先根和中根序列創(chuàng)造一棵子樹,子樹根結(jié)點(diǎn)值是prelist[preStart],n指定子序列的長度,返回//所創(chuàng)建的子樹的根結(jié)點(diǎn)privateBinaryNode<T>create(T[]prelist,T[]inlist,intpreStart,intinStart,intn){ if(n<=0) returnnull; Telem=prelist[preStart];//臨時變量elem存儲子樹根結(jié)點(diǎn)值prelist[preStart] BinaryNode<T>p=newBinaryNode<T>(elem);//創(chuàng)建葉子結(jié)點(diǎn) inti=0;// while(i<n&&!elem.equals(inlist[inStart+i])){//在中根序列中尋找根結(jié)點(diǎn)的所在位置 i++;p.left=create(prelist,inlist,preStart+1,inStart,i);//創(chuàng)建p的左子樹p.right=create(prelist,inlist,preStart+i+1,inStart+i+1,n-1-i);//創(chuàng)建p的右子樹 }returnp;}//標(biāo)明空子樹的先根遍歷序列構(gòu)造二叉樹publicBinaryTree(T[]prelist){//Tprelist[]數(shù)組保存二叉樹的先根遍歷序列 this.root=create(prelist);//create(prelist)方法創(chuàng)建一棵二叉樹的子樹}//以標(biāo)明空子樹的先根遍歷序列構(gòu)造二叉樹//以標(biāo)明空子樹的先根遍歷序列構(gòu)造一棵子二叉樹,子二叉樹的根結(jié)點(diǎn)值是prelist[i],返回所創(chuàng)建的子二叉樹的根結(jié)點(diǎn)privateinti=0;//私有成員變量(全局變量)i,由于參數(shù)按層次變化,因此i同時充當(dāng)計(jì)數(shù)變量privateBinaryNode<T>create(T[]prelist)//create(Tprelist[])是遞歸方法{ BinaryNode<T>p=null;//二叉樹結(jié)點(diǎn)指針p初始化為空 if(i<prelist.length)//i的值從