《数据结构实验三-二叉树的实现2017》由会员分享，可在线阅读，更多相关《数据结构实验三-二叉树的实现2017（8页珍藏版）》请在金锄头文库上搜索。
1、实 验 报 告课程名称 数据结构 实验名称 二叉树的实现 系别 专业班级 指导教师 学号 姓名 实验日期 实验成绩 一、实验目的(1) 掌握二叉树的逻辑结构；(2) 掌握二叉树的二叉链表存储结构；(3) 验证二叉树的二叉链表存储及遍历操作。二、实验内容(1) 建立一棵含有n个结点的二叉树，采用二叉链表存储；结点序列由键盘输入！(2) 输出前序、中序和后序遍历该二叉树的遍历结果。(3) 输出二叉树的叶子个数及叶子名称。三、设计与编码1.本实验用到的理论知识2.算法设计3.编码生成树编码：public class BiTree public BiTreeNode root;public BiTre
2、e()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(BiTreeNo
3、de 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) S
4、ystem.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();
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+ ); S.push(T.rchild); public void postRootTraverse(BiTreeNode T) if(T!=null)postRootTraverse(T.lchild);postRootTraverse(T.rchild);System.out
6、.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.r
7、child=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 v
8、oid 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 s
9、c=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(); Sys
10、tem.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#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个字母设计哈夫曼编码。考虑到公司仍有部分低层及高层人员的补充，因此在选择招聘渠道供应商的附加值时以配送普工现场招聘会和高端人才交流会为佳，另外根据供应商平台实力，若能给公司提供
