實驗五 二叉樹

1、實驗五 二叉樹一、 實驗?zāi)康模?、掌握二叉樹的創(chuàng)建算法、掌握二叉樹的遍歷算法2、掌握哈夫曼樹的構(gòu)造和應(yīng)用，利用哈夫曼方法及其編/譯碼技術(shù)實現(xiàn)對傳輸信息編碼/譯碼系統(tǒng)。二、 實驗內(nèi)容：1、 在一棵二叉鏈表表示的二叉樹中，實現(xiàn)以下操作。1） 輸出葉子結(jié)點。2） 求二叉樹中葉子結(jié)點個數(shù)。3） 將每個結(jié)點的左子樹與右子樹交換。4） 已知先根和中根次序遍歷序列構(gòu)造二叉樹。5） 判斷兩棵二叉樹是否相等。6） 求結(jié)點所在的層次。7） 復(fù)制一棵二叉樹。8） 判斷一棵二叉樹是否為完全二叉樹。算法及測試結(jié)果粘貼如下：package Q1;public class BinaryNode<T> publi

2、c 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);package Q1;public class BinaryTree<T>p

3、ublic Node<String> head_pre;public Node<String> head_in;public BinaryNode<T> root;public BinaryTree()this.root=null;public boolean isEmpty()return this.root=null;private BinaryTree<String> init_make()BinaryTree<String> bitree=new BinaryTree<String>();BinaryNode<

4、;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&quo

5、t;),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;private void leaf(BinaryNode<String> p)if(p!=null)if(p.left=null && p.right=null)Syste

6、m.out.print(p.data+" ");leaf(p.left);leaf(p.right);private int leaf_count(BinaryNode<String> 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<String> p)BinaryNode temp = new

7、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<T> preOrder_inOrder_make(T preList,T inList,int preStart,int inStart,int

8、 n)if(n<=0)return null;T elem=preListpreStart;BinaryNode<T> p=new BinaryNode<T>(elem);int i=0;while(i<n && !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

9、,n-1-i);return p;private void preOrder(BinaryNode<String> p)if(p!=null)System.out.print(p.data+" ");preOrder(p.left);preOrder(p.right);private void inOrder(BinaryNode<String> p)if(p!=null)preOrder(p.left);System.out.print(p.data+" ");preOrder(p.right);private boolean

10、CompTree(BinaryNode<String> tree1,BinaryNode<String> 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) |

11、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<T> p, int i, T x) if (p=null) return -1; if (p.data.equals(x) return i; int level = getLevel(p.left, i+

12、1, x); if (level=-1) level = getLevel(p.right, i+1, x); return level; private BinaryNode<T> copy(BinaryNode<T> p) if (p=null) return null; BinaryNode<T> q = new BinaryNode<T>(p.data); q.left = copy(p.left); q.right = copy(p.right); return q; private boolean isCompleteBinaryTr

13、ee() if (this.root=null) return true; LinkedQueue<BinaryNode<T>> que = new LinkedQueue<BinaryNode<T>>(); que.enqueue(root); BinaryNode<T> p=null; while (!que.isEmpty() p = que.dequeue(); if (p.left!=null ) que.enqueue(p.left); if (p.right!=null) que.enqueue(p.right); el

14、se 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<String> tree1 =new BinaryTree<String>();tree1=tree1.init_make();System.out.prin

15、t("這棵樹的葉子結(jié)點分別為： ");tree1.leaf(tree1.root);System.out.println();int num=tree1.leaf_count(tree1.root);System.out.println("這棵樹的葉子結(jié)點個數(shù)為： "+num);System.out.print("這棵樹的前序遍歷為： ");tree1.preOrder(tree1.root);System.out.println();System.out.print("這棵樹左右子樹交換后的前序遍歷為： ");t

16、ree1.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",

17、"H","F"BinaryTree<String> tree_pre_in =new BinaryTree<String>(preList,inList);System.out.print("這棵樹的前序遍歷為： ");tree1.preOrder(tree_pre_in.root);System.out.println();BinaryTree<String> tree2 =new BinaryTree<String>();tree2=tree2.init_make();System.

18、out.println("判斷這兩棵二叉樹時候相同："+tree1.CompTree(tree1.root ,tree2.root);System.out.println("結(jié)點B所在的層數(shù)："+tree1.getLevel("B");BinaryTree<String> tree3 =new BinaryTree<String>();tree3.copy(tree1.root);System.out.println("這課二叉樹是否為完全二叉樹："+tree1.isCompleteBina

19、ryTree();package Q1;public class LinkedQueue<T> private Node<T> 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<T> q=new Node<T>(x,null);if(this.front

20、=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<T> public T data;public Node<T> next;public Node(T data,Node<T>

21、 next)this.data=data;this.next=next;public Node()this(null,null);2、 問題描述（設(shè)計性實驗）哈夫曼樹很易求出給定字符集及其概率(或頻度)分布的最優(yōu)前綴碼。哈夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。該技術(shù)一般可將數(shù)據(jù)文件壓縮掉20至90，其壓縮效率取決于被壓縮文件的特征。利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳送電文須預(yù)先編碼，在接收須將傳送來的數(shù)據(jù)進(jìn)行譯碼。請自行設(shè)計實現(xiàn)一個具有初始化、編碼、譯碼、輸入/輸出等功能的哈夫曼碼的編碼/譯碼系統(tǒng)。

22、并實現(xiàn)以下報文的編碼和譯碼：“this program is my favorite”。測試數(shù)據(jù)某通信的電文字符集為26個英文字母及空格字符，其出現(xiàn)頻度如下表所示：字符空格abcdefghi頻度1866413223210321154757字符jklmnopqrs頻度15322057631514851字符tuvwxyz頻度80238181161實現(xiàn)提示如何創(chuàng)建哈夫曼樹及如何求得各結(jié)點對應(yīng)的哈夫曼編碼算法1）設(shè)計思想描述（1） 問題分析。（2） 哈夫曼樹中各結(jié)點的結(jié)構(gòu)描述。（3） 哈夫曼樹的存儲結(jié)構(gòu)描述（提示：分析采用順序存儲還是利用鏈?zhǔn)酱鎯Φ龋?）主要算法設(shè)計與實現(xiàn)package Q2;pub

23、lic 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+

24、","+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;i<n;i+)this.hu

25、fftreei=new TriElement(weighti);for(int i=0;i<n-1;i+)int min1=Integer.MAX_VALUE,min2=min1;int x1=-1,x2=-1;for(int j=0;j<n+i;j+)if(hufftreej.data<min1 && hufftreej.parent=-1)min2=min1;x2=x1;min1=hufftreej.data;x1=j;else if(hufftreej.data<min2 && hufftreej.parent=-1)min2=hu

26、fftreej.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;i<this.leafNum;i+)hufcodesi=""int child=i;int parent=hufftreechild.pare

27、nt;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 w

28、eight=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;i<weight.length/4;i+)Syst

29、em.out.print(char)(i+96)+":"+hufcodesi+" ");System.out.println();for(int i=weight.length/4;i<weight.length/2;i+)System.out.print(char)(i+96)+":"+hufcodesi+" ");System.out.println();for(int i=weight.length/2;i<weight.length/4*3+2;i+)System.out.print(char)(i+96)+":"+hufcodesi+"