打开APP
未登录
开通VIP,畅享免费电子书等14项超值服
开通VIP
首页
好书
留言交流
下载APP
联系客服
AVL树及其实现
昵称1740930
>《语言》
2012.03.30
关注
AVL树及其实现
引言
平衡二叉树由于logN的时间效率,在排序和查找中有重要应用。
实现
形态匀称的二叉树称为平衡二叉树 (Balanced binary tree) ,其严格定义是:
一棵空树是平衡二叉树;若 T 是一棵非空二叉树,其左、右子树为 TL 和 TR ,令 hl 和 hr 分别为左、右子树的深度。当且仅当
①TL 、 TR 都是平衡二叉树;
② | hl - hr |≤ 1;
时,则 T 是平衡二叉树。
以下是
它的c代码实现,具体思想参见<<数据结构>>(严蔚敏)一书。
#include
<
stdio.h
>
#include
<
malloc.h
>
#define
LH 1
//
左高
#define
EH 0
//
等高
#define
RH -1
//
右高
#define
TRUE 1
#define
FALSE 0
typedef
int
ElemType;
typedef
struct
BSTNode
{
ElemType key;
int
bf;
struct
BSTNode
*
lchild,
*
rchild;
}
BSTNode,
*
BSTree;
//
平衡树的定义
//
中序遍历
void
InOrderTraverse(BSTree root)
{
if
(root)
{
InOrderTraverse(root
->
lchild);
printf(
"
%d,
"
,root
->
key);
InOrderTraverse(root
->
rchild);
}
}
//
前序遍历
void
PreOrderTraverse(BSTree root)
{
if
(root)
{
printf(
"
%d,
"
,root
->
key);
PreOrderTraverse(root
->
lchild);
PreOrderTraverse(root
->
rchild);
}
}
//
右旋 如图1
void
R_Rotate(BSTree
&
p)
{
BSTree lc
=
p
->
lchild;
p
->
lchild
=
lc
->
rchild;
lc
->
rchild
=
p;
p
=
lc;
}
//
左旋
void
L_Rotate(BSTree
&
p)
{
BSTree rc
=
p
->
rchild;
p
->
rchild
=
rc
->
lchild;
rc
->
lchild
=
p;
p
=
rc;
}
//
左平衡处理
void
LeftBalance(BSTree
&
T)
{
BSTree lc
=
T
->
lchild;
switch
(lc
->
bf)
{
case
LH:
T
->
bf
=
lc
->
bf
=
EH;
R_Rotate(T);
break
;
case
RH:
BSTree rd
=
lc
->
rchild;
switch
(rd
->
bf)
{
case
LH:
//
如图2所示
T
->
bf
=
RH;
lc
->
bf
=
EH;
break
;
case
EH:
T
->
bf
=
lc
->
bf
=
EH;
break
;
case
RH:
T
->
bf
=
EH;
lc
->
bf
=
LH;
break
;
}
rd
->
bf
=
EH;
L_Rotate(T
->
lchild);
//
先左旋
R_Rotate(T);
//
右旋
break
;
}
}
//
右平衡处理
void
RightBalance(BSTree
&
T)
{
BSTree rc
=
T
->
rchild;
switch
(rc
->
bf)
{
case
RH:
T
->
bf
=
rc
->
bf
=
EH;
L_Rotate(T);
break
;
case
LH:
BSTree ld
=
rc
->
lchild;
switch
(ld
->
bf)
{
case
RH:
T
->
bf
=
LH;
rc
->
bf
=
EH;
break
;
case
EH:
T
->
bf
=
rc
->
bf
=
EH;
break
;
case
LH:
T
->
bf
=
EH;
rc
->
bf
=
RH;
break
;
}
ld
->
bf
=
EH;
R_Rotate(T
->
rchild);
L_Rotate(T);
break
;
}
}
//
在平衡二叉排序树中插入一个结点
int
InsertAVL(BSTree
&
t,ElemType e,
bool
&
taller)
{
if
(
!
t)
{
t
=
(BSTree)malloc(
sizeof
(BSTNode));
t
->
key
=
e;
t
->
lchild
=
t
->
rchild
=
NULL;
t
->
bf
=
EH;
taller
=
TRUE;
}
else
{
if
(e
==
t
->
key)
{
taller
=
FALSE;
return
0
;
}
if
(e
<
t
->
key)
{
if
(
!
InsertAVL(t
->
lchild,e,taller))
return
0
;
//
未插入
if
(taller)
{
switch
(t
->
bf)
{
case
LH:
LeftBalance(t);
taller
=
FALSE;
break
;
case
EH:
t
->
bf
=
LH;
taller
=
TRUE;
break
;
case
RH:
t
->
bf
=
EH;
taller
=
FALSE;
break
;
}
}
}
else
{
if
(
!
InsertAVL(t
->
rchild,e,taller))
return
0
;
//
未插入
if
(taller)
{
switch
(t
->
bf)
{
case
RH:
RightBalance(t);
taller
=
FALSE;
break
;
case
EH:
t
->
bf
=
RH;
taller
=
TRUE;
break
;
case
LH:
t
->
bf
=
EH;
taller
=
FALSE;
break
;
}
}
}
}
return
1
;
}
//
查找key,若没找到,则返回NULL
BSTree Search(BSTree t,ElemType key)
{
BSTree p
=
t;
while
(p)
{
if
(p
->
key
==
key)
return
p;
else
if
(p
->
key
<
key)
p
=
p
->
rchild;
else
p
=
p
->
lchild;
}
return
p;
}
/**/
int
main(
int
argc,
char
*
argv[])
{
BSTree root
=
NULL,r;
bool
taller
=
FALSE;
int
array[]
=
{
13
,
24
,
37
,
90
,
53
}
;
for
(
int
i
=
0
;i
<
5
;i
++
)
InsertAVL(root,array[i],taller);
printf(
"
inorder traverse
\n
"
);
InOrderTraverse(root);
printf(
"
\npreorder traverse
\n
"
);
PreOrderTraverse(root);
printf(
"
\nsearch key
\n
"
);
r
=
Search(root,
37
);
if
(r)
{
printf(
"
%d\n
"
,r
->
key);
}
else
{
printf(
"
not find!\n
"
);
}
}
图1.
图2
输出结果如下:
分类:
数据结构与算法
标签:
数据结构
,
算法
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报
。
打开APP,阅读全文并永久保存
查看更多类似文章
猜你喜欢
类似文章
【热】
打开小程序,算一算2024你的财运
求!!建立平衡二叉树的源程序
平衡二叉树的实现实例
【查找结构3】平衡二叉查找树 [AVL]
二叉排序树的实现
二叉排序/搜索/查找树
无聊时写过的一点代码,包括二叉树、二叉树模板、平衡二叉树模板,对某些人可能有用,呵呵
更多类似文章 >>
生活服务
热点新闻
留言交流
回顶部
联系我们
分享
收藏
点击这里,查看已保存的文章
导长图
关注
一键复制
下载文章
绑定账号成功
后续可登录账号畅享VIP特权!
如果VIP功能使用有故障,
可点击这里联系客服!
联系客服
微信登录中...
请勿关闭此页面
先别划走!
送你5元优惠券,购买VIP限时立减!
5
元
优惠券
优惠券还有
10:00
过期
马上使用
×