数据结构实验三

1、实验报告课程名称数据结构实验名称二叉树的实现系别专业班级指导教师学号实验日期实验成绩一、实验目的(1) 掌握二叉树的逻辑结构；(2) 掌握二叉树的二叉链表存储结构；(3) 验证二叉树的二叉链表存储及遍历操作。二、实验容(1) 建立一棵含有n个结点的二叉树，采用二叉链表存储；结点序列由键盘输入!(2) 输出前序、中序和后序遍历该二叉树的遍历结果。(3) 输出二叉树的叶子个数及叶子名称。三、设计与编码1.本实验用到的理论知识2 算法设计3 编码生成树编码：public class BiTree public BiTreeNode root；public BiTree() this root二nul

2、l；public BiTree(BiTreeNode root) this root二root；public static int index=0；public BiTree (String preStr)char c=preStr. charAt；if(c! = #) root二new BiTreeNode(c)；root.lchild=new BiTree(preStr). root；root rchild二new BiTree(preStr) root； elseroot二null；public void preRootTraverse(BiTreeNode T) if(T!=null)

3、 System out print(T data)； preRootTraverse(T lchild)； preRootTraverse(T. rchild)； public void preRootTraverse()BiTreeNode T二root； if(T!二null) LinkStack S二new LinkStack()；S. push(T)； while(!S. isEmpty() T= (BiTreeNode) S. pop()；System out. print (T data+n ”)； while(T!=null) if(T. lchild!=null)System

4、out print (T. lchild data+r, ”)； if(T. rchild!=null)S. push(T. rchild)；T二T lchild；public void inRootTraverse(BiTreeNode T)if(T!二null) inRootTraverse(T lchild)；System out. print (T. data)； inRootTraverse(T. rchild)；public void ineRootTraverse() BiTreeNode T=root；if(T!二null) LinkStack S二new LinkStack(

5、)；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+rr)；S push(T. rchild)；public void postRootTraverse(BiTreeNode T)if(T!二null) postRootTraverse(T lch订d)； postRootTraverse(T. rchild)

6、； System out. print (T. data)；public void postRootTraverse()BiTreeNode T二root；if(T!=null)LinkStack S=new LinkStackO ；S push(T)；Boolean flag；BiTreeNode p二null； while(!S. isEmpty() while(S. peek() !=null)S. push (BiTreeNode) S. peek (). lch订d)； S pop();while(!S. isEmpty() T= (BiTreeNode) S. peek()；if(

7、T. rchild=null丨 |T.rchild二二p) System, out. print (T. data+ ” ”)；S. pop()；P=T；flag二true；elseS. push(T. rchild)；flag=false；if (! flag)break；public int leafNum(BiTreeNode t) if (t=null) return 0；elseint ln=leafNum(t. lchild)；int rn=leafNum(t.rchild)；if(t. lchild=二null&t. rchild=二null) return ln+rn+1；el

8、sereturn ln+rn；public void printTreeLeaf(BiTreeNode t) if(t!=null)printTreeLeaf(t. lchild)； printTreeLeaf (t rchild)； if(t. lchild=null&t. rchild=null) System out print(t data+u ”)；测试编码:package bitree；import java.util. Seanner； public class Test public static void main(StringEJ args) System, out. pr

9、int In (请输入秣明空子树的先根遍历序列：); Sea rrner sc二new Sea rm er(System in)；String preStr二sc next()；BiTree T二new BiTree(preStr)；System, out. print In (先根遍历输 出：“)；T preRootTraverse ()；System out printlnO ；System, out. printin(,r 中根遍历输出：)；T ineRootTraverse()；System out println()；System, out. printin (n 后根遍历输出：)；

10、T postRootTraverse ()；System out printlnO ;System, out. printin (，r 叶子节点数+T. leaf Num (T. root):System out. print (口十子节/占：n)；T. printTreeLeaf (T. root)；4、画出实验中使用的二叉树图形。(要求每个同学自行设计三个二叉树，节点不少于6个，雷同者本次实验无成绩)四、运行与调试1. 在调试程序的过程中遇到什么问题，是如何解决的? 问题：出现字符串索引越界6 Console 勿 X 场 I 直 Test (9)丿妙。Applicatkjnl C:Prog

11、ram File$Vavajdk1.0.0_112bmjsvaw.exe (2017年5月24日上午2:18:19) 诸输入标明空子捋的先根週历宇列，ACBD#CException in thread main javalangSt广inglndexOirtOfBoundsException: String index out of 广ange: 8 at javalangStringcharAt(String.java:658) at bitree. BiTre已 (BiTge java: 17) at bitree.BiTre已.cinitCBiTFee.java:20) at bitre

12、e BiTree (BiT厂ee jaua :21) at bitree.BiTrew/BiTree.java:2e6 at bitree .Test main( Test java: 9)原因：二叉树的先根遍历序列错误。解决办法：更正为正确的先根序列ACBD#C*。2设计了哪些测试数据？预计结果是什么？Chat数据：其先根序列分别为1. 1248#tt59#0#tt36#7#tt2. ABDHtttt I #E#CF3. 12#46#80#35#79#3#4 abehttfti ttftd j #b#c f 1 ttttmttttgnttttotttt3 程序运行的结果如何冃 Console

13、 S3terminated a Test Java Application C:请输入标明空手树的先根遍历序列1248#59#0#36#7#忧根遍历输出：1248590367中根遍历输岀：8429501637后根遍历输出，8490526731叶子节点数；5叶子节点：8 9 0 6 7曰 Console 為 Test (9) Java Application C:请输入标明空子树的先根泄历序列：ABDH#I#E#CF：#G#先根適历输出，ABDHIECFJG中根遍历输出：HDIBEAJFCG后根遍历输出；HIDEB3FGCA 叶子节点数：5叶子节点，H I E J G貝 Console S3terminated Test (9) Java Application C: 请谕入标明空子树的先根遍历序列，12#46#80#35#79#3#先根遍历输出；12468035793中根遍历输出：26084159373后根遍历输出：贞狀 08642397531叶子节点数，2叶子节点：0 3 Console S3 Test (9) Java Application C:Program Files 请输入标明空子树的先根適历序列， abeh#i#dj#b