堆、霍夫曼编码、搜索树

1、/*一、实验目的1、掌握堆和搜索树的基本概念，插入、删除方法。二、实验内容1、创建最大堆类。最大堆的存储结构使用链表。2、提供操作:堆的插入、堆的删除。堆的初始化。Huffman树的构造。二叉搜索树的构造。3、接收键盘录入的一系列整数，输出其对应的最大堆、Huffman编码以及二叉搜索树。4、堆排序。*/ #include <iostream>#include <string.h>#include<cmath>#include<queue>using namespace std;/二叉树节点类 class BinaryTreeNode publi

2、c:BinaryTreeNode() LeftChild=RightChild=0; BinaryTreeNode(const int & e)data=e;LeftChild=RightChild=0;BinaryTreeNode(const int& e,BinaryTreeNode *l,BinaryTreeNode *r) data=e;LeftChild=l;RightChild=r;int data;BinaryTreeNode *LeftChild,*RightChild; /逐层遍历 输出 void Travel(BinaryTreeNode* roots) q

3、ueue<BinaryTreeNode *> q; while(roots) cout<<roots->data<<" " if(roots->LeftChild)q.push(roots->LeftChild); if(roots->RightChild)q.push(roots->RightChild); try roots=q.front(); q.pop (); catch(.) return; /前序遍历 输出 void PrOrder(BinaryTreeNode* roots)if(roots)

4、 cout<<roots->data<<" " PrOrder(roots->LeftChild); PrOrder(roots->RightChild); /中序遍历 输出 void InOrder(BinaryTreeNode* roots)if(roots) InOrder(roots->LeftChild); cout<<roots->data<<" " InOrder(roots->RightChild);/*定义最大堆类 */ class MaxHeap pu

5、blic:MaxHeap() root = 0; state = 0;/定义层数 void MakeHeap(int element, MaxHeap& left, MaxHeap& right); /返回最大值 int Max() if (!root) return 0; return root->data; MaxHeap& Insert(const int& x);/插入元素 MaxHeap& DeleteMax(int& x);/删除最大元素，根 MaxHeap& Initialize(int a, int n);/初始化最

6、大堆 void Deactivate()heap=0;/删除最大堆 void HeapSort(int a,int n);/最大堆排序 BinaryTreeNode *root, *last,*last_p; /root是指向根节点的指针，last是指向最后一个节点的指针 ,last_p是指向最后一个节点的父节点的指针 int state;/当前状态下的节点数 void InsertAdjust(BinaryTreeNode *u, int k, int i,BinaryTreeNode *temp);/插入元素后重构最大堆 void DeleteAdjust(BinaryTreeNode *

7、u);/重构最大堆 BinaryTreeNode* FindPLast(BinaryTreeNode *u,int k,int i);/查找最后一个节点的父节点 private: MaxHeap *heap;/合并最大堆 void MaxHeap:MakeHeap(int element, MaxHeap& left, MaxHeap& right) root = new BinaryTreeNode(element, left.root, right.root); left.root = right.root = 0; last=last_p=root; state+; /最

8、大堆的初始化MaxHeap& MaxHeap:Initialize(int a, int n) MaxHeap LMaxHeap,RMaxHeap; MakeHeap(a0,LMaxHeap,RMaxHeap); for(int i=1;i<n;i+) Insert(ai); return *this;/堆排序 void MaxHeap:HeapSort(int * a,int n)/创建一个最大堆并初始化 MaxHeap maxHeap;maxHeap.Initialize(a,n);/从最大堆中逐个抽取元素int x;for(int i=n-1;i>=0;i-) max

9、Heap.DeleteMax(x); ai=x;/最大堆的插入 MaxHeap& MaxHeap:Insert(const int& x) if(root)/节点数大于一 int k = (int) (log(double)(state) / log(2.0) + 1;/层数 int index = state - (int) (pow(2.0, k - 1) - 1); /节点数 int p_index = index / 2 + 1;/父节点数 BinaryTreeNode *temp = new BinaryTreeNode (x);/创建一个临时节点存储x last =

10、 temp;/最后一个节点指针指向临时节点 if (index = (int) (pow(2.0, k - 1) p_index = 1; InsertAdjust(root, k, p_index, temp); else InsertAdjust(root, k - 1, p_index, temp);else/节点数小于一 root = new BinaryTreeNode(x); last=last_p=root; state+; return *this; /查找最后一个有孩子的节点 ，k为层数，i为当前位置 BinaryTreeNode* MaxHeap:FindPLast(Bin

11、aryTreeNode *u,int k,int i) if(k<=1) return u; else int n=(int)pow(2.0,k-1); int s=n/2; if(i<=s) return FindPLast(u->LeftChild,k-1,i); else return FindPLast(u->RightChild,k-1,i-s); /临时排序 ，u为根节点，k为层数，i为当前位置 ，temp为插入的节点 void MaxHeap:InsertAdjust(BinaryTreeNode *u, int k, int i,BinaryTreeNo

12、de *temp) int half = (int) pow(2.0, k - 2); if (u->data < temp->data) swap(u->data, temp->data); if (!u->LeftChild | !u->RightChild)/如果根节点u不是有两个孩子 if (!u->LeftChild) /把temp插到左孩子上 u->LeftChild = temp; last_p=u; state+; else /把temp插到右孩子上 u->RightChild = temp; last_p=u; st

13、ate+; else /向左向右递归 if (i <= half) InsertAdjust(u->LeftChild, k - 1, i, temp); else InsertAdjust(u->RightChild, k - 1, i - half, temp); /最大堆的重构 void MaxHeap:DeleteAdjust(BinaryTreeNode *u) if (!u->LeftChild && !u->RightChild) /没有孩子 return; else if(u->LeftChild && u-&

14、gt;RightChild)/有两个孩子 if (u->LeftChild->data > u->RightChild->data) if (u->data < u->LeftChild->data) swap(u->data, u->LeftChild->data); DeleteAdjust(u->LeftChild); else if (u->data < u->RightChild->data)/只有一个孩子 swap(u->data, u->RightChild->

15、data); DeleteAdjust(u->RightChild); /删除最大元素 MaxHeap& MaxHeap:DeleteMax(int& x) if (!root) exit(1);/空树 else if(!last)x=root->data;/只有一个节点 state=0;/清空节点数 root=0;/删除根节点 else x = root->data; root->data = last->data; /删除根节点 int k =(int)(log(double)(state)/log(double)(2)+ 1;/层数 int

16、index = state-(int)(pow(2.0, k - 1) - 1);/判断要删除的最后一个节点是其父节点的左孩子还是右孩子的变量 DeleteAdjust(root); /删除最后一个节点 if(index%2) last_p->LeftChild=0;/最后一个节点是左孩子 else last_p->RightChild=0; /最后一个节点是右孩子 delete last;/删除最后一个节点 state-; /节点数减一 /重新定义最后一个节点的父节点指针和最后一个节点的指针 k = (int)(log(double)(state-1)/log(double)(2

17、)+ 1; index = state - 1 - (int)(pow(2.0, k - 1) - 1); int p_index = index / 2 + 1; if (index = (int) (pow(2.0, k - 1) p_index=1; last_p=FindPLast(root,k,p_index); else last_p=FindPLast(root,k-1,p_index); if(!last_p->RightChild)/最后一个父节点没有右孩子 last=last_p->LeftChild;/赋值最后一个节点的指针 else last=last_p-

18、>RightChild;/最后一个父节点有右孩子 return *this;/*Huffman类 */ class HuffmanTreeNodepublic:int weight;/权重int parent,lchild,rchild; ; typedef HuffmanTreeNode * HuffmanTree;/声明一个HuffmanTreeNode类型的HuffmanTree HuffmanTree HuffmanCoding(char* &HC,int w,int a,int n);/Huffman编码void Select(HuffmanTree HT,int n,

19、int&s1,int&s2); void PrintHffmanCode(char* &HC,int w,int code,int codeLen,int a,int aLen );/选出两个权值最小的节点 void Select(HuffmanTree HT,int n,int&s1,int&s2)int i=1,j;while(HTi.parent!=0) i+; j=i+1;while(HTj.parent!=0) j+;if(HTi.weight>HTj.weight) s1=j;/s1为权重小的 s2=i;else s1=i; s2=j;

20、i=j+1;while(i<=n) if(HTi.parent!=0) i+; else if(HTi.weight<HTs1.weight) s2=s1; s1=i; else if(HTi.weight<HTs2.weight) s2=i; i+;/Huffman编码 HuffmanTree HuffmanCoding(char *& HC,int w,int a,int n)int i,start,c,f;HuffmanTreeNode *p;char *cd;if(n<1)return NULL;int m=2*n-1;/定义一个有m+1个节点的霍夫曼树

21、HuffmanTree HT=new HuffmanTreeNodem+1; /初始化for(p=HT+1,i=1;i<=n;i+,p+) p->weight=wi-1; p->lchild=0; p->rchild=0; p->parent=0; int s1,s2;for(;i<=m;+i) Select(HT,i-1,s1,s2); HTs1.parent=i; HTs2.parent=i; HTi.parent=0; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight;/父

22、节点weight值为左右孩子的权值之和 HC=new char* n;cd=new charn; cdn-1='0' for(i=1;i<=n;+i) start=n-1; for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) if(HTf.lchild=c) cd-start='0' else cd-start='1' HCi-1=new charn-start; strcpy(HCi-1,&cdstart); return HT; void PrintHffmanCode(char* &

23、HC,int w,int code,int codeLen,int a,int aLen ) HuffmanTree HT=HuffmanCoding(HC,w,code,codeLen); for(int r=0;r<codeLen;r+) cout<<coder<<"的字符的赫夫曼编码为:"<<HCr<<endl;/*二叉搜索树 */class DBSTreepublic :DBSTree()root=0;BinaryTreeNode * root;DBSTree & BSInitialize(int a,i

24、nt len); DBSTree & BSInsert(const int& e);/初始化 DBSTree & DBSTree:BSInitialize(int a,int len) for(int i=0;i<len;i+) BSInsert(ai); return *this;/插入元素 DBSTree & DBSTree:BSInsert(const int& e)BinaryTreeNode *p=root,*pp=0;while(p) pp=p; if(e<p->data) p=p->LeftChild; else i

25、f(e>p->data) p=p->RightChild;BinaryTreeNode * r=new BinaryTreeNode(e);if(root) if(e<pp->data) pp->LeftChild=r; else pp->RightChild=r;else root=r;return *this;int main()MaxHeap maxHeap;/声明一个最大堆对象 DBSTree bstree;int s, n,sel,Alen;char *codeA;int* IntA,* w;/IntA存储Huffman字符，w存储字符对应的

26、权值 int *a;int len;int F=1;while(F)int t;cout<<"输入题号：1.最大堆 2.Huffman 3.二叉搜索树 0.退出"<<endl;cin>>t;if(t=1)cout<<"输入最大堆元素个数："cin>>len;cout<<endl; a=new intlen;for(int i=0;i<len;i+) cout<<"输入第"<<i+1<<"个元素" cin

27、>>ai;maxHeap.Initialize(a,len);/初始化一个最大堆 int T=1;while(T)cout<<"最大堆操作:1.堆排序 2.输出最大堆 3.插入元素 4.删除最大元素 0.退出"<<endl;int D;cin>>D;switch(D)case 0:T=0;break;case 1:maxHeap.HeapSort(a,len);for(int h=0;h<len;h+) cout <<ah<<" " cout <<endl;brea

28、k;case 2: cout<<"初始化层次遍历输出最大堆：" Travel(maxHeap.root); cout<<endl; cout<<"前序遍历输出最大堆：" PrOrder(maxHeap.root); cout<<endl; break;case 3:cout<<"输入插入元素：" cin>>s; maxHeap.Insert(s); cout<<"插入元素后层次遍历输出最大堆：" Travel(maxHeap.root); cout<<endl; cout<<"插入元素后前序遍历输出最大堆：" PrOrder(maxHeap.root); cout<<