实验五 二叉树.doc

.实验五 二叉树一、 实验目的：1、掌握二叉树的创建算法、掌握二叉树的遍历算法2、掌握哈夫曼树的构造和应用，利用哈夫曼方法及其编/译码技术实现对传输信息编码/译码系统。二、 实验内容：1、 在一棵二叉链表表示的二叉树中，实现以下操作。1） 输出叶子结点。2） 求二叉树中叶子结点个数。3） 将每个结点的左子树与右子树交换。4） 已知先根和中根次序遍历序列构造二叉树。5） 判断两棵二叉树是否相等。6） 求结点所在的层次。7） 复制一棵二叉树。8） 判断一棵二叉树是否为完全二叉树。算法及测试结果粘贴如下：package Q1;public class BinaryNode public T data;public BinaryNode left,right;public BinaryNode(T data,BinaryNode left,BinaryNode right)this.data=data;this.left=left;this.right=right;public BinaryNode(T data)this(data,null,null);public BinaryNode()this(null,null,null);package Q1;public class BinaryTreepublic Node head_pre;public Node head_in;public BinaryNode root;public BinaryTree()this.root=null;public boolean isEmpty()return this.root=null;private BinaryTree init_make()BinaryTree bitree=new BinaryTree();BinaryNode child_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;private void leaf(BinaryNode p)if(p!=null)if(p.left=null & p.right=null)System.out.print(p.data+ );leaf(p.left);leaf(p.right);private int leaf_count(BinaryNode p)if(p=null)return 0;if(p.left=null & p.right=null)return 1;else return leaf_count(p.left)+leaf_count(p.right);private void exchange(BinaryNode p)BinaryNode temp = new BinaryNode();if(p!=null)temp=p.left;p.left=p.right;p.right=temp;exchange(p.left);exchange(p.right);public BinaryTree(T prelist,T inlist)this.root=preOrder_inOrder_make(prelist,inlist,0,0,prelist.length);private BinaryNode preOrder_inOrder_make(T preList,T inList,int preStart,int inStart,int n)if(n=0)return null;T elem=preListpreStart;BinaryNode p=new BinaryNode(elem);int i=0;while(in & !elem.equals(inListinStart+i)i+;p.left=preOrder_inOrder_make(preList,inList,preStart+1,inStart,i);p.right=preOrder_inOrder_make(preList,inList,preStart+i+1,inStart+i+1,n-1-i);return p;private void preOrder(BinaryNode p)if(p!=null)System.out.print(p.data+ );preOrder(p.left);preOrder(p.right);private void inOrder(BinaryNode p)if(p!=null)preOrder(p.left);System.out.print(p.data+ );preOrder(p.right);private boolean CompTree(BinaryNode tree1,BinaryNode tree2)if (tree1 = null & tree2 = null) return true; if (tree1 = null | tree2 = null) return false; if (tree1.data != tree2.data) return false; if (CompTree(tree1.left,tree2.left) & CompTree(tree1.right,tree2.right) | CompTree(tree1.left,tree2.right) & CompTree(tree1.right,tree2.left) return true; return false; private int getLevel(T x) return getLevel(root, 1, x); private int getLevel(BinaryNode p, int i, T x) if (p=null) return -1; if (p.data.equals(x) return i; int level = getLevel(p.left, i+1, x); if (level=-1) level = getLevel(p.right, i+1, x); return level; private BinaryNode copy(BinaryNode p) if (p=null) return null; BinaryNode q = new BinaryNode(p.data); q.left = copy(p.left); q.right = copy(p.right); return q; private boolean isCompleteBinaryTree() if (this.root=null) return true; LinkedQueueBinaryNode que = new LinkedQueueBinaryNode(); que.enqueue(root); BinaryNode p=null; while (!que.isEmpty() p = que.dequeue(); if (p.left!=null ) que.enqueue(p.left); if (p.right!=null) que.enqueue(p.right); else break; else if (p.right!=null) return false; else break; while (!que.isEmpty() p = que.dequeue(); if (p.left!=null | p.right!=null) return false; return true; public static void main(String args)BinaryTree tree1 =new BinaryTree();tree1=tree1.init_make();System.out.print(这棵树的叶子结点分别为： );tree1.leaf(tree1.root);System.out.println();int num=tree1.leaf_count(tree1.root);System.out.println(这棵树的叶子结点个数为： +num);System.out.print(这棵树的前序遍历为： );tree1.preOrder(tree1.root);System.out.println();System.out.print(这棵树左右子树交换后的前序遍历为： );tree1.exchange(tree1.root);tree1.preOrder(tree1.root);System.out.println();String preList =A,B,D,G,C,E,F,H;String inList =D,G,B,A,E,C,H,F;BinaryTree tree_pre_in =new BinaryTree(preList,inList);System.out.print(这棵树的前序遍历为： );tree1.preOrder(tree_pre_in.root);System.out.println();BinaryTree tree2 =new BinaryTree();tree2=tree2.init_make();System.out.println(判断这两棵二叉树时候相同：+tree1.CompTree(tree1.root ,tree2.root);System.out.println(结点B所在的层数：+tree1.getLevel(B);BinaryTree tree3 =new BinaryTree();tree3.copy(tree1.root);System.out.println(这课二叉树是否为完全二叉树：+tree1.isCompleteBinaryTree();package Q1;public class LinkedQueue private Node front,rear;public LinkedQueue()this.front=this.rear=null;public boolean isEmpty()return this.front=null&this.rear=null;public void enqueue(T x)if(x=null)return;Node q=new Node(x,null);if(this.front=null)this.front=q;elsethis.rear.next=q;this.rear=q;public T dequeue()if(isEmpty()return null;T temp=this.front.data;this.front=this.front.next;if(this.front=null)this.rear=null;return temp;package Q1;public class Node public T data;public Node next;public Node(T data,Node next)this.data=data;this.next=next;public Node()this(null,null);2、 问题描述（设计性实验）哈夫曼树很易求出给定字符集及其概率(或频度)分布的最优前缀码。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。该技术一般可将数据文件压缩掉20至90，其压缩效率取决于被压缩文件的特征。利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时，降低传输成本。但是，这要求在发送端通过一个编码系统对待传送电文须预先编码，在接收须将传送来的数据进行译码。请自行设计实现一个具有初始化、编码、译码、输入/输出等功能的哈夫曼码的编码/译码系统。并实现以下报文的编码和译码：“this program is my favorite”。测试数据某通信的电文字符集为26个英文字母及空格字符，其出现频度如下表所示：字符空格abcdefghi频度1866413223210321154757字符jklmnopqrs频度15322057631514851字符tuvwxyz频度80238181161实现提示如何创建哈夫曼树及如何求得各结点对应的哈夫曼编码算法1）设计思想描述（1） 问题分析。（2） 哈夫曼树中各结点的结构描述。（3） 哈夫曼树的存储结构描述（提示：分析采用顺序存储还是利用链式存储等）。2）主要算法设计与实现package Q2;public class TriElement int data,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+);package Q2;public class HuffmanTree private int leafNum;private TriElement hufftree;public HuffmanTree(int weight)int n=weight.length;this.leafNum=n;this.hufftree=new TriElement2*n-1;for(int i=0;in;i+)this.hufftreei=new TriElement(weighti);for(int i=0;in-1;i+)int min1=Integer.MAX_VALUE,min2=min1;int x1=-1,x2=-1;for(int j=0;jn+i;j+)if(hufftreej.datamin1 & hufftreej.parent=-1)min2=min1;x2=x1;min1=hufftreej.data;x1=j;else if(hufftreej.datamin2 & hufftreej.parent=-1)min2=hufftreej.data;x2=j;hufftreex1.parent=n+i;hufftreex2.parent=n+i;this.hufftreen+i=new TriElement(hufftreex1.data+hufftreex2.data,-1,x1,x2); public String huffmanCodes()String hufcodes=new Stringthis.leafNum;for(int i=0;ithis.leafNum;i+)hufcodesi=;int child=i;int parent=hufftreechild.parent;while(parent!=-1)if(hufftreeparent.left=child)hufcodesi=0+hufcodesi;elsehufcodesi=1+hufcodesi;child=parent;parent=hufftreechild.parent;return hufcodes;package Q2;public class Test public static void main(String args) String temp=this program is my favorite;int weight=186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1;HuffmanTree huf=new HuffmanTree(weight);String hufcodes=huf.huffmanCodes();System.out.println(huffman编码为：);System.out.print(空格:+hufcodes0+ );for(int i=1;iweight.length/4;i+)System.out.print(char)(i+96)+:+hufcodesi+ );System.out.println();for(int i=weight.length/4;iweight.length/2;i+)System.out.print(char)(i+96)+:+hufcodesi+ );System.out.println();for(int i=weight.length/2;iweight.length/4*3+2;i+)System.out.print(char)(i+96)+:+hufcodesi+ );System.out.println();for(int i=weight.length/4*3