平衡二叉树操作的演示.doc

《平衡二叉树操作的演示.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#include#includetypedefintKeyType;//定义关键字类型typedefstructnode//记录类型{KeyTypekey;//关键字项intbf;//平衡因子structnode*lchild,*rchild;//左右孩子指针}BSTNode;voidLeftProcess(BSTNode*&p,int&taller){//对以指针p所指结点为根的二叉树作左平衡旋转处理，本算法结束时，//指针p指向新的根结点BSTNode*p1,*p2;if(p->bf==0)//原本左右子树等

2、高，现因左子树增高而使树增高{p->bf=1;taller=1;}elseif(p->bf==-1)//原本右子树比左子树高，现左右子树等高{p->bf=0;taller=0;}else//原本左子树比右子树高，须作左子树的平衡处理{p1=p->lchild;//p指向*p的左子树根节点if(p1->bf==1)//新结点插入在*p的左孩子的左子树上，要做LL调整{p->lchild=p1->rchild;p1->rchild=p;p->bf=p1->bf=0;p=p1;}elseif(p1->bf==-1)//新结点插入在*p的左孩子的右子树上，要

3、做LR调整{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;elseif(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

4、;}}voidRightProcess(BSTNode*&p,int&taller){//对以指针p所指结点为根的二叉树作右平衡旋转处理，本算法结束时，//指针p指向新的根结点BSTNode*p1,*p2;if(p->bf==0)//原本左右子树等高，现因右子树增高而使树增高{p->bf=-1;taller=1;}elseif(p->bf==1)//原本左子树比右子树高，现左右子树等高{p->bf=0;taller=0;}else//原本右子树比左子树高，须作右子树的平衡处理{p1=p->rchild;//p指向*p的右子树根结点if(p1->bf=

5、=-1)//新结点插入在*p的右孩子的左子树上，要做RR调整{p->rchild=p1->lchild;p1->lchild=p;p->bf=p1->bf=0;p=p1;}elseif(p1->bf==1)//新结点插入在*p的右孩子的左子树上，要做RL调整{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;elseif(p2->bf==-

6、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;}}intInsertAVL(BSTNode*&b,KeyTypee,int&taller){//若在平衡二叉排序树b中不存在和e有相同关键字的结点，则插入一个数据元素为e的新结点，//并返回1，否则返回0。若因插入而使二叉排序树失去平衡，则作平衡旋转处理，布尔变量taller//反映b长高与否if(b==

7、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;return0;}if(ekey)//继续在*b的左子树中进行搜索{if((InsertAVL(b->lchild,e,taller))==0)//未插入return0;if(taller==1)//已插入到

8、*b的左子树中且左子树长高LeftProcess(b,taller);}else//继续在*b的右子树中进行