武汉纺织大学数据结构实验报告2.doc

《武汉纺织大学数据结构实验报告2.doc》由会员分享，可在线阅读，更多相关《武汉纺织大学数据结构实验报告2.doc（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、武汉纺织大学数据结构实验报告班级： 专业 班 姓名： 序号： 实验时间： 年 月 日 指导教师： 实验二：二叉树操作及应用一、实验目的：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、存储结构； 、对二叉树进行中序线索化，建立中序线索二叉树； 、输出中序遍历序列。三、操作步骤：1.二叉树（1）接口类BinaryTTree.javapackage tree;public interface BinaryTTree /二叉树接口，二叉树抽象数据类型boolean isEmpty();/判断二叉树是否为空int count();/返回二叉树的结点个数int height();/返回二叉树的高度void preOrder();/先根次序遍历二叉树void inOrder();/中根次序遍历二叉树void postOrder();/后根次序遍历二叉树void levelOrder()

4、;/按层次遍历二叉树BinaryNode search(T key);/查找并返回首次出现的关键字为key元素结点BinaryNode getParent(BinaryNode node);/返回node的父母结点void insertRoot(T x);/插入元素x作为根节点BinaryNode insertChild(BinaryNode p,T x,boolean leftChild);/插入孩子节点void removeChild(BinaryNode p,boolean leftChild);/删除p结点的左或右子树void removeAll();/删除二叉树（2）二叉链表结点类B

5、inaryNode.javapackage tree;public class BinaryNode /二叉树的二叉链表结点类public T data;/数据域，存储数据元素public BinaryNode left,right;/链域，分别指向左、右孩子结点/构造结点，参数分别指定元素和左、右孩子结点public BinaryNode(T data,BinaryNodeleft,BinaryNode right)this.data = data;this.left = left;this.right = right;public BinaryNode(T data)this(data,n

6、ull,null);/构造指定值的叶子节点public BinaryNode()this(null,null,null);（3）二叉树类BinaryTree.javapackage tree;/二叉树类，实现BinaryTree接口，泛型T指定节点的元素类型public class BinaryTree implements BinaryTTree public BinaryNode root;public BinaryTree()this.root = null;public boolean isEmpty() return this.root=null;public int count()

7、 return count(root);public int count(BinaryNode p)if(p=null)return 0;return 1+count(p.left)+count(p.right);public int height() return height(root);public int height(BinaryNode p)if(p = null)return 0;int lh = height(p.left);int rh = height(p.right);return (lhrh)?lh+1:rh+1;public void preOrder() Syste

8、m.out.print(先根次序遍历: );preOrder(root);System.out.println();public void preOrder(BinaryNode p)if(p!=null)System.out.print(p.data.toString()+ );preOrder(p.left);preOrder(p.right);public void inOrder() System.out.print(中根次序遍历: );inOrder(root);System.out.println();public void inOrder(BinaryNode p)if(p !=

9、 null)inOrder(p.left);System.out.print(p.data.toString()+ );inOrder(p.right);public void postOrder() System.out.print(后根次序遍历: );postOrder(root);System.out.println();public void postOrder(BinaryNode p)if(p != null)postOrder(p.left);postOrder(p.right);System.out.print(p.data.toString()+ );public void

10、levelOrder() /按层次遍历二叉树LinkedQueueBinaryNode que = new LinkedQueueBinaryNode();/创建空队列BinaryNode p = this.root;System.out.print(层次遍历: );while(p != null)System.out.print(p.data+ );if(p.left != null)que.enqueue(p.left);/p的左孩子结点入队if(p.right != null)que.enqueue(p.right);/p的右孩子结点入队p = que.dequeue();/p指向出队结

11、点，若队列空返回nullSystem.out.println();（4）使用二叉树UseBinaryTree.javapackage tree;import java.util.Scanner;/* * * author pang * */public class UseBinaryTree public static BinaryTree make(String a,String b,String c,String d,String e,String f,String g,String h)BinaryTree bitree = new BinaryTree();BinaryNode chi

12、ld_f,child_d,child_b,child_c;child_d = new BinaryNode(d,null,new BinaryNode(g);child_b = new BinaryNode(b,child_d,null);child_f = new BinaryNode(f,new BinaryNode(h),null);child_c = new BinaryNode(c,new BinaryNode(e),child_f);bitree.root = new BinaryNode(a,child_b,child_c);return bitree;public static

13、 void main(String args)System.out.println(请输入结点数据：);Scanner scan = new Scanner(System.in);String a = scan.next();String b = scan.next();String c = scan.next();String d = scan.next();String e = scan.next();String f = scan.next();String g = scan.next();String h = scan.next();BinaryTree bitree = make(a

14、,b,c,d,e,f,g,h);System.out.println(1-先序遍历n2-中序遍历n3-后序遍历n4-层次遍历n5-求结点总数n6-求高度n0-退出);System.out.println(输入菜单选项，进行相应操作并输出结果);while (true) int number = scan.nextInt();operate(bitree,number);/菜单功能方法public static void operate(BinaryTree bitree,int a)switch(a)case 1:bitree.preOrder();break;case 2:bitree.in

15、Order();break;case 3:bitree.postOrder();break;case 4:bitree.levelOrder();break;case 5:System.out.println(二叉树结点数： +bitree.count();break;case 6:System.out.println(二叉树高度： +bitree.height();break;case 0:System.exit(0);default:System.out.println(请正确输入指令！);（5）注意事项二叉树类BinaryTree.java中有用到队列部分内容，需要导入包或者将该部分文件

16、放入tree包中才能使用（6）运行结果：2.哈夫曼树（1）二叉树的静态三叉链表结点类TriElement.javapackage huffman;public class TriElement /二叉树的三叉静态链表结点类int data;/数据域，表示权值int parent,left,right;/父母结点和左、右孩子结点下标public TriElement(int data,int parent,int left,int right)this.data = data;this.parent = parent;this.left = left;this.right = right;pub

17、lic TriElement(int data)this(data,-1,-1,-1);public TriElement()this(0);public String toString()return (+this.data+,+this.parent+,+this.left+,+this.right+);（2）哈夫曼树类HuffmanTree.javapackage huffman;public class HuffmanTree /Huffman树private int leafNum;/叶子结点private TriElement huftree;/Huffman树的结点数组publi

18、c HuffmanTree(int weight)/构造指定权值集合的Huffman树int n = weight.length;/n个叶子结点this.leafNum = n;this.huftree = new TriElement2*n-1;/n个叶子结点的Huffman树共有2n-1个结点for(int i=0;in;i+)/结点数组初始化有n个叶子结点this.huftreei = new TriElement(weighti);for(int i=0;in-1;i+)/构造n-1个2度将结点，每次循环构造1个2度结点int min1=Integer.MAX_VALUE,min2=m

19、in1;/最小和次最小权值，初值为整数最大值int x1=-1,x2=-1;/记录两个无父母的最小权值结点下标for(int j=0;jn+i;j+)/查找两个无父母的最小权值结点if(huftreej.datamin1 & huftreej.parent=-1)min2 = min1;x2 = x1;min1 = huftreej.data;/min1记下最小权值x1 = j;/x1记下最小权值结点的下标else if(huftreej.datamin2 & huftreej.parent=-1)min2 = huftreej.data;x2 = j;/x2记下次最小权值结点的下标huftr

20、eex1.parent = n+i;/将找出的两棵权值最小的子树合并为一棵子树huftreex2.parent = n+i;this.huftreen+i = new TriElement(huftreex1.data+huftreex2.data,-1,x1,x2);public String toString()String str=Huffman树的结点数组：n;for(int i=0;ithis.huftree.length&huftreei!=null;i+)str += 第+i+行+this.huftreei.toString()+n;return str;public Strin

21、g huffmanCodes()/返回当前Huffman树的Huffman编码String hufcodes = new Stringthis.leafNum;for(int i=0;ithis.leafNum;i+)/求n个叶子结点的Huffman编码hufcodesi = ;int child = i;int parent = huftreechild.parent;while(parent != -1)/由叶子结点向上直到根节点循环if(huftreeparent.left = child)hufcodesi=0+hufcodesi;/左孩子结点编码为0elsehufcodesi=1+h

22、ufcodesi;/右孩子结点编码为1child = parent;parent = huftreechild.parent;return hufcodes;（3）获取哈夫曼编码HuffmanTree_example.javapackage huffman;import java.util.Scanner;import Josephus.SeqList;/* * * author pang * */public class HuffmanTree_example public static void main(String args)SeqList list = new SeqList();S

23、ystem.out.println(请依次输入权值并以0结束作为标识);Scanner scan = new Scanner(System.in);while(true)int x = scan.nextInt();if(x != 0)list.append(x);elsebreak;int weight = new intlist.length();for(int i = 0;ilist.length();i+)weighti = list.get(i);HuffmanTree htree = new HuffmanTree(weight);System.out.print(htree.to

24、String();String code = htree.huffmanCodes();System.out.print(Huffman编码： n);for(int i = 0;icode.length;i+)System.out.println(char)(A+i)+: +codei+ );（4）注意事项从键盘输入权值且不确定个数，需要一个标识符，这里用了0作为标识符。使用到了线性表部分内容，需要导入包或将文件放入此包中。（5）运行结果：3.二叉树的中序线索化（1）二叉链表结点类ThreadNode.javapackage threadBinaryTree;public class Thre

25、adNode public T data;public ThreadNode left,right;public int ltag,rtag;public ThreadNode(T data,ThreadNode left,int ltag,ThreadNode right,int rtag)this.data = data;this.left = left;this.ltag = ltag;this.right = right;this.rtag = rtag;public ThreadNode(T data) this(data,null,0,null,0);public ThreadNo

26、de() this(null,null,0,null,0);（2）中序线索二叉树类ThreadBinaryTree.javapackage threadBinaryTree;public class ThreadBinaryTree public ThreadNode root;public ThreadBinaryTree() this.root = null;public boolean isEmpty() return root = null;public ThreadBinaryTree(T prelist)this.root = create(prelist);inorderThre

27、ad(this.root);private int i = 0;private ThreadNode create(T prelist) ThreadNode p = null;if (i prelist.length) T elem = prelisti+;if (elem != null) p = new ThreadNode(elem);p.left = create(prelist);p.right = create(prelist);return p;private ThreadNode front=null;private void inorderThread(ThreadNode

28、 p)if(p!=null)inorderThread(p.left);if(p.left=null)p.ltag=1;p.left=front;if(p.right=null)p.rtag=1;if(front!=null&front.rtag=1)front.right=p;front=p;inorderThread(p.right);public ThreadNode inNext(ThreadNode p)if(p.rtag=1)p=p.right;elsep=p.right;while(p.ltag=0)p=p.left;return p;public void inOrder()S

29、ystem.out.print(中根次序遍历中序线索二叉树： );ThreadNode p = this.root;while(p!=null&p.ltag=0)p=p.left;while(p!=null)System.out.print(p.data.toString()+ );p=inNext(p);System.out.println();（3）中跟次序遍历package threadBinaryTree;public class ThreadBinaryTree_ex public static void main(String args)String prelist = A,B,D,null,null,E,G,null,null,null,C,F,null,H,null,null,K;ThreadBinaryTree tbitree = new ThreadBinaryTree(prelist);tbitree.inOrder();（4）运行结果：四、实验收获和建议：