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

武汉纺织大学数据结构实验报告班级： 专业 班 姓名： 序号： 实验时间： 年 月 日 指导教师： 实验二：二叉树操作及应用一、实验目的：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页程序内容，并保存和编译； 、运行程序，建立二叉树存储结构； 、对二叉树进行中序线索化，建立中序线索二叉树； 、输出中序遍历序列。三、操作步骤：1.二叉树（1）接口类BinaryTTree.javapackage tree;public interface BinaryTTree<T> /二叉树接口，二叉树抽象数据类型boolean isEmpty();/判断二叉树是否为空int count();/返回二叉树的结点个数int height();/返回二叉树的高度void preOrder();/先根次序遍历二叉树void inOrder();/中根次序遍历二叉树void postOrder();/后根次序遍历二叉树void levelOrder();/按层次遍历二叉树BinaryNode<T> search(T key);/查找并返回首次出现的关键字为key元素结点BinaryNode<T> getParent(BinaryNode<T> node);/返回node的父母结点void insertRoot(T x);/插入元素x作为根节点BinaryNode<T> insertChild(BinaryNode<T> p,T x,boolean leftChild);/插入孩子节点void removeChild(BinaryNode<T> p,boolean leftChild);/删除p结点的左或右子树void removeAll();/删除二叉树（2）二叉链表结点类BinaryNode.javapackage tree;public class BinaryNode<T> /二叉树的二叉链表结点类public T data;/数据域，存储数据元素public BinaryNode<T> left,right;/链域，分别指向左、右孩子结点/构造结点，参数分别指定元素和左、右孩子结点public BinaryNode(T data,BinaryNode<T>left,BinaryNode<T> right)this.data = data;this.left = left;this.right = right;public BinaryNode(T data)this(data,null,null);/构造指定值的叶子节点public BinaryNode()this(null,null,null);（3）二叉树类BinaryTree.javapackage tree;/二叉树类，实现BinaryTree<T>接口，泛型T指定节点的元素类型public class BinaryTree<T> implements BinaryTTree<T> public BinaryNode<T> root;public BinaryTree()this.root = null;public boolean isEmpty() return this.root=null;public int count() return count(root);public int count(BinaryNode<T> p)if(p=null)return 0;return 1+count(p.left)+count(p.right);public int height() return height(root);public int height(BinaryNode<T> p)if(p = null)return 0;int lh = height(p.left);int rh = height(p.right);return (lh>rh)?lh+1:rh+1;public void preOrder() System.out.print("先根次序遍历: ");preOrder(root);System.out.println();public void preOrder(BinaryNode<T> 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<T> p)if(p != 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<T> p)if(p != null)postOrder(p.left);postOrder(p.right);System.out.print(p.data.toString()+" ");public void levelOrder() /按层次遍历二叉树LinkedQueue<BinaryNode<T>> que = new LinkedQueue<BinaryNode<T>>();/创建空队列BinaryNode<T> 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指向出队结点，若队列空返回nullSystem.out.println();（4）使用二叉树UseBinaryTree.javapackage tree;import java.util.Scanner;/* * * author pang * */public class UseBinaryTree public static BinaryTree<String> make(String a,String b,String c,String d,String e,String f,String g,String h)BinaryTree<String> bitree = new BinaryTree<String>();BinaryNode<String> child_f,child_d,child_b,child_c;child_d = new BinaryNode<String>(d,null,new BinaryNode<String>(g);child_b = new BinaryNode<String>(b,child_d,null);child_f = new BinaryNode<String>(f,new BinaryNode<String>(h),null);child_c = new BinaryNode<String>(c,new BinaryNode<String>(e),child_f);bitree.root = new BinaryNode<String>(a,child_b,child_c);return bitree;public static 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<String> bitree = make(a,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<String> bitree,int a)switch(a)case 1:bitree.preOrder();break;case 2:bitree.inOrder();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中有用到队列部分内容，需要导入包或者将该部分文件放入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;public 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树的结点数组public 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;i<n;i+)/结点数组初始化有n个叶子结点this.huftreei = new TriElement(weighti);for(int i=0;i<n-1;i+)/构造n-1个2度将结点，每次循环构造1个2度结点int min1=Integer.MAX_VALUE,min2=min1;/最小和次最小权值，初值为整数最大值int x1=-1,x2=-1;/记录两个无父母的最小权值结点下标for(int j=0;j<n+i;j+)/查找两个无父母的最小权值结点if(huftreej.data<min1 && huftreej.parent=-1)min2 = min1;x2 = x1;min1 = huftreej.data;/min1记下最小权值x1 = j;/x1记下最小权值结点的下标else if(huftreej.data<min2 && huftreej.parent=-1)min2 = huftreej.data;x2 = j;/x2记下次最小权值结点的下标huftreex1.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;i<this.huftree.length&&huftreei!=null;i+)str += "第"+i+"行"+this.huftreei.toString()+"n"return str;public String huffmanCodes()/返回当前Huffman树的Huffman编码String hufcodes = new Stringthis.leafNum;for(int i=0;i<this.leafNum;i+)/求n个叶子结点的Huffman编码hufcodesi = ""int child = i;int parent = huftreechild.parent;while(parent != -1)/由叶子结点向上直到根节点循环if(huftreeparent.left = child)hufcodesi="0"+hufcodesi;/左孩子结点编码为0elsehufcodesi="1"+hufcodesi;/右孩子结点编码为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<Integer> list = new SeqList<Integer>();System.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;i<list.length();i+)weighti = list.get(i);HuffmanTree htree = new HuffmanTree(weight);System.out.print(htree.toString();String code = htree.huffmanCodes();System.out.print("Huffman编码： n");for(int i = 0;i<code.length;i+)System.out.println(char)('A'+i)+": "+codei+" ");（4）注意事项从键盘输入权值且不确定个数，需要一个标识符，这里用了0作为标识符。使用到了线性表部分内容，需要导入包或将文件放入此包中。（5）运行结果：3.二叉树的中序线索化（1）二叉链表结点类ThreadNode.javapackage threadBinaryTree;public class ThreadNode<T> public T data;public ThreadNode<T> left,right;public int ltag,rtag;public ThreadNode(T data,ThreadNode<T> left,int ltag,ThreadNode<T> 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 ThreadNode() this(null,null,0,null,0);（2）中序线索二叉树类ThreadBinaryTree.javapackage threadBinaryTree;public class ThreadBinaryTree<T> public ThreadNode<T> root;public ThreadBinaryTree() this.root = null;public boolean isEmpty() return root = null;public ThreadBinaryTree(T prelist)this.root = create(prelist);inorderThread(this.root);private int i = 0;private ThreadNode<T> create(T prelist) ThreadNode<T> p = null;if (i < prelist.length) T elem = prelisti+;if (elem != null) p = new ThreadNode<T>(elem);p.left = create(prelist);p.right = create(prelist);return p;private ThreadNode<T> front=null;private void inorderThread(ThreadNode<T> 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<T> inNext(ThreadNode<T> p)if(p.rtag=1)p=p.right;elsep=p.right;while(p.ltag=0)p=p.left;return p;public void inOrder()System.out.print("中根次序遍历中序线索二叉树： ");ThreadNode<T> 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<String> tbitree = new ThreadBinaryTree<String>(prelist);tbitree.inOrder();（4）运行结果：四、实验收获和建议：