《数据结构实验三-二叉树的实现2017》由会员分享，可在线阅读，更多相关《数据结构实验三-二叉树的实现2017（9页珍藏版）》请在装配图网上搜索。
1、. . .实 验 报 告课程名称 数据结构 实验名称 二叉树的实现 系别专业班级指导教师学号实验日期实验成绩一、实验目的(1) 掌握二叉树的逻辑结构；(2) 掌握二叉树的二叉链表存储结构；(3) 验证二叉树的二叉链表存储与遍历操作。二、实验容(1) 建立一棵含有n个结点的二叉树，采用二叉链表存储；结点序列由键盘输入！(2) 输出前序、中序和后序遍历该二叉树的遍历结果。(3) 输出二叉树的叶子个数与叶子名称。三、设计与编码1.本实验用到的理论知识2.算法设计3.编码生成树编码：public class BiTree public BiTreeNode root;public BiTree()th
2、is.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)
3、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
4、.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.pus
5、h(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.prin
6、t(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
7、=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 p
8、rintTreeLeaf(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
9、 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.o
10、ut.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#CFJ#G#3. 12#46#80#35#79#3#4. abeh#i#dj#b#cfl#m#gn#o# 3. 程序运行的结果如何五、总结与心得六、思考题(1) 试将如下森林转为二叉树。(2)假设用于通讯的电文仅由6个字母组成，字母在电文中出现的频率分别为：7，9，2，6，32，3。试为这6个字母设计哈夫曼编码。9 / 9
数据结构实验三-二叉树的实现2017
