搜索
武汉纺织大学《数据结构》实验报告班级：级专业班姓名：序号：01实验时间：2014年5月4日指导教师：实验二：二叉树操作及应用一、实验目的：1、掌握二叉树的基本概念、基本操作以及各种存储结构。2、掌握二叉树的多种遍历方法。2、掌握哈夫曼树以及哈夫曼编码的求取过程。二、实验内容：1、编写一个程序，生成一棵二叉树并进行基本操作。实验步骤：①、在Java语言编辑环境中新建程序，输入程序内容，并保存和编译；②、运行程序，从键盘输入二叉树各个结点数据，参考书本173页【例6.1】；③、显示菜单如下：1——先序遍历2——中序遍历3——后序遍历4——层次遍历5——求结点总数6——求高度0——退出④、输入菜单选项，进行相应操作并输出结果。⑤可参考程序为：172页先序、中序、后序遍历；174页求结点个数、求高度；185页层次遍历。2、编写一个程序，构造哈夫曼树并获取哈夫曼编码。实验步骤：①、在Java语言编辑环境中新建程序，参考书本205-207页程序内容，并保存和编译；②、运行程序，根据指定权值，建立哈夫曼树；③、输出哈夫曼树存储结构信息；④、输出各个哈夫曼编码。⑤、如有能力，请将此程序修改为：从键盘上输入权值，并构造哈夫曼树、获取哈夫曼编码。3、编写程序，实现对二叉树的中序线索化操作。实验步骤：①、在Java语言编辑环境中新建程序，参考书本190-193页程序内容，并保存和编译；②、运行程序，建立二叉树存储结构；③、对二叉树进行中序线索化，建立中序线索二叉树；④、输出中序遍历序列。三、操作步骤：代码：packageBinaryTree;importjava.util.Scanner;publicclassBinaryTree_make{publicstaticvoidmain(Stringargs[]){Scannerreader=newScanner(System.in);System.out.print(请输入结点个数：);intnumber=reader.nextInt();System.out.print(请输入各个结点数据：);intt=0;String[]prelist=newString[number];for(t=0;tnumber;t++){prelist[t]=reader.next();}BinaryTreeStringbitree=newBinaryTreeString(prelist);System.out.println(本程序功能菜单如下，请选择输入：);System.out.println(1——先序遍历);System.out.println(2——中序遍历);System.out.println(3——后序遍历);System.out.println(4——层次遍历);System.out.println(5——求结点总数);System.out.println(6——求高度);System.out.println(0——退出);intnum=-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());}else{System.out.println(您输入的值超出范围！);}}}}}}}if(num==0){System.out.println(退出程序);}}}四、实验收获和建议：