數據結構實驗三-二叉樹的實現2023

實驗報告課程名稱數據結構實驗名稱二叉樹的實現系別專業(yè)班級指導教師學號姓名實驗日期實驗成績一、實驗目的掌握二叉樹的邏輯結構；掌握二叉樹的二叉鏈表存儲結構；驗證二叉樹的二叉鏈表存儲及遍歷操作。二、實驗內容建立一棵含有n個結點的二叉樹，采用二叉鏈表存儲；結點序列由鍵盤輸入！輸出前序、中序和后序遍歷該二叉樹的遍歷結果。輸出二叉樹的葉子個數及葉子名稱。三、設計與編碼1.本實驗用到的理論知識2.算法設計3.編碼生成樹編碼：publicclassBiTree{ publicBiTreeNoderoot; publicBiTree(){ this.root=null; } publicBiTree(BiTreeNoderoot){ this.root=root; } publicstaticintindex=0; publicBiTree(StringpreStr){ charc=preStr.charAt(index++); if(c!='#'){ root=newBiTreeNode(c); root.lchild=newBiTree(preStr).root; root.rchild=newBiTree(preStr).root; }else root=null; } publicvoidpreRootTraverse(BiTreeNodeT){ if(T!=null){ System.out.print(T.data); preRootTraverse(T.lchild); preRootTraverse(T.rchild); } } publicvoidpreRootTraverse(){ BiTreeNodeT=root; if(T!=null){ LinkStackS=newLinkStack(); S.push(T); while(!S.isEmpty()){ T=(BiTreeNode)S.pop(); System.out.print(T.data+""); while(T!=null){ if(T.lchild!=null) System.out.print(T.lchild.data+""); if(T.rchild!=null) S.push(T.rchild); T=T.lchild; } } } } publicvoidinRootTraverse(BiTreeNodeT){ if(T!=null){ inRootTraverse(T.lchild); System.out.print(T.data); inRootTraverse(T.rchild); } } publicvoidineRootTraverse(){ BiTreeNodeT=root; if(T!=null){ LinkStackS=newLinkStack(); S.push(T); while(!S.isEmpty()){ while(S.peek()!=null) S.push(((BiTreeNode)S.peek()).lchild); S.pop(); if(!S.isEmpty()){ T=(BiTreeNode)S.pop(); System.out.print(T.data+""); S.push(T.rchild); } } } } publicvoidpostRootTraverse(BiTreeNodeT){ if(T!=null){ postRootTraverse(T.lchild); postRootTraverse(T.rchild); System.out.print(T.data); } }publicvoidpostRootTraverse(){ BiTreeNodeT=root; if(T!=null){ LinkStackS=newLinkStack(); S.push(T); Booleanflag; BiTreeNodep=null; while(!S.isEmpty()){ while(S.peek()!=null) S.push(((BiTreeNode)S.peek()).lchild); S.pop(); while(!S.isEmpty()){ T=(BiTreeNode)S.peek(); if(T.rchild==null||T.rchild==p){ System.out.print(T.data+""); S.pop(); p=T; flag=true; }else{ S.push(T.rchild); flag=false; } if(!flag) break; } } } }publicintleafNum(BiTreeNodet){ if(t==null){ return0; } else{ intln=leafNum(t.lchild); intrn=leafNum(t.rchild); if(t.lchild==null&&t.rchild==null){ returnln+rn+1; } else{ returnln+rn; } }}publicvoidprintTreeLeaf(BiTreeNodet){if(t!=null){ printTreeLeaf(t.lchild); printTreeLeaf(t.rchild); if(t.lchild==null&&t.rchild==null){ System.out.print(t.data+"");; } }}}測試編碼：packagebitree;importjava.util.Scanner;publicclassTest{ publicstaticvoidmain(String[]args){ System.out.println("請輸入標明空子樹的先根遍歷序列："); Scannersc=newScanner(System.in);StringpreStr=sc.next();BiTreeT=newBiTree(preStr);System.out.println("先根遍歷輸出：");T.preRootTraverse();System.out.println();System.out.println("中根遍歷輸出：");T.ineRootTraverse();System.out.println();System.out.println("后根遍歷輸出：");T.postRootTraverse();System.out.println();System.out.println("葉子節(jié)點數"+T.leafNum(T.root));System.out.print("葉子節(jié)點：");T.printTreeLeaf(T.root);}}4、畫出實驗中使用的二叉樹圖形。（要求每個同學自行設計三個二叉樹，節(jié)點不少于6個，雷同者本次實驗無成績）四、運行與調試1.在調試程序的過程中遇到什么問題，是如何解決的？問題：出現字符串索引越界原因：二叉樹的先根遍歷序列錯誤。解決辦法：更正為正確的先根序列ACBD###C##。2.設計了哪些測試數據？預計結果是什么？Char數據：其先根序列分別為1.1248###59#