高度優(yōu)先左高樹與堆的性質(zhì)類似，都可有作為優(yōu)先級隊列的底層結(jié)構(gòu)。但應(yīng)用高度優(yōu)先左高樹可以很容易的實現(xiàn)兩個優(yōu)先級隊列的合并操作。
1
//高度優(yōu)先左高樹(HBLT)實現(xiàn)
2#ifndef HBLT_H
3#define HBLT_H
4#include <queue>
5//定義HBLT節(jié)點結(jié)構(gòu)
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樹結(jié)構(gòu)
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;//根節(jié)點指針
40 int size;
41 void Meld(HBLTNode<T>*&x,HBLTNode<T>*y);//將以x，y為根的兩棵HBLT樹合并
42 void PostVisit(HBLTNode<T> *root);//對樹進(jìn)行后序遍歷刪除節(jié)點
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);
104--size;
105return *this;
106}
107
108//-------------------------------------------------------------
109template<class T>
110HBLT<T>& HBLT<T>::Meld(HBLT<T>& x)
111{
112Meld(root,x.root);
113x.root=NULL;
114size=size+x.size;
115return *this;
116}
117//-------------------------------------------------------------
118template<class T>
119void HBLT<T>::PostVisit(HBLTNode<T> *root)
120{
121if(root)
122{
123PostVisit(root->LeftChild);
124PostVisit(root->RightChild);
125delete root;
126}
127}
128//-------------------------------------------------------------
129template<class T>
130void HBLT<T>::Initialize(T a[],int n)
131{
132if(root)
133 PostVisit(root);//刪除以前的節(jié)點
134size=n;
135queue<HBLTNode<T>* > Q;
136for(int i=0;i<n;i++)
137{
138HBLTNode<T> *NewNode=new HBLTNode<T>(a[i],1);
139Q.push(NewNode);
140}
141
142for(i=1;i<=n-1;i++)
143{
144HBLTNode<T> *Node1 = Q.front();Q.pop();
145HBLTNode<T> *Node2 = Q.front();Q.pop();
146Meld(Node1,Node2);
147Q.push(Node1);
148}
149
150root = Q.front();
151}
152#endif
posted on 2008-09-18 17:27
楊彬彬 閱讀(1567)
評論(0) 編輯 收藏 引用