实验五二叉树.docx

实验五二叉树.docx

《实验五二叉树.docx》由会员分享，可在线阅读，更多相关《实验五二叉树.docx（17页珍藏版）》请在冰点文库上搜索。

实验五二叉树

实验五二叉树

一、实验目的：

1、掌握二叉树的创建算法、掌握二叉树的遍历算法

2、掌握哈夫曼树的构造和应用，利用哈夫曼方法及其编/译码技术实现对传输信息编码/译码系统。

二、实验内容：

1、在一棵二叉链表表示的二叉树中，实现以下操作。

1）输出叶子结点。

2）求二叉树中叶子结点个数。

3）将每个结点的左子树与右子树交换。

4）已知先根和中根次序遍历序列构造二叉树。

5）判断两棵二叉树是否相等。

6）求结点所在的层次。

7）复制一棵二叉树。

8）判断一棵二叉树是否为完全二叉树。

算法及测试结果粘贴如下：

packageQ1;

publicclassBinaryNode{

publicTdata;

publicBinaryNodeleft,right;

publicBinaryNode（Tdata,BinaryNodeleft,BinaryNoderight）{

this.data=data;

this.left=left;

this.right=right;

}

publicBinaryNode（Tdata）{

this（data,null,null）;

}

publicBinaryNode（）{

this（null,null,null）;

}

}

packageQ1;

publicclassBinaryTree{

publicNodehead_pre;

publicNodehead_in;

publicBinaryNoderoot;

publicBinaryTree（）{

this.root=null;

}

publicbooleanisEmpty（）{

returnthis.root==null;

}

privateBinaryTreeinit_make（）{

BinaryTreebitree=newBinaryTree（）;

BinaryNodechild_f,child_d,child_b,child_c;

child_d=newBinaryNode（"D",null,newBinaryNode（"G"））;

child_b=newBinaryNode（"B",child_d,null）;

child_f=newBinaryNode（"F",newBinaryNode（"H"）,null）;

child_c=newBinaryNode（"C",newBinaryNode（"E"）,child_f）;

bitree.root=newBinaryNode（"A",child_b,child_c）;

returnbitree;

}

privatevoidleaf（BinaryNodep）{

if（p!

=null）{

if（p.left==null&&p.right==null）{

System.out.print（p.data+""）;

}

leaf（p.left）;

leaf（p.right）;

}

}

privateintleaf_count（BinaryNodep）{

if（p==null）

return0;

if（p.left==null&&p.right==null）

return1;

elsereturnleaf_count（p.left）+leaf_count（p.right）;

}

privatevoidexchange（BinaryNodep）{

BinaryNodetemp=newBinaryNode（）;

if（p!

=null）{

temp=p.left;

p.left=p.right;

p.right=temp;

exchange（p.left）;

exchange（p.right）;

}

}

publicBinaryTree（T[]prelist,T[]inlist）{

this.root=preOrder_inOrder_make（prelist,inlist,0,0,prelist.length）;

}

privateBinaryNodepreOrder_inOrder_make（T[]preList,T[]inList,intpreStart,intinStart,intn）{

if（n<=0）

returnnull;

Telem=preList[preStart];

BinaryNodep=newBinaryNode（elem）;

inti=0;

while（i

elem.equals（inList[inStart+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）;

returnp;

}

privatevoidpreOrder（BinaryNodep）{

if（p!

=null）{

System.out.print（p.data+""）;

preOrder（p.left）;

preOrder（p.right）;

}

}

privatevoidinOrder（BinaryNodep）{

if（p!

=null）{

preOrder（p.left）;

System.out.print（p.data+""）;

preOrder（p.right）;

}

}

privatebooleanCompTree（BinaryNodetree1,BinaryNodetree2）{

if（tree1==null&&tree2==null）{

returntrue;

}

if（tree1==null||tree2==null）{

returnfalse;

}

if（tree1.data!

=tree2.data）{

returnfalse;

}

if（CompTree（tree1.left,tree2.left）&&CompTree（tree1.right,tree2.right）||

CompTree（tree1.left,tree2.right）&&CompTree（tree1.right,tree2.left））{

returntrue;

}

returnfalse;

}

privateintgetLevel（Tx）{

returngetLevel（root,1,x）;

}

privateintgetLevel（BinaryNodep,inti,Tx）{

if（p==null）

return-1;

if（p.data.equals（x））

returni;

intlevel=getLevel（p.left,i+1,x）;

if（level==-1）

level=getLevel（p.right,i+1,x）;

returnlevel;

}

privateBinaryNodecopy（BinaryNodep）{

if（p==null）

returnnull;

BinaryNodeq=newBinaryNode（p.data）;

q.left=copy（p.left）;

q.right=copy（p.right）;

returnq;

}

privatebooleanisCompleteBinaryTree（）{

if（this.root==null）

returntrue;

LinkedQueue>que=newLinkedQueue>（）;

que.enqueue（root）;

BinaryNodep=null;

while（!

que.isEmpty（））{

p=que.dequeue（）;

if（p.left!

=null）{

que.enqueue（p.left）;

if（p.right!

=null）

que.enqueue（p.right）;

elsebreak;

}

elseif（p.right!

=null）

returnfalse;

elsebreak;

}

while（!

que.isEmpty（））{

p=que.dequeue（）;

if（p.left!

=null||p.right!

=null）

returnfalse;

}

returntrue;

}

publicstaticvoidmain（String[]args）{

BinaryTreetree1=newBinaryTree（）;

tree1=tree1.init_make（）;

System.out.print（"这棵树的叶子结点分别为：

"）;

tree1.leaf（tree1.root）;

System.out.println（）;

intnum=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"};

BinaryTreetree_pre_in=newBinaryTree（preList,inList）;

System.out.print（"这棵树的前序遍历为：

"）;

tree1.preOrder（tree_pre_in.root）;

System.out.println（）;

BinaryTreetree2=newBinaryTree（）;

tree2=tree2.init_make（）;

System.out.println（"判断这两棵二叉树时候相同：

"+tree1.CompTree（tree1.root,tree2.root））;

System.out.println（"结点B所在的层数：

"+tree1.getLevel（"B"））;

BinaryTreetree3=newBinaryTree（）;

tree3.copy（tree1.root）;

System.out.println（"这课二叉树是否为完全二叉树：

"+tree1.isCompleteBinaryTree（））;

}

}

packageQ1;

publicclassLinkedQueue{

privateNodefront,rear;

publicLinkedQueue（）{

this.front=this.rear=null;

}

publicbooleanisEmpty（）{

returnthis.front==null&&this.rear==null;

}

publicvoidenqueue（Tx）{

if（x==null）

return;

Nodeq=newNode（x,null）;

if（this.front==null）

this.front=q;

else

this.rear.next=q;

this.rear=q;

}

publicTdequeue（）{

if（isEmpty（））

returnnull;

Ttemp=this.front.data;

this.front=this.front.next;

if（this.front==null）

this.rear=null;

returntemp;

}

}

packageQ1;

publicclassNode{

publicTdata;

publicNodenext;

publicNode（Tdata,Nodenext）{

this.data=data;

this.next=next;

}

publicNode（）{

this（null,null）;

}

}

2、[问题描述]（设计性实验）

哈夫曼树很易求出给定字符集及其概率（或频度）分布的最优前缀码。

哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。

该技术一般可将数据文件压缩掉20％至90％，其压缩效率取决于被压缩文件的特征。

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时，降低传输成本。

但是，这要求在发送端通过一个编码系统对待传送电文须预先编码，在接收须将传送来的数据进行译码。

请自行设计实现一个具有初始化、编码、译码、输入/输出等功能的哈夫曼码的编码/译码系统。

并实现以下报文的编码和译码：

“thisprogramismyfavorite”。

[测试数据]

某通信的电文字符集为26个英文字母及空格字符，其出现频度如下表所示：

字符

空格

a

b

c

d

e

f

g

h

i

频度

186

64

13

22

32

103

21

15

47

57

字符

j

k

l

m

n

o

p

q

r

s

频度

1

5

32

20

57

63

15

1

48

51

字符

t

u

v

w

x

y

z

频度

80

23

8

18

1

16

1

[实现提示]如何创建哈夫曼树及如何求得各结点对应的哈夫曼编码算法

1）设计思想描述

（1）问题分析。

（2）哈夫曼树中各结点的结构描述。

（3）哈夫曼树的存储结构描述（提示：

分析采用顺序存储还是利用链式存储等）。

2）主要算法设计与实现

packageQ2;

publicclassTriElement{

intdata,parent,left,right;

publicTriElement（intdata,intparent,intleft,intright）{

this.data=data;

this.parent=parent;

this.left=left;

this.right=right;

}

publicTriElement（intdata）{

this（data,-1,-1,-1）;

}

publicTriElement（）{

this（0）;

}

publicStringtoString（）{

return"（"+this.data+","+this.parent+","+this.left+","+this.right+"）";

}

}

packageQ2;

publicclassHuffmanTree{

privateintleafNum;

privateTriElement[]hufftree;

publicHuffmanTree（int[]weight）{

intn=weight.length;

this.leafNum=n;

this.hufftree=newTriElement[2*n-1];

for（inti=0;i

this.hufftree[i]=newTriElement（weight[i]）;

for（inti=0;i

intmin1=Integer.MAX_VALUE,min2=min1;

intx1=-1,x2=-1;

for（intj=0;j

if（hufftree[j].data

min2=min1;

x2=x1;

min1=hufftree[j].data;

x1=j;

}

elseif（hufftree[j].data

min2=hufftree[j].data;

x2=j;

}

hufftree[x1].parent=n+i;

hufftree[x2].parent=n+i;

this.hufftree[n+i]=newTriElement（hufftree[x1].data+hufftree[x2].data,-1,x1,x2）;

}

}

publicString[]huffmanCodes（）{

String[]hufcodes=newString[this.leafNum];

for（inti=0;i

hufcodes[i]="";

intchild=i;

intparent=hufftree[child].parent;

while（parent!

=-1）{

if（hufftree[parent].left==child）

hufcodes[i]="0"+hufcodes[i];

else

hufcodes[i]="1"+hufcodes[i];

child=parent;

parent=hufftree[child].parent;

}

}

returnhufcodes;

}

}

packageQ2;

publicclassTest{

publicstaticvoidmain（String[]args）{

Stringtemp="thisprogramismyfavorite";

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};

HuffmanTreehuf=newHuffmanTree（weight）;

String[]hufcodes=huf.huffmanCodes（）;

System.out.println（"huffman编码为：

"）;

System.out.print（"空格:

"+hufcodes[0]+""）;

for（inti=1;i

System.out.print（（char）（i+96）+":

"+hufcodes[i]+""）;

System.out.println（）;

for（inti=weight.length/4;i

System.out.print（（char）（i+96）+":

"+hufcodes[i]+""）;

System.out.println（）;

for（inti=weight.length/2;i

System.out.print（（char）（i+96）+":

"+hufcodes[i]+""）;

System.out.println（）;

for（inti=weight.length/4*3+2;i

System.out.print（（char）（i+96）+":

"+hufcodes[i]+""）;

System.out.println（）;

Stringvalue=codes（hufcodes,temp）;

System.out.println（"编码是:

"+value）;

System.out.println（discoding（value,hufcodes））;

}

publicstaticStringcodes（String[]hufcodes,Stringtemp）{

Stringstr="";

for（inti=0;i

if（temp.charAt（i）==''）

str+=hufcodes[0];

else

str+=hufcodes[temp.charAt（i）-96];

returnstr;

}

publicstaticStri