随笔 - 8  文章 - 26  trackbacks - 0
<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(4)

随笔档案

文章分类

文章档案

相册

C++语言

搜索

  •  

最新评论

阅读排行榜

评论排行榜

高度优先左高树与堆的性质类似,都可有作为优先级队列的底层结构。但应用高度优先左高树可以很容易的实现两个优先级队列的合并操作。

  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 杨彬彬 阅读(1522) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理