C语言数据结构之平衡二叉树（AVL树）实现方法示例

2023-09-17 15:37:04 302

本文实例讲述了C语言数据结构之平衡二叉树（AVL树）实现方法。分享给大家供大家参考，具体如下：

AVL树是每个结点的左子树和右子树的高度最多差1的二叉查找树。

要维持这个树，必须在插入和删除的时候都检测是否出现破坏树结构的情况。然后立刻进行调整。

看了好久，网上各种各种的AVL树，千奇百怪。

关键是要理解插入的时候旋转的概念。

//
//AvlTree.h
//HelloWorld
//Createdbyfeiyin001on17/1/9.
//Copyright(c)2017年FableGame.Allrightsreserved.
//
#ifndef__HelloWorld__AvlTree__
#define__HelloWorld__AvlTree__
#include
namespaceFable
{
intmax(inta,intb)
{
returna>b?a:b;
}
//二叉查找树，对于Comparable,必须实现了><=的比较
template
classAvlTree
{
public:
//构造函数
AvlTree(){}
//复制构造函数
AvlTree(constAvlTree&rhs)
{
root=clone(rhs.root);
}
//析构函数
~AvlTree()
{
makeEmpty(root);
}
//复制赋值运算符
constAvlTree&operator=(constAvlTree&rhs)
{
if(this!=&rhs)
{
makeEmpty(root);//先清除
root=clone(rhs.root);//再复制
}
return*this;
}
//查找最小的对象
constComparable&findMin()const
{
findMin(root);
}
//查找最大的对象
constComparable&findMax()const
{
findMax(root);
}
//是否包含了某个对象
boolcontains(constComparable&x)const
{
returncontains(x,root);
}
//树为空
boolisEmpty()const
{
returnroot==nullptr;
}
//打印整棵树
voidprintTree()const
{
printTree(root);
}
//清空树
voidmakeEmpty()
{
makeEmpty(root);
}
//插入某个对象
voidinsert(constComparable&x)
{
insert(x,root);
}
//移除某个对象
voidremove(constComparable&x)
{
remove(x,root);
}
private:
structAvlNode
{
Comparableelement;
AvlNode*left;
AvlNode*right;
intheight;
AvlNode(constComparable&theElement,AvlNode*lt,AvlNode*rt,inth=0)
:element(theElement),left(lt),right(rt),height(h){}
};
typedefAvlNode*AvlNodePtr;
AvlNodePtrroot;//根结点
//顺时针旋转
voidclockwiseRotate(AvlNodePtr&a)
{
AvlNodePtrb=a->left;//左叶子
a->left=b->right;//a的左叶子变为b的右叶子，b本来的子结点都比a小的。
b->right=a;//b的右结点指向a，b的高度上升了。
a->height=max(height(a->left),height(a->right))+1;//重新计算a的高度
b->height=max(height(b->left),a->height)+1;//重新计算b的高度
a=b;//a的位置现在是b，当前的根结点
}
//逆时针旋转
voidantiClockWiseRotate(AvlNodePtr&a)
{
AvlNodePtrb=a->right;//右结点
a->right=b->left;//a接收b的左结点
b->left=a;//自己成为b的左结点
a->height=max(height(a->left),height(a->right))+1;//计算高度
b->height=max(b->height,height(a->right))+1;//计算高度
a=b;//新的根结点
}
//对左边结点的双旋转
voiddoubleWithLeftChild(AvlNodePtr&k3)
{
antiClockWiseRotate(k3->left);//逆时针旋转左结点
clockwiseRotate(k3);//顺时针旋转自身
}
//对右边结点的双旋转
voiddoubleWithRightChild(AvlNodePtr&k3)
{
clockwiseRotate(k3->right);//顺时针旋转有节点
antiClockWiseRotate(k3);//逆时针旋转自身
}
//插入对象，这里使用了引用
voidinsert(constComparable&x,AvlNodePtr&t)
{
if(!t)
{
t=newAvlNode(x,nullptr,nullptr);
}
elseif(xelement)
{
insert(x,t->left);//比根结点小，插入左边
if(height(t->left)-height(t->right)==2)//高度差达到2了
{
if(xleft->element)//插入左边
{
clockwiseRotate(t);//顺时针旋转
}
else
{
doubleWithLeftChild(t);//双旋转
}
}
}
elseif(x>t->element)
{
insert(x,t->right);//比根结点大，插入右边
if(height(t->right)-height(t->left)==2)//高度差达到2
{
if(t->right->elementheight=max(height(t->left),height(t->right))+1;//计算结点的高度
}
voidremoveMin(AvlNodePtr&x,AvlNodePtr&t)const
{
if(!t)
{
return;//找不到
}
if(t->left)
{
removeMin(t->left);//使用了递归的方式
}
else
{
//找到最小的结点了
x->element=t->element;
AvlNodePtroldNode=t;
t=t->right;
deleteoldNode;//删除原来要删除的结点
}
if(t)
{
t->height=max(height(t->left),height(t->right))+1;//计算结点的高度
if(height(t->left)-height(t->right)==2)
{//如果左儿子高度大于右儿子高度
if(height(t->left->left)>=height(t->left->right))//并且左儿子的左子树高度大于左儿子的右子树高度
{
clockwiseRotate(t);//顺时针旋转
}
else
{
doubleWithLeftChild(t);//双旋转左子树
}
}
else
{
if(height(t->right->right)-height(t->right->left)==2)//如果右子树大于左子树
{
antiClockWiseRotate(t);//逆时针旋转
}
else
{
doubleWithRright(t);//双旋转右子树
}
}
}
}
//删除某个对象，这里必须要引用
voidremove(constComparable&x,AvlNodePtr&t)const
{
if(!t)
{
return;//树为空
}
elseif(xelement)
{
remove(x,t->left);//比根结点小，去左边查找
}
elseif(x>t->element)
{
remove(x,t->right);//比根结点大，去右边查找
}
elseif(!t->left&&!t->right)//找到结点了，有两个叶子
{
removeMin(t,t->right);//这里选择的方法是删除右子树的最小的结点
}
else
{
AvlNodePtroldNode=t;
t=(t->left)?t->left:t->right;//走到这里，t最多只有一个叶子，将t指向这个叶子
deleteoldNode;//删除原来要删除的结点
}
if(t)
{
t->height=max(height(t->left),height(t->right))+1;//计算结点的高度
if(height(t->left)-height(t->right)==2)
{//如果左儿子高度大于右儿子高度
if(height(t->left->left)>=height(t->left->right))//并且左儿子的左子树高度大于左儿子的右子树高度
{
clockwiseRotate(t);//顺时针旋转
}
else
{
doubleWithLeftChild(t);//双旋转左子树
}
}
else
{
if(height(t->right->right)-height(t->right->left)==2)//如果右子树大于左子树
{
antiClockWiseRotate(t);//逆时针旋转
}
else
{
doubleWithRright(t);//双旋转右子树
}
}
}
}
//左边子树的结点肯定比当前根小的，所以一直往左边寻找
AvlNodePtrfindMin(AvlNodePtrt)const
{
if(!t)
{
returnnullptr;//找不到
}
if(!t->left)
{
returnt;
}
returnfindMin(t->left);//使用了递归的方式
}
//右边子树的结点肯定比当前根大，所以一直往右边找
AvlNodePtrfindMax(AvlNodePtrt)const
{
if(t)
{
while(t->right)//使用了循环的方式
{
t=t->right;
}
}
returnt;
}
//判断是否包含某个对象，因为要使用递归，所以还有一个public版本的
boolcontains(constComparable&x,AvlNodePtrt)const
{
if(!t)
{
returnfalse;//空结点了
}
elseif(xelement)
{
//根据二叉树的定义，比某个结点小的对象，肯定只能存在与这个结点的左边的子树
returncontains(x,t->left);
}
elseif(x>t->element)
{
//根据二叉树的定义，比某个结点大的对象，肯定只能存在与这个结点的右边的子树
returncontains(x,t->right);
}
else
{
//相等，就是找到啦。
returntrue;
}
}
//清空子树
voidmakeEmpty(AvlNodePtr&t)
{
if(t)
{
makeEmpty(t->left);//清空左边
makeEmpty(t->right);//清空右边
deletet;//释放自身
}
t=nullptr;//置为空
}
//打印子树，这里没有使用复杂的排位，纯属打印
voidprintTree(AvlNodePtrt)const
{
if(!t)
{
return;
}
std::cout<element<left);//打印左子树
printTree(t->right);//打印右子树
}
AvlNodePtrclone(AvlNodePtrt)const
{
if(!t)
{
returnnullptr;
}
returnnewAvlNode(t->element,clone(t->left),clone(t->right));
}
intheight(AvlNodePtrt)const
{
returnt==nullptr?-1:t->height;
}
};
}
#endif

简单测试一下。

//
//AvlTree.cpp
//HelloWorld
//Createdbyfeiyin001on17/1/9.
//Copyright(c)2017年FableGame.Allrightsreserved.
//
#include"AvlTree.h"
usingnamespaceFable;
intmain(intargc,char*argv[])
{
AvlTreea;
for(inti=0;i<100;++i)
{
a.insert(i);
}
return0;
}

这个删除的方法完全是自己写的，可能不是很高效。

希望本文所述对大家C语言程序设计有所帮助。

C语言数据结构之平衡二叉树（AVL树）实现方法示例

热门推荐

随机推荐