高度优先左高树与堆的性质类似，都可有作为优先级队列的底层结构。但应用高度优先左高树可以很容易的实现两个优先级队列的合并操作。
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
杨彬彬 阅读(1548)
评论(0) 编辑 收藏 引用