山东大学数据结构实验报告七Word文档格式.docx
《山东大学数据结构实验报告七Word文档格式.docx》由会员分享，可在线阅读，更多相关《山东大学数据结构实验报告七Word文档格式.docx（30页珍藏版）》请在冰点文库上搜索。
friendclassHuffman;
public:
BinaryTree（）{root=0;
num=0;
}
boolIsEmpty（）{returnroot==0;
boolRoot（int&
x）;
voidMakeTree（constint&
element,BinaryTree&
left,BinaryTree&
right）;
voidBreakTree（int&
intHeight（）const{returnHeight（root）;
intNumNode（）{num=1;
NumNode（root）;
returnnum;
voidPreOrder（）{PreOrder（root）;
cout<
<
endl;
voidInOrder（）{InOrder（root）;
voidPostOrder（）{PostOrder（root）;
voidLevelOrder（）{LevelOrder（root）;
voidTransfer（BinaryTree*t）{t->
root=root;
root=0;
private:
voidVisit（BinaryTreeNode*）;
intHeight（BinaryTreeNode*）const;
voidNumNode（BinaryTreeNode*）;
voidPreOrder（BinaryTreeNode*）;
voidInOrder（BinaryTreeNode*）;
voidPostOrder（BinaryTreeNode*）;
voidLevelOrder（BinaryTreeNode*）;
BinaryTreeNode*root;
intnum;
};
#endif
Binarytree.cpp
stack>
queue>
binarytree.h"
voidBinaryTree:
:
Visit（BinaryTreeNode*t）{
t->
data<
"
;
}
PreOrder（BinaryTreeNode*t）{
stack<
BinaryTreeNode*>
s;
while（t）{
Visit（t）;
if（t->
RightChild）s.push（t->
RightChild）;
LeftChild）s.push（t->
LeftChild）;
if（s.empty（））{
return;
}
else{
t=s.top（）;
s.pop（）;
InOrder（BinaryTreeNode*t）{
BinaryTreeNode*pre=NULL;
LeftChild）{
if（pre==t->
Visit（t）;
pre=t;
if（s.empty（））{
return;
}
else{
t=s.top（）;
s.pop（）;
}
elseif（t->
LeftChild->
RightChild）{
BinaryTreeNode*d=t->
RightChild;
while（d->
d=d->
if（pre==d）{
Visit（t）;
pre=t;
if（s.empty（））{
return;
}
else{
t=s.top（）;
s.pop（）;
if（t->
s.push（t）;
t=t->
LeftChild;
else{
if（t->
s.push（t）;
t=t->
elseif（t->
Visit（t）;
pre=t;
t=t->
if（s.empty（））{
return;
t=s.top（）;
s.pop（）;
PostOrder（BinaryTreeNode*t）{
s.push（t->
LevelOrder（BinaryTreeNode*t）{
queue<
BinaryTreeNode*>
q;
LeftChild）q.push（t->
RightChild）q.push（t->
if（q.empty（））{
t=q.front（）;
q.pop（）;
boolBinaryTree:
Root（int&
x）{
if（root）{
x=root->
data;
returntrue;
elsereturnfalse;
MakeTree（constint&
right）{
root=newBinaryTreeNode（element,left.root,right.root）;
left.root=right.root=0;
BreakTree（int&
if（!
root）{
cout<
该树是空树"
<
else{
element=root->
left.root=root->
right.root=root->
deleteroot;
root=0;
intBinaryTree:
Height（BinaryTreeNode*t）const{
t）return0;
inthl=Height（t->
inthr=Height（t->
if（hl>
hr）return++hl;
elsereturn++hr;
NumNode（BinaryTreeNode*t）{
q.push（t->
num++;
RightChild）{
Binarytreenode.h
#ifndefBINARYTREENODE_H
#defineBINARYTREENODE_H
classBinaryTreeNode{
friendclassBinaryTree;
BinaryTreeNode（）{LeftChild=RightChild=0;
BinaryTreeNode（constint&
e）{data=e;
LeftChild=RightChild=0;
e,BinaryTreeNode*l,BinaryTreeNode*r）{data=e;
LeftChild=l;
RightChild=r;
BinaryTreeNode*LeftChild,*RightChild;
intdata;
Bstree.h
classBSTree:
publicBinaryTree{
boolSearch（constint&
k,int&
e）const;
BSTree&
Insert（constint&
e）;
Delete（constint&
voidAscend（）{InOrder（）;
Bstree.cpp
bstree.h"
boolBSTree:
Search（constint&
e）const{
BinaryTreeNode*p=root;
while（p）{
if（k<
p->
data）
p=p->
elseif（k>
e=p->
returntrue;
returnfalse;
BSTree&
BSTree:
Insert（constint&
e）{
BinaryTreeNode*p=root,*pp=0;
pp=p;
if（e<
elseif（e>
return*this;
BinaryTreeNode*r=newBinaryTreeNode（e）;
pp->
pp->
LeftChild=r;
else
RightChild=r;
else
root=r;
return*this;
Delete（constint&
while（p&
&
data!
=k）{
p）{
错误!
搜索树中不存在该元素!
"
return*this;
e=p->
if（p->
LeftChild&
BinaryTreeNode*s=p->
LeftChild,*ps=p;
while（s->
ps=s;
s=s->
p->
data=s->
p=s;
pp=ps;
BinaryTreeNode*c;
LeftChild）
c=p->
if（p==root）
root=c;
if（p==pp->
LeftChild=c;
RightChild=c;
deletep;
Heapnode.h
classHeapNode{
friendclassMaxHeap;
HeapNode*parent,*left,*right;
Huffman.h
#ifndefHUFFMAN_H
#defineHUFFMAN_H
string>
classHuffman{
friendHuffmanHuffmanTree（int*,int）;
friendintmain（）;
friendclassMinHeap;
operatorint（）const{returnweight;
voidOutPut（）const;
voidHuOrder（BinaryTreeNode*p,stringstr）const;
BinaryTreetree;
intweight;
Huffman.cpp
huffman.h"
minheap.h"
HuffmanHuffmanTree（int*a,intn）{
Huffman*w=newHuffman[n+1];
BinaryTreez,zero;
for（inti=1;
i<
=n;
i++）{
z.MakeTree（i,zero,zero）;
w[i].weight=a[i];
w[i].tree=z;
MinHeapH;
H.Initialize（w,n,n）;
Huffmanx,y;
n;
H.DeleteMin（x）;
H.DeleteMin（y）;
z.MakeTree（0,x.tree,y.tree）;
x.weight+=y.weight;
x.tree=z;
H.Insert（x）;
H.DeleteMin（x）;
w=NULL;
delete[]w;
returnx;
voidHuffman:
OutPut（）const{
if（tree.root->
tree.root->
stringstr="
HuOrder（tree.root,str）;
0"
HuOrder（BinaryTreeNode*p,stringstr）const{
data）{
下标为"
p->
的元素的Huffman编码:
——"
str<
HuOrder（p->
LeftChild,str+"
）;
RightChild,str+"
1"
Maxheap.h
heapnode.h"
classMaxHeap{
MaxHeap（）{root=0;
size=0;
~MaxHeap（）;
intSize（）const{returnsize;
boolIsEmpty（）const{returnroot==0;
intMax（）{if（size==0）{cout<
该堆为空!
return-1;
}returnroot->
MaxHeap&
x）;
DeleteMax（int&
voidInitialize（inta[],intarraysize）;
voidOutPut（）;
intFind（intk）;
voidClear（）;
intsize;
HeapNode*root;
Maxheap.cpp
#include"
maxheap.h"
MaxHeap:
~MaxHeap（）{
Clear（）;
MaxHeap&
MaxHeap:
x）{
size）{
root=newHeapNode（）;
root->
data=x;
parent=root->
left=root->
right=0;
size++;
intnum,i=1;
HeapNode*r=root;
while（i!
=size/2）{
num=size;
while（num!
=2*i&
num!
=2*i+1）{
num=num/2;
if（num==2*i）{
r=r->
left;
i=2*i;
right;
i=2*i+1;
if（size==2*i）{
r->
left=newHeapNode（）;
left->
parent=r;
left-
升级会员 