数据结构实验三-二叉树的实现2023

实验报告课程名称数据结构实验名称二叉树的实现系别专业班级指导教师学号姓名实验日期实验成绩一、实验目的掌握二叉树的逻辑结构；掌握二叉树的二叉链表存储结构；验证二叉树的二叉链表存储及遍历操作。二、实验内容建立一棵含有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("叶子节点数"+T.leafNum(T.root));System.out.print("叶子节点：");T.printTreeLeaf(T.root);}}4、画出实验中使用的二叉树图形。（要求每个同学自行设计三个二叉树，节点不少于6个，雷同者本次实验无成绩）四、运行与调试1.在调试程序的过程中遇到什么问题，是如何解决的？问题：出现字符串索引越界原因：二叉树的先根遍历序列错误。解决办法：更正为正确的先根序列ACBD###C##。2.设计了哪些测试数据？预计结果是什么？Char数据：其先根序列分别为1.1248###59#