堆、霍夫曼編碼、搜索樹

1、/*一、實驗目的1、掌握堆和搜索樹的基本概念，插入、刪除方法。二、實驗內容1、創(chuàng)建最大堆類。最大堆的存儲結構使用鏈表。2、提供操作:堆的插入、堆的刪除。堆的初始化。Huffman樹的構造。二叉搜索樹的構造。3、接收鍵盤錄入的一系列整數，輸出其對應的最大堆、Huffman編碼以及二叉搜索樹。4、堆排序。*/ #include <iostream>#include <string.h>#include<cmath>#include<queue>using namespace std;/二叉樹節(jié)點類 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是指向根節(jié)點的指針，last是指向最后一個節(jié)點的指針 ,last_p是指向最后一個節(jié)點的父節(jié)點的指針 int state;/當前狀態(tài)下的節(jié)點數 void InsertAdjust(BinaryTreeNode *u, int k, int i,BinaryTreeNode *temp);/插入元素后重構最大堆 void DeleteAdjust(BinaryTreeNode *

7、u);/重構最大堆 BinaryTreeNode* FindPLast(BinaryTreeNode *u,int k,int i);/查找最后一個節(jié)點的父節(jié)點 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)/創(chuàng)建一個最大堆并初始化 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)/節(jié)點數大于一 int k = (int) (log(double)(state) / log(2.0) + 1;/層數 int index = state - (int) (pow(2.0, k - 1) - 1); /節(jié)點數 int p_index = index / 2 + 1;/父節(jié)點數 BinaryTreeNode *temp = new BinaryTreeNode (x);/創(chuàng)建一個臨時節(jié)點存儲x last =

10、 temp;/最后一個節(jié)點指針指向臨時節(jié)點 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/節(jié)點數小于一 root = new BinaryTreeNode(x); last=last_p=root; state+; return *this; /查找最后一個有孩子的節(jié)點 ，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為根節(jié)點，k為層數，i為當前位置 ，temp為插入的節(jié)點 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)/如果根節(jié)點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;/只有一個節(jié)點 state=0;/清空節(jié)點數 root=0;/刪除根節(jié)點 else x = root->data; root->data = last->data; /刪除根節(jié)點 int k =(int)(log(double)(state)/log(double)(2)+ 1;/層數 int

16、index = state-(int)(pow(2.0, k - 1) - 1);/判斷要刪除的最后一個節(jié)點是其父節(jié)點的左孩子還是右孩子的變量 DeleteAdjust(root); /刪除最后一個節(jié)點 if(index%2) last_p->LeftChild=0;/最后一個節(jié)點是左孩子 else last_p->RightChild=0; /最后一個節(jié)點是右孩子 delete last;/刪除最后一個節(jié)點 state-; /節(jié)點數減一 /重新定義最后一個節(jié)點的父節(jié)點指針和最后一個節(jié)點的指針 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)/最后一個父節(jié)點沒有右孩子 last=last_p->LeftChild;/賦值最后一個節(jié)點的指針 else last=last_p-

18、>RightChild;/最后一個父節(jié)點有右孩子 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 );/選出兩個權值最小的節(jié)點 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個節(jié)點的霍夫曼樹

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、節(jié)點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<<