山东大学数据结构实验报告七.docx
《山东大学数据结构实验报告七.docx》由会员分享，可在线阅读，更多相关《山东大学数据结构实验报告七.docx（30页珍藏版）》请在冰点文库上搜索。
山东大学数据结构实验报告七
山东大学软件工程学院数据结构课程实验报告
学号：
姓名：
班级：
软件工程2014级2班
实验题目：
堆和搜索树
实验学时：
实验日期：
2015.12.2
实验目的：
掌握堆和搜索树的基本概念，插入、删除方法。
硬件环境：
实验室
软件环境：
VistualStudio2013
实验步骤与内容：
实验内容：
1、创建最大堆类。
最大堆的存储结构使用链表。
2、提供操作:
堆的插入、堆的删除。
堆的初始化。
Huffman树的构造。
二叉搜索树的构造。
3、接收键盘录入的一系列整数，输出其对应的最大堆、Huffman编码以及二叉搜索树。
4、堆排序。
代码体：
Binarytree.h
#ifndefBINARYTREE_H
#defineBINARYTREE_H
#include
usingnamespacestd;
#include"binarytreenode.h"
classBinaryTree{
friendclassBSTree;
friendclassHuffman;
public:
BinaryTree（）{root=0;num=0;}
boolIsEmpty（）{returnroot==0;}
boolRoot（int&x）;
voidMakeTree（constint&element,BinaryTree&left,BinaryTree&right）;
voidBreakTree（int&element,BinaryTree&left,BinaryTree&right）;
intHeight（）const{returnHeight（root）;}
intNumNode（）{num=1;NumNode（root）;returnnum;}
voidPreOrder（）{PreOrder（root）;cout<voidInOrder（）{InOrder（root）;cout<voidPostOrder（）{PostOrder（root）;cout<voidLevelOrder（）{LevelOrder（root）;cout<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
#include
#include
#include
usingnamespacestd;
#include"binarytree.h"
voidBinaryTree:
:
Visit（BinaryTreeNode*t）{
cout<data<<"";
}
voidBinaryTree:
:
PreOrder（BinaryTreeNode*t）{
stacks;
while（t）{
Visit（t）;
if（t->RightChild）s.push（t->RightChild）;
if（t->LeftChild）s.push（t->LeftChild）;
if（s.empty（））{
return;
}
else{
t=s.top（）;
s.pop（）;
}
}
}
voidBinaryTree:
:
InOrder（BinaryTreeNode*t）{
stacks;
BinaryTreeNode*pre=NULL;
while（t）{
if（t->LeftChild）{
if（pre==t->LeftChild）{
Visit（t）;
pre=t;
if（s.empty（））{
return;
}
else{
t=s.top（）;
s.pop（）;
}
}
elseif（t->LeftChild->RightChild）{
BinaryTreeNode*d=t->LeftChild->RightChild;
while（d->RightChild）{
d=d->RightChild;
}
if（pre==d）{
Visit（t）;
pre=t;
if（s.empty（））{
return;
}
else{
t=s.top（）;
s.pop（）;
}
}
else{
if（t->RightChild）s.push（t->RightChild）;
s.push（t）;
t=t->LeftChild;
}
}
else{
if（t->RightChild）s.push（t->RightChild）;
s.push（t）;
t=t->LeftChild;
}
}
elseif（t->RightChild）{
Visit（t）;
pre=t;
t=t->RightChild;
}
else{
Visit（t）;
pre=t;
if（s.empty（））{
return;
}
else{
t=s.top（）;
s.pop（）;
}
}
}
}
voidBinaryTree:
:
PostOrder（BinaryTreeNode*t）{
stacks;
BinaryTreeNode*pre=NULL;
while（t）{
if（t->RightChild）{
if（pre==t->RightChild）{
Visit（t）;
pre=t;
if（s.empty（））{
return;
}
else{
t=s.top（）;
s.pop（）;
}
}
else{
if（t->LeftChild）{
s.push（t）;
s.push（t->RightChild）;
t=t->LeftChild;
}
else{
s.push（t）;
t=t->RightChild;
}
}
}
elseif（t->LeftChild）{
if（pre==t->LeftChild）{
Visit（t）;
pre=t;
if（s.empty（））{
return;
}
else{
t=s.top（）;
s.pop（）;
}
}
else{
s.push（t）;
t=t->LeftChild;
}
}
else{
Visit（t）;
pre=t;
if（s.empty（））{
return;
}
else{
t=s.top（）;
s.pop（）;
}
}
}
}
voidBinaryTree:
:
LevelOrder（BinaryTreeNode*t）{
queueq;
while（t）{
Visit（t）;
if（t->LeftChild）q.push（t->LeftChild）;
if（t->RightChild）q.push（t->RightChild）;
if（q.empty（））{
return;
}
else{
t=q.front（）;
q.pop（）;
}
}
}
boolBinaryTree:
:
Root（int&x）{
if（root）{
x=root->data;
returntrue;
}
elsereturnfalse;
}
voidBinaryTree:
:
MakeTree（constint&element,BinaryTree&left,BinaryTree&right）{
root=newBinaryTreeNode（element,left.root,right.root）;
left.root=right.root=0;
}
voidBinaryTree:
:
BreakTree（int&element,BinaryTree&left,BinaryTree&right）{
if（!
root）{
cout<<"该树是空树"<}
else{
element=root->data;
left.root=root->LeftChild;
right.root=root->RightChild;
deleteroot;
root=0;
}
}
intBinaryTree:
:
Height（BinaryTreeNode*t）const{
if（!
t）return0;
inthl=Height（t->LeftChild）;
inthr=Height（t->RightChild）;
if（hl>hr）return++hl;
elsereturn++hr;
}
voidBinaryTree:
:
NumNode（BinaryTreeNode*t）{
queueq;
while（t）{
if（t->LeftChild）{
q.push（t->LeftChild）;
num++;
}
if（t->RightChild）{
q.push（t->RightChild）;
num++;
}
if（q.empty（））{
return;
}
else{
t=q.front（）;
q.pop（）;
}
}
}
Binarytreenode.h
#ifndefBINARYTREENODE_H
#defineBINARYTREENODE_H
classBinaryTreeNode{
friendclassBinaryTree;
friendclassBSTree;
friendclassHuffman;
public:
BinaryTreeNode（）{LeftChild=RightChild=0;}
BinaryTreeNode（constint&e）{data=e;LeftChild=RightChild=0;}
BinaryTreeNode（constint&e,BinaryTreeNode*l,BinaryTreeNode*r）{data=e;LeftChild=l;RightChild=r;}
private:
BinaryTreeNode*LeftChild,*RightChild;
intdata;
};
#endif
Bstree.h
#include"binarytree.h"
classBSTree:
publicBinaryTree{
public:
boolSearch（constint&k,int&e）const;
BSTree&Insert（constint&e）;
BSTree&Delete（constint&k,int&e）;
voidAscend（）{InOrder（）;}
};
Bstree.cpp
#include
usingnamespacestd;
#include"bstree.h"
boolBSTree:
:
Search（constint&k,int&e）const{
BinaryTreeNode*p=root;
while（p）{
if（kdata）
p=p->LeftChild;
elseif（k>p->data）
p=p->RightChild;
else{
e=p->data;
returntrue;
}
}
returnfalse;
}
BSTree&BSTree:
:
Insert（constint&e）{
BinaryTreeNode*p=root,*pp=0;
while（p）{
pp=p;
if（edata）
p=p->LeftChild;
elseif（e>p->data）
p=p->RightChild;
else{
return*this;
}
}
BinaryTreeNode*r=newBinaryTreeNode（e）;
if（root）{
if（edata）
pp->LeftChild=r;
else
pp->RightChild=r;
}
else
root=r;
return*this;
}
BSTree&BSTree:
:
Delete（constint&k,int&e）{
BinaryTreeNode*p=root,*pp=0;
while（p&&p->data!
=k）{
pp=p;
if（kdata）
p=p->LeftChild;
else
p=p->RightChild;
}
if（!
p）{
cout<<"错误!
搜索树中不存在该元素!
"<return*this;
}
e=p->data;
if（p->LeftChild&&p->RightChild）{
BinaryTreeNode*s=p->LeftChild,*ps=p;
while（s->RightChild）{
ps=s;
s=s->RightChild;
}
p->data=s->data;
p=s;
pp=ps;
}
BinaryTreeNode*c;
if（p->LeftChild）
c=p->LeftChild;
else
c=p->RightChild;
if（p==root）
root=c;
else{
if（p==pp->LeftChild）
pp->LeftChild=c;
else
pp->RightChild=c;
}
deletep;
return*this;
}
Heapnode.h
classHeapNode{
friendclassMaxHeap;
private:
HeapNode*parent,*left,*right;
intdata;
};
Huffman.h
#ifndefHUFFMAN_H
#defineHUFFMAN_H
#include
usingnamespacestd;
#include"binarytree.h"
classHuffman{
friendHuffmanHuffmanTree（int*,int）;
friendintmain（）;
friendclassMinHeap;
public:
operatorint（）const{returnweight;}
voidOutPut（）const;
voidHuOrder（BinaryTreeNode*p,stringstr）const;
private:
BinaryTreetree;
intweight;
};
#endif
Huffman.cpp
#include"huffman.h"
#include"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;
for（inti=1;iH.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->LeftChild&&tree.root->RightChild）{
stringstr="";
HuOrder（tree.root,str）;
}
else{
cout<data<<":
"<<"0"<}
}
voidHuffman:
:
HuOrder（BinaryTreeNode*p,stringstr）const{
if（p->data）{
cout<<"下标为"<data<<"的元素的Huffman编码:
——"<}
else{
HuOrder（p->LeftChild,str+"0"）;
HuOrder（p->RightChild,str+"1"）;
}
}
Maxheap.h
#include
usingnamespacestd;
#include"heapnode.h"
classMaxHeap{
public:
MaxHeap（）{root=0;size=0;}
~MaxHeap（）;
intSize（）const{returnsize;}
boolIsEmpty（）const{returnroot==0;}
intMax（）{if（size==0）{cout<<"该堆为空!
"<data;}
MaxHeap&Insert（constint&x）;
MaxHeap&DeleteMax（int&x）;
voidInitialize（inta[],intarraysize）;
voidOutPut（）;
private:
intFind（intk）;
voidClear（）;
intsize;
HeapNode*root;
};
Maxheap.cpp
#include
usingnamespacestd;
#include"maxheap.h"
MaxHeap:
:
~MaxHeap（）{
Clear（）;
}
MaxHeap&MaxHeap:
:
Insert（constint&x）{
if（!
size）{
root=newHeapNode（）;
root->data=x;
root->parent=root->left=root->right=0;
size++;
}
else{
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;
}
else{
r=r->right;
i=2*i+1;
}
}
if（size==2*i）{
r->left=newHeapNode（）;
r->left->data=x;
r->left->parent=r;
r->left-
升级会员 