数据结构实验三-二叉树的实现2017.doc

实 验 报 告课程名称 数据结构 实验名称 二叉树的实现 系别 专业班级 指导教师 学号 姓名 实验日期 实验成绩 一、实验目的(1) 掌握二叉树的逻辑结构；(2) 掌握二叉树的二叉链表存储结构；(3) 验证二叉树的二叉链表存储及遍历操作。二、实验内容(1) 建立一棵含有n个结点的二叉树，采用二叉链表存储；结点序列由键盘输入！(2) 输出前序、中序和后序遍历该二叉树的遍历结果。(3) 输出二叉树的叶子个数及叶子名称。三、设计与编码1.本实验用到的理论知识2.算法设计3.编码生成树编码：public class BiTree public BiTreeNode root;public BiTree()this.root=null;public BiTree(BiTreeNode root)this.root=root;public static int index=0; public BiTree(String preStr)char c=preStr.charAt(index+);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)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+ ); while(T!=null) if(T.lchild!=null) System.out.print(T.lchild.data+ ); 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(); 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); public void postRootTraverse(BiTreeNode T) if(T!=null)postRootTraverse(T.lchild);postRootTraverse(T.rchild);System.out.print(T.data); public void postRootTraverse() BiTreeNode T=root; if(T!=null) LinkStack S=new LinkStack(); S.push(T); Boolean flag; BiTreeNode p=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; public int leafNum(BiTreeNode t) if(t=null) return 0; else int ln=leafNum(t.lchild); int rn=leafNum(t.rchild); if(t.lchild=null&t.rchild=null) return ln+rn+1; else return 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+ ); 测试编码：package bitree;import java.util.Scanner;public class Test public static void main(String args) System.out.println(请输入标明空子树的先根遍历序列：);Scanner sc=new Scanner(System.in); String preStr=sc.next(); BiTree T=new BiTree(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#0#36#7#2. ABDH#I#E#C