武汉纺织大学《数据结构》实验报告

1、武汉纺织大学数据结构实验报告班级： 级 专业 班 姓名： 序号： 01 实验时间： 2014 年 5 月 4 日 指导教师： 实验二：二叉树操作及应用一、实验目的：1、掌握二叉树的基本概念、基本操作以及各种存储结构。2、掌握二叉树的多种遍历方法。2、掌握哈夫曼树以及哈夫曼编码的求取过程。二、实验内容： 1、编写一个程序，生成一棵二叉树并进行基本操作。 实验步骤： 、在Java语言编辑环境中新建程序，输入程序内容，并保存和编译； 、运行程序，从键盘输入二叉树各个结点数据，参考书本173页【例6.1】； 、显示菜单如下： 1先序遍历 2中序遍历 3后序遍历 4层次遍历 5求结点总数 6求高度 0退

2、出 、输入菜单选项，进行相应操作并输出结果。 可参考程序为：172页先序、中序、后序遍历；174页求结点个数、求高度；185页层次遍历。 2、编写一个程序，构造哈夫曼树并获取哈夫曼编码。 实验步骤： 、在Java语言编辑环境中新建程序，参考书本205-207页程序内容，并保存和编译； 、运行程序，根据指定权值，建立哈夫曼树； 、输出哈夫曼树存储结构信息； 、输出各个哈夫曼编码。 、如有能力，请将此程序修改为：从键盘上输入权值，并构造哈夫曼树、获取哈夫曼编码。 3、编写程序，实现对二叉树的中序线索化操作。实验步骤： 、在Java语言编辑环境中新建程序，参考书本190-193页程序内容，并保存和编

3、译； 、运行程序，建立二叉树存储结构； 、对二叉树进行中序线索化，建立中序线索二叉树； 、输出中序遍历序列。三、操作步骤：代码：package BinaryTree;import java.util.Scanner;public class BinaryTree_make public static void main(String args) Scanner reader = new Scanner(System.in);System.out.print(请输入结点个数：);int number = reader.nextInt();System.out.print(请输入各个结点数据：);

4、int t = 0;String prelist = new Stringnumber;for (t = 0; t number; t+) prelistt = reader.next();BinaryTree bitree = new BinaryTree(prelist);System.out.println(本程序功能菜单如下，请选择输入：);System.out.println(1先序遍历);System.out.println(2中序遍历);System.out.println(3后序遍历);System.out.println(4层次遍历);System.out.println(5

5、求结点总数);System.out.println(6求高度);System.out.println(0退出);int num = -1;while (num != 0) num = reader.nextInt();if (num = 1) bitree.preOrder(); else if (num = 2) bitree.inOrder(); else if (num = 3) bitree.postOrder(); else if (num = 4) bitree.levelOrder(); else if (num = 5) System.out.println(二叉树结点总数： + bitree.count(); else if (num = 6) System.out.println(二叉树的高度： + bitree.height(); e