高度優先左高樹與堆的性質類似，都可有作為優先級隊列的底層結構。但應用高度優先左高樹可以很容易的實現兩個優先級隊列的合并操作。
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);
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);//刪除以前的節點
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
楊彬彬 閱讀(1552)
評論(0) 編輯 收藏 引用