平衡二叉树操作演示.doc

平衡二叉树操作的演示

#include

#include typedef int KeyType;

//定义 //记录 //关 //平衡 //左右孩

关键字类型

typedef struct node

类型

{KeyType key;

键字项

int bf;

因子

struct node *lchild,*rchild;

子指针

}BSTNode;

void LeftProcess(BSTNode *&p,int &taller)

{// 对以指针 p 所指结点为根的二叉树作左平衡

旋转处理，本算法结束时，

//指针 p 指向新的根结点

BSTNode *p1,*p2;

if(p->bf==0)

// 原

本左右子树等高，现因左子树增高而使树增高 {p->bf=1;

taller=1;

}

else if(p->bf==-1)

//原本

右子树比左子树高，现左右子树等高 {p->bf=0;

taller=0;

}

else

//原 //p 指 //新

本左子树比右子树高，须作左子树的平衡处理 {p1=p->lchild;

向*p 的左子树根节点 if(p1->bf==1)

结点插入在 *p 的左孩子的左子树上， 要做 LL 调整

{p->lchild=p1->rchild;

p1->rchild=p;

p->bf=p1->bf=0;

p=p1;

}

else if(p1->bf==-1)

//新结 LR 调

点插入在 *p 的左孩子的右子树上，要做

整

{p2=p1->rchild;

p1->rchild=p2->lchild;

p2->lchild=p1;

p->lchild=p2->rchild;

p2->rchild=p;

if(p2->bf==0)

结点插入在 *p2 处作为叶子结点的情况

p->bf=p1->bf=0;

else if(p2->bf==1)

点插在 *p2 的左子树上的情况

{p1->bf=0;

p->bf=-1;

}

else

结点插在 *p2 的右子树上的情况

{p1->bf=1;

p->bf=0;

}

p=p2;

p->bf=0;

将 p 指向新的根结点，并置其 bf 值为 0}

//新

//新结

//新

//仍

taller=0;

}

}

void RightProcess(BSTNode *&p,int &taller)

{// 对以指针 p 所指结点为根的二叉树作右平衡

旋转处理，本算法结束时，

//指针 p 指向新的根结点

BSTNode *p1,*p2;

if(p->bf==0)

// 原

本左右子树等高，现因右子树增高而使树增高 {p->bf=-1;

taller=1;

}

else if(p->bf==1)

//原本

左子树比右子树高，现左右子树等高

{p->bf=0;

taller=0;

}

else

//原 //p 指

本右子树比左子树高，须作右子树的平衡处理

{p1=p->rchild;

向*p 的右子树根结点

if(p1->bf==-1)

点插入在 *p 的右孩子的左子树上，要做

整

{p->rchild=p1->lchild;

p->bf=p1->bf=0;

p=p1;

}

else if(p1->bf==1)

点插入在 *p 的右孩子的左子树上，要做

整

{p2=p1->lchild;

p1->lchild=p2->rchild;

p2->rchild=p1;

p->rchild=p2->lchild;

p2->lchild=p;

if(p2->bf==0)

结点插在 *p2 处作为叶子结点的情况

p->bf=p1->bf=0;

else if(p2->bf==-1)

*p2

点插在

的右子树上的情况 {p1->bf=0;

//新结

RR 调

//新结

RL 调

//新

//新结

p->bf=1;

}

else

//新

结点插在 *p2 的左子树上的情况

p->bf=0;

}

p=p2;

p->bf=0;

//仍

将 p 指向新的结点，并置其 bf 值为 0 }

taller=0;

}

}

int

InsertA VL(BSTNode*&b,KeyType

e,int

&taller)

{// 若在平衡二叉排序树 b 中不存在和 e 有相同关

键字的结点，则插入一个数据元素为 e 的新结点，

//并返回 1，否则返回 0。若因插入而使二叉排序树失去平衡，则作平衡旋转处理，布尔变量

taller

//反映 b 长高与否

if(b==NULL)

//

原树为空，插入新结点，树长高，置

taller 为 1

{b=(BSTNode*)malloc(sizeof(BSTNode)); b->key=e;

b->lchild=b->rchild=NULL;

b->bf=0;

taller=1;

}

else

{if(e==b->key)

//树

中已存在和 e 有相同关键字的结点则不插入 {taller=0; return 0; }

if(ekey)

续在 *b 的左子树中进行搜索 {if((InsertA VL(b->lchild,e,taller))==0) 未插入 return 0; if(taller==1)

入到 *b 的左子树中且左子树长高

// 继 //

//已插

LeftProcess(b,taller);

}

else

续在 *b 的右子树中进行搜索 {if((InsertA VL(b->rchild,e,taller))==0)

未插入

return 0;

if(taller==1)

入到 *b 的右子树中且右子树长高

RightProcess(b,taller);

}

}

return 1;

}

void DispBSTree(BSTNode *b)

{// 以括号表示法输出

AVL

if(b!=NULL)

{printf(\"%d\

if(b->lchild!=NULL||b->rchild!=NULL)

//继 //

//已插

{printf(\"(\");

DispBSTree(b->lchild);

if(b->rchild!=NULL)printf(\

DispBSTree(b->rchild);

printf(\")\");

}

}

}

void

LeftProcess1(BSTNode*&p,int&taller)

//在删除结点时进行左处理 {BSTNode *p1,*p2;

if(p->bf==1)

{p->bf=0;

taller=1;

}

else if(p->bf==0)

{p->bf=-1;

taller=0;

}

else

{p1=p->rchild;

if(p1->bf==0)

//须作 RR

调整

{p->rchild=p1->lchild;

p1->lchild=p;

p->bf=1; p=p1;

taller=0;

}

else if(p1->bf==-1)

须作 RR 调整

{p->rchild=p1->lchild;

p1->lchild=p;

p1->bf=p->bf=0;

p=p1;

taller=1;

}

else

//须作 RL

调整 {p2=p1->lchild;

p1->lchild=p2->rchild;

p2->rchild=p1;

p->rchild=p2->lchild;

//

p2->lchild=p;

if(p2->bf==0)

{p->bf=0;

p1->bf=0;

}

else if(p2->bf==-1)

{p1->bf=1;

p->bf=0;

}

else

{p1->bf=0;

p->bf=-1;

}

p2->bf=0;

p=p2;

taller=1;

}

}

}

void

RightProcess1(BSTNode*&p,int&taller)

//在删除结点是进行右处理 {BSTNode *p1,*p2;

if(p->bf==-1)

{p->bf=0;

taller=1;

} {p->bf=1;

taller=0;

}

else

{p1=p->lchild;

if(p1->bf==0)

//须作 LL 调整

{p->lchild=p1->rchild;

p1->rchild=p;

p->bf=-1;

p1->bf=1;

p=p1;

taller=0;

}

else if(p1->bf==1)

须作 LL

调整

{p->lchild=p1->rchild;

//

p1->rchild=p;

p1->bf=p->bf=0;

p=p1;

taller=1;

}

else

//须作 LR 调整

{p2=p1->rchild;

p1->rchild=p2->lchild;

p2->lchild=p1;

p->lchild=p2->rchild;

p2->rchild=p;

if(p2->bf==0)

{p->bf=0;

p1->bf=0;

}

else if(p2->bf==1)

{p1->bf=-1;

p->bf=0;

}

else

{p1->bf=0;

p->bf=1;

}

p2->bf=0;

p=p2;

taller=1;

}

}

}

void

Delete(BSTNode*q,BSTNode*&r,int

&taller)

{// 由 DeleteAVL 调用，用于处理被删结点左右子

树均不空的情况

if(r->rchild==NULL)

{q->key=r->key;

q=r;

r=r->lchild;

free(q);

taller=1;

}

else

{Delete(q,r->rchild,taller);

if(taller==1)

RightProcess1(r,taller);

}

}

int DeleteAVL(BSTNode *&p,KeyType

x,int

&taller)

{// 在 AVL 树中删除关键字为

x 的结点

int k;

BSTNode *q;

if(p==NULL)

return 0;

else if(xkey)

{k=DeleteA VL(p->lchild,x,taller); if(taller==1)

LeftProcess1(p,taller);

return k;

}

else if(x>p->key)

{k=DeleteA VL(p->rchild,x,taller); if(taller==1)

RightProcess1(p,taller);

return k;

}

else

找到了关键字为 x 的结点，由 p 指向它 {q=p;

if(p->rchild==NULL)

被删结点右子树为空

{p=p->lchild;

free(q);

taller=1;

}

else if(p->lchild==NULL)

删结点左子树为空

{p=p->rchild;

free(q);

taller=1;

}

else

删结点左右子树均不为空 {Delete(q,q->lchild,taller);

if(taller==1)

LeftProcess1(q,taller);

p=q;

//

//

//被

//被

}

return 1;

}

}

void main()

{BSTNode *b=NULL;

int i,j,k;

KeyType a[]={4,9,0,1,8,6,3,5,2,7},n=10;

printf(\" 创建一棵 AVL 树:\\n\");

for(i=0;i{printf(\"

第%d 步，插入 %d 元素 :\

InsertA VL(b,a[i],j);

DispBSTree(b);

printf(\"\\n\");

}

printf(\"A VL:\");

DispBSTree(b);

printf(\"\\n\");

printf(\" 删除结点 :\\n\");

k=8;

printf(\" 删除结点 %d:\

DeleteAVL(b,k,j);

printf(\"A VL:\");

DispBSTree(b);

printf(\"\\n\"); k=2;

printf(\" 删除结点 %d:\

DeleteAVL(b,k,j);

printf(\"A VL:\");

DispBSTree(b);

printf(\"\\n\\n\");

}