这是我写的AVL树的实现，其中的Remove非算法已经编不下去了，
但其他的成员函数都已经通过测试了，这是在我感觉写了这么多的类中最难写的一个了，大家参考讨论：
#ifndef AVLTREE_H
#define AVLTREE_H
#include"LinkedStack.h"
////////////////////////////////////////////////////
//AVLNode结构 平衡二叉排序树的结点的定义
////////////////////////////////////////////////////
template<class T>
struct AVLNode
{
AVLNode<T>* left;
//左子树
AVLNode<T>* right;
//右子树
T data;
//数据域
//当前结点的平衡因子(即右子树高度减去左子树高度)
//如果是平衡的二叉排序树的话bf应该为1,0,-1
int bf;
//默认构造函数
AVLNode():left(NULL),right(NULL),bf(0){};
//带参数的构造函数
AVLNode(T d,AVLNode<T>* l=NULL,AVLNode<T>* r=NULL)
{data=d;left=l;right=r;bf=0;}
};
/////////////////////////////////////AVLNode结构结束
////////////////////////////////////////////////////
//AVLTree类模板
平衡二叉排序树树类的声明和定义
////////////////////////////////////////////////////
template<class T>
class AVLTree
{
protected:
//AVLTree<T>的根结点
AVLNode<T>* root;
//在子树subTree中搜索关键码为x的结点的指针
AVLNode<T>* Search(T x,AVLNode<T>*& subTree)const;
//非递归:把关键码为x的结点插入到二叉排序树subTree中
bool Insert(T x,AVLNode<T>*& subTree);
//递归:把关键码插入到以subTree为根的子树中去
bool InsertRev(T x,AVLNode<T>* subTree);
//把关键码为x的结点在树中删除
bool Remove(T x,AVLNode<T>*& subTree);
//释放子树所有结点的内存
void makeEmpty(AVLNode<T>* subTree);
void RotateL(AVLNode<T>*& ptr);
//对结点ptr进行左单旋操作
void RotateR(AVLNode<T>*& ptr);
//对结点ptr进行右单旋操作
void RotateLR(AVLNode<T>*& ptr);
//对结点ptr先左后右单旋
void RotateRL(AVLNode<T>*& ptr);
//对结点ptr先右后左单旋
int Height(AVLNode<T>* ptr)const;
//求树的高度
void DisplayAVL(AVLNode<T>* subTree);//递归:以广义表的形式显示该平衡二叉排序树
public:
AVLTree(){root=NULL;};
//默认空构造函数
AVLTree(int A[],int n); //带参数的构造函数
~AVLTree()
//析构函数,释放所有的结点的内存
{makeEmpty(root);};
Create(char* des);
//通过广义表描述字符串创建一个二叉搜索树
bool Insert(T x)
//插入关键码为x的结点
{return Insert(x,root);};
bool Remove(T x)
//删除关键码为x的结点
{return Remove(x,root);};
AVLNode<T>* Search(T x) //寻找关键码为x的结点的指针
{return Search(x,root);};
//友员重载输出运算符<<
friend ostream& operator<<(ostream& os,AVLTree<T>& R);
//成员重载输入运算符>>
friend istream& operator>>(istream& is,AVLTree<T>& R);
int Height()const;
//得到树的高度
};
///////////////////////////////AVLTree类模板声明结束
////////////////////////////////////////////////////
//带参数的构造函数
//通过数组里的数的序列一次构造一棵AVL树
////////////////////////////////////////////////////
template<class T>
AVLTree<T>::AVLTree(int A[],int n)
{
root=NULL;
//需要先把root根初始化为NULL
for(int i=0;i<n;i++)
Insert(A[i]);
};
////////////////////////////////带参数的构造函数结束
////////////////////////////////////////////////////
//Search()私有成员函数
//递归:在子树subTree中搜索具有关键码为x的指针结点
////////////////////////////////////////////////////
template<class T>
AVLNode<T>* AVLTree<T>::Search(T x,AVLNode<T>*& subTree)const
{
if(subTree!=NULL)
//如果子树不空
{
if(subTree->data==x)
return subTree;
else if(x<subTree->data) //递归在左子树中寻找
return Search(x,subTree->left);
else
//递归在右子树中寻找
return Search(x,subTree->right);
}
else
return NULL;
};
////////////////////////////////Search()私有函数结束
////////////////////////////////////////////////////
//makeEmpty()私有成员函数
//释放子树subTree所有结点的恶内存
////////////////////////////////////////////////////
template<class T>
void AVLTree<T>::makeEmpty(AVLNode<T>* subTree)
{
//即采用后序方式释放内存
if(subTree!=NULL)
{
//先递归释放左右子树的结点的内存
makeEmpty(subTree->right);
makeEmpty(subTree->left);
//释放根结点的内存
delete subTree;
};
};
/////////////////////////////makeEmpty()私有函数结束
////////////////////////////////////////////////////
//RotateL()私有成员函数
//实现对以ptr为轴的结点进行左单旋,即把ptr右边的子
//结点"提拔"上来,而自己本身向左边下滑,即逆时针旋转
////////////////////////////////////////////////////
template<class T>
void AVLTree<T>::RotateL(AVLNode<T>*& ptr)
{
AVLNode<T>* subL=ptr; //即将下放的结点指针
ptr=ptr->right;
//将指针指向要旋转的结点
subL->right=ptr->left;//把要旋转的结点的左子树置为subL结点的右子树
ptr->left=subL;
//把subL置为要旋转的那个结点的左子树
ptr->bf=0;
//ptr结点的平衡因子变为了0
subL->bf=0;
//subL结点的平衡因子变为了0
};
///////////////////////////////RotateL()私有函数结束
////////////////////////////////////////////////////
//RotateR()私有成员函数
//实现对以ptr为轴的结点进行右单旋，即把ptr左边的子
//结点"提拔"上来，而自己本身向右边下滑,即顺时针旋转
////////////////////////////////////////////////////
template<class T>
void AVLTree<T>::RotateR(AVLNode<T>*& ptr)
{
AVLNode<T>* subR=ptr; //subR即将要被右旋
ptr=ptr->left;
//ptr指向旋转的结点
subR->left=ptr->right;//把ptr的右子树给subR结点的左子树
ptr->right=subR;
//subR成为ptr的右子树
ptr->bf=0;
//ptr,subR两个结点旋转后平衡因子为0
subR->bf=0;
};
///////////////////////////////RotateR()私有函数结束
////////////////////////////////////////////////////
//RotateLR()私有成员函数
//对以ptr为根结点的子树进行先左后右旋转
////////////////////////////////////////////////////
template<class T>
void AVLTree<T>::RotateLR(AVLNode<T>*& ptr)
{
AVLNode<T>* subR=ptr;
//要进行右旋的结点
AVLNode<T>* subL=subR->left;//要进行左旋的结点
ptr=subL->right;
//旋转轴结点
//先对subL进行左旋
subL->right=ptr->left;
ptr->left=subL;
if(ptr->bf<=0)
//如果是左子树高
subL->bf=0;
else
//如果是右子树高
subL->bf=-1;
//再对subR进行右旋
subR->left=ptr->right;
ptr->right=subR;
if(ptr->bf<=0)
//如果是左子树高
subR->bf=1;
else
//如果是右子树高
subL->bf=0;
//对ptr平衡化结束
ptr->bf=0;
};
//////////////////////////////RotateLR()私有函数结束
////////////////////////////////////////////////////
//RotateRL()私有成员函数
//对以ptr为根的子树进行先右后左的旋转
////////////////////////////////////////////////////
template<class T>
void AVLTree<T>::RotateRL(AVLNode<T>*& ptr)
{
AVLNode<T>* subL=ptr;
//要进行左旋的结点指针
AVLNode<T>* subR=ptr->right;//要进行右旋的结点指针
ptr=subR->left;
//最底层失去平衡的结点
//先进行右旋
subR->left=ptr->right;
ptr->right=subR;
if(ptr->bf>0)
//如果ptr是右子树高
subR->bf=0;
//subR结点的平衡因子就是0
else
//如果ptr是左子树高
subR->bf=1;
//subL结点的平衡因子就是1
//再进行左旋
subL->right=ptr->left;
ptr->left=subL;
if(ptr->bf==1)
//如果ptr是右子树高
subL->bf=-1;
else
//如果ptr是左子树高
subL->bf=0;
//最后不平衡的结点得以平衡
ptr->bf=0;
};
//////////////////////////////RotateRL()私有函数结束
////////////////////////////////////////////////////
//Insert()私有成员函数(非递归算法)
//在已经平衡的二叉树ptr中插入一个结点,并保持原有的平衡
//如果插入成功返回true,否则返回false
////////////////////////////////////////////////////
template<class T>
bool AVLTree<T>::Insert(T x,AVLNode<T>*& ptr)
{
//首先不考虑平衡与否把结点插入到二叉树中去
//并把从根到叶寻找插入位置经过的路径所有的结点保存入堆栈
//保存从插入位置到根结点的所有的结点的堆栈
LinkedStack<AVLNode<T>* > Path;
AVLNode<T>* pr;
//pr:p的父结点指针
AVLNode<T>* p;
//p:新插入的结点指针
AVLNode<T>* q;
//q:插入后平衡前pr的子树根结点
//寻找插入的位置并把经过的结点保存入堆栈
AVLNode<T>* cusor=ptr;
//游标指针从根结点开始
while(cusor!=NULL)
{
if(x==cusor->data)
//如果要插入的结点已经存在
return false;
Path.Push(cusor);
//把经过的结点压入堆栈
if(x>cusor->data)
//大于则从右子树继续往下
cusor=cusor->right;
else
//小于则从左子树继续往下
cusor=cusor->left;
};
//依据x的值新建结点p,并把p插入其中
p=new AVLNode<T>(x);
//依据关键码x新建一个结点p
if(ptr==NULL)
//如果本来是空树
{ptr=p;return true;}
Path.getTop(pr);
//获取要插入结点p的父结点pr
if(p->data<pr->data)
//如果小于父结点pr
pr->left=p;
//则在左子树插入
else
//如果大于父结点pr
pr->right=p;
//则在右子树插入
//调整平衡因子,并对最小不平衡子树进行平衡化处理
while(!Path.IsEmpty())
//循环条件:未到跟结点
{
//插入结点后调整相应结点的平衡因子
Path.Pop(pr);
//从堆栈中取出一个根结点
if(p==pr->left)
//如果新插入的p是pr的左子树
pr->bf--;
//平衡因子减1
else if(p==pr->right)
//如果新插入的p是pr的右子树
pr->bf++;
//平衡因子加1
//根据结点pr的平衡因子作相应的平衡化处理
if(pr->bf==0)
//p是在pr的矮的子树上插入的
break;
//无需作平衡化处理
else if(abs(pr->bf)==1)
//pr本身不需要平衡化处理，但影响其父结点
p=pr;
//回溯pr的父结点,子树p的高度已经加1了
else
//如果|pr->bf|==2,说明在高的那棵子树上插入了
{
if(pr->bf==2)
//如果pr是右子树高
{
q=pr->right;
//得到pr的右子树的根结点
if(q->bf==1)
//如果右子树是右高,则pr属于RR型子树
RotateL(pr);
//对pr进行左单旋处理
else
//如果右子树是左高,则pr属于RL型子树
RotateRL(pr);
//对pr进行先右后左双旋处理
}
else
//如果pr是左子树高
{
q=pr->left;
//得到pr的左子树的根结点
if(q->bf==1)
//如果左子树是右高则pr属于LR型子树
RotateLR(pr);
//对pr进行先左后右双旋处理
else
//如果左子树是左高则pr属于型子树
RotateR(pr);
//对pr进行右单旋处理
};
break;
//因为对子树pr进行平衡化处理后子树的高度不变
//所以可以直接退出了而不要继续往上处理了
};
};
//把平衡化后的子树和原来的树整体连接起来
if(Path.IsEmpty())
//如果已经到树的根结点了
ptr=pr;
else
//如果没有到根结点
{
Path.getTop(p);
//得到最小化不平衡子树平衡化后的父结点
if(pr->data<p->data)
p->left=pr;
//在左子树插入
else
p->right=pr;
//在右子树插入
};
return true;
//插入成功
};
////////////////////////////////Insert()私有函数结束
////////////////////////////////////////////////////
//InsertRev()私有成员函数
//递归:插入具有制定关键码的结点
////////////////////////////////////////////////////
template<class T>
bool AVLTree<T>::InsertRev(T x,AVLNode<T>*& subTree)
{
//如果子树为空
if(subTree==NULL)
{
//依照关键码x新建一个结点
AVLNode<T>* p=new AVLNode<T>(x);
//直接把该结点挂上子树subTree
subTree=p;
//插入成功
return true;
};
//如果在右子递归树插入
if(x<subTree->data)
{
InsertRev(x,subbTree->left);
}
//如果在左子树递归插入
else if(x>subTree->data)
{
InsertRev(x,subTree->right);
}
//如果等于说明插入失败
else
return false;
};
/////////////////////////////////InsertRev()函数结束
////////////////////////////////////////////////////
//Remove()私有成员函数
//非递归:删除已经平衡的AVL树中的具有指定关键码的结点
//注意:本代码还未编写成功,是在想不出来了
////////////////////////////////////////////////////
template<class T>
bool AVLTree<T>::Remove(T x,AVLNode<T>*& ptr)
{
//首先在AVL树中找到要删除的那个结点
LinkedStack<AVLNode<T>*> Stack;
//父结回溯用的堆栈
AVLNode<T>* pr=ptr;
//父结点指针
AVLNode<T>* p;
//要删除的结点的指针
AVLNode<T>* q;
//子树的根结点
while(p!=NULL)
{
Stack.Push(p);
//把经过的结点压入堆栈
if(x<p->data)
//如果在左子树删除
p=p->left;
else if(x>p->data)
//如果在右子树删除
p=p->right;
else
break;
//如果已经找到
};
if(p==NULL)
//说明没有找到要删除的结点
return false;
//采用非递归的方式把已经找到的结点删除并调整平衡因子
while(!Stack.IsEmpty())
//从被删除的结点开始向上回溯
{
if(p->left==NULL
//如果左右子树都是空的
&& p->right==NULL)
//即删除的是叶子结点
{
Stack.Pop(pr);
Stack.getTop(pr);
//从堆栈中获取p的父结点的指针pr
if(pr->left==p)
//如果p是pr的左子树
{
pr->left==NULL;
//把pr的左指针域置空,删除结点p
delete p;
//释放结点p的内存
pr->bf++;
//原p的父结点pr的平衡因子加1
}
else if(pr->right==p)
//如果p是pr的右子树
{
pr->right==NULL;
//把pr的右指针域置空,删除结点p
delete p;
//释放结点p的空间
pr->bf--;
//原p的父结点pr的平衡因子减1
}
}
else if(p->left!=NULL
//如果左右子女都存在
&& p->right!=NULL)
{
q=p;
//以q为游标,从p开始
while(q->left!=NULL)
//寻找p的右子树中序下的第一个结点
q=q->left;
p->data=q->data;
//把用结点q替代结点p的位置
p=q;
//问题转向删除结点q了
}
};
};
////////////////////////////////Remove()私有函数结束
////////////////////////////////////////////////////
//递归:Height()私有成员函数
得到树的高度
////////////////////////////////////////////////////
template<class T>
int AVLTree<T>::Height(AVLNode<T>* subTree)const
{
if(subTree==NULL)
return 0;
//如果根结点为空,则树的高度为0
else
//如果树不空
{
int LH=Height(subTree->left); //递归得到左子树的高度
int RH=Height(subTree->right);//递归得到右子树的高度
if(LH>RH)
return LH+1;
//如果左子树更高
else
return RH+1;
//如果右子树更高
};
};
////////////////////////////////Height()私有函数结束
////////////////////////////////////////////////////
//Display()私有成员函数
//递归:以广义表的形式显示该平衡二叉排序树的内容
////////////////////////////////////////////////////
template<class T>
void AVLTree<T>::DisplayAVL(AVLNode<T>* subTree)
{
if(subTree!=NULL)
{
//如果是叶子结点
if(subTree->left==NULL && subTree->right==NULL)
//直接显示而后面不用加括号
cout<<subTree->data;
//如果是子表
else
{
cout<<subTree->data;
//递归显示子树的内容
cout<<"(";
DisplayAVL(subTree->left);
cout<<",";
DisplayAVL(subTree->right);
cout<<")";
};
};
};
///////////////////////////////Display()私有函数结束
////////////////////////////////////////////////////
//友元重载<<输出运算符 以广义表的形式显示树的内容
////////////////////////////////////////////////////
template<class T>
ostream& operator<<(ostream& os,AVLTree<T>& R)
{
R.DisplayAVL(R.root);
return os;
};
//////////////////////////////////////<<友元重载结束
////////////////////////////////////////////////////
//友元重载>>输入运算符
////////////////////////////////////////////////////
template<class T>
istream& operator>>(istream& is,AVLTree<T>& R)
{
T x;
is>>x;
//键盘输入一个关键码
R.Insert(x);
//把该关键码创建成结点插入其中
return is;
};
//////////////////////////////////////>>友元重载结束
#endif
