HBLT可用于實現優先級隊列，并可實現兩個優先級隊列的合并操作.
(如發現錯誤請留言)
1
//高度優先左高樹(HBLT)實現
2#ifndef HBLT_H
3#define HBLT_H
4#include <queue>
5//定義HBLT節點結構
6template<class T>
7class HBLTNode
8
{
9
10public:
11HBLTNode(T &e,int s)
12
{
13data=e;
14sh=s;
15RightChild=LeftChild=NULL;
16
}
17
18public:
19 T data;
20 int sh;//高度因子
21 HBLTNode<T> *RightChild,*LeftChild;
22
};
23
24//定義HBLT樹結構
25template<class T>
26class HBLT
27{
28public:
29 HBLT(){size=0,root=NULL;}
30 virtual ~HBLT();
31 HBLT<T>& Insert(T e);//插入新元素
32 HBLT<T>& DeleteMax(T &e);//刪除并返回最大元素
33 HBLT<T>& Meld(HBLT<T>& x);
34 bool IsEmpty(){return root==NULL?true:false;}
35 void Initialize(T a[],int n);//對HBLT樹重新初始化
36 int Size(){return size;}
37private:
38
39 HBLTNode<T> *root;//根節點指針
40 int size;
41 void Meld(HBLTNode<T>*&x,HBLTNode<T>*y);//將以x，y為根的兩棵HBLT樹合并
42 void PostVisit(HBLTNode<T> *root);//對樹進行后序遍歷刪除節點
43
44};
45
46
47template<class T>
48HBLT<T>::~HBLT()
49{
50PostVisit(root);
51}
52//----------------------------------------------------------
53template<class T>
54void HBLT<T>::Meld(HBLTNode<T>*&x,HBLTNode<T>*y)
55{
56if(!y)//y為空樹
57 return;
58if(!x)//x為空樹
59{
60x=y;
61return;
62}
63
64if(x->data<y->data) swap(x,y);//保證x指向大值
65
66//遞歸合并x的右子樹與y
67Meld(x->RightChild,y);
68
69if(!x->LeftChild)//如果X的左子樹為空則將右子樹移向左邊
70{
71x->LeftChild=x->RightChild;
72x->RightChild=NULL;
73}
74else
75{
76if(x->LeftChild->sh<x->RightChild->sh)//左子樹沒有右子樹高
77{
78swap(x->LeftChild,x->RightChild);
79x->sh=x->RightChild->sh+1;
80}
81}//if
82
83}
84//-------------------------------------------------------------
85template<class T>
86HBLT<T>& HBLT<T>::Insert(T e)
87{
88HBLTNode<T> *NewNode=new HBLTNode<T>(e,1);
89Meld(root,NewNode);
90size++;
91return *this;
92}
93
94//-------------------------------------------------------------
95template<class T>
96HBLT<T>& HBLT<T>::DeleteMax(T &e)
97{
98
99e=root->data;
100HBLTNode<T> *Left=root->LeftChild;
101HBLTNode<T> *Right=root->RightChild;
102root=Left;
103Meld(root,Right);
104return *this;
105}
106
107//-------------------------------------------------------------
108template<class T>
109HBLT<T>& HBLT<T>::Meld(HBLT<T>& x)
110{
111Meld(root,x.root);
112x.root=NULL;
113size=size+x.size;
114return *this;
115}
116//-------------------------------------------------------------
117template<class T>
118void HBLT<T>::PostVisit(HBLTNode<T> *root)
119{
120if(root)
121{
122PostVisit(root->LeftChild);
123PostVisit(root->RightChild);
124delete root;
125}
126}
127//-------------------------------------------------------------
128template<class T>
129void HBLT<T>::Initialize(T a[],int n)
130{
131if(root)
132 PostVisit(root);//刪除以前的節點
133size=n;
134queue<HBLTNode<T>* > Q;
135for(int i=0;i<n;i++)
136{
137HBLTNode<T> *NewNode=new HBLTNode<T>(a[i],1);
138Q.push(NewNode);
139}
140
141for(i=1;i<=n-1;i++)
142{
143HBLTNode<T> *Node1 = Q.front();Q.pop();
144HBLTNode<T> *Node2 = Q.front();Q.pop();
145Meld(Node1,Node2);
146Q.push(Node1);
147}
148
149root = Q.front();
150}
151#endif
測試代碼：
MainApp.cpp
1
2#include <iostream>
3#include "HBLT.h"
4using namespace std;
5void main()
6{
7 int a[5]={6,8,3,6,1};
8 HBLT<int> hblt;
9 hblt.Insert(1).Insert(4).Insert(2);
10 hblt.Initialize(a,5);
11 HBLT<int> hblt2;
12 hblt2.Insert(11).Insert(7);
13 hblt.Meld(hblt2);
14 int out;
15 while(!hblt.IsEmpty())
16 {
17 hblt.DeleteMax(out);
18 cout<<out<<endl;
19 }
20cout<<"Size:"<<hblt.Size();
21}
posted on 2008-09-17 21:32
楊彬彬 閱讀(1562)
評論(0) 編輯 收藏 引用 所屬分類:
數據結構