数据结构实验报告
题目：平衡二叉树
学 院 专 业 年级班别
学 号
学生姓名 指导教师
2015年7月1日
1.题目：采用字符类型为整型类型和链式存储结构，实现抽象数据类型BTree。 ADT BTree{
数据对象：D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0 }
数据关系：R1＝{ |ai-1, ai∈D, i=2,...,n }
基本操作：
Adj_balance(T)
操作结果：创建平衡二叉树。
InsertAVL(T,search,taller)
初始条件：二叉树T已存在。
操作结果：增加新结点。
SetAVL(T,search,taller)
初始条件：二叉树T已存在。
操作结果：在平衡二叉树上增加新结点并调平衡。
DeleteAVL(T,search,shorter)
初始条件：二叉树T已存在。
操作结果：删除结点。
} ADT BTree
2．存储结构定义
公用头文件DS0.h:
#include
#include
树的内部变量
typedef struct BTNode
{
int data;
int bf; //平衡因子
struct BTNode *lchild,*rchild;//左、右孩子
}BTNode,*BTree;
/*需要的函数声明*/
void Right_Balance(BTree &p);
void Left_Balance(BTree &p);
void Left_Root_Balance(BTree &T);
void Right_Root_Balance(BTree &T);
bool InsertAVL(BTree &T,int i,bool &taller);
void PrintBT(BTree T);
void Left_Root_Balance_det(BTree &p,int &shorter);
void Right_Root_Balance_det(BTree &p,int &shorter);
void Delete(BTree q,BTree &r,int &shorter);
int DeleteAVL(BTree &p,int x,int &shorter);
void Adj_balance(BTree &T);
bool SetAVL(BTree &T,int i,bool &taller);
bool Insert_Balance_AVL(BTree &T,int i,bool &taller);
int menu( );
3. 算法设计
/*对以*p为根的二叉排序树作右旋处理*/
void Right_Balance(BTree &p)
{
BTree lc;
lc =p->lchild; //lc指向的*p左子树根结点
p->lchild = lc->rchild; //rc的右子树挂接为*p的左子树
lc->rchild = p;
p = lc; //p指向新的结点
}
/*对以*p为根的二叉排序树作左旋处理*/
void Left_Balance(BTree &p)
{
BTree rc;
rc = p->rchild; //指向的*p右子树根结点
p->rchild = rc->lchild; //rc左子树挂接到*p的右子树
rc->lchild = p;
p = rc; //p指向新的结点
}
/*对以指针T所指结点为根的二叉树作左平衡旋转处理*/
void Left_Root_Balance(BTree &T)
{
BTree lc,rd;
lc = T->lchild; //指向*T的左子树根结点
switch(lc->bf) //检查*T的左子树的平衡度，并作相应平衡处理 {
case 1: //新结点插入在*T的左孩子的左子树上，要作单右旋处理
T->bf = lc->bf = 0;
Right_Balance(T);
break;
case -1: //新结点插入在*T的左孩子的右子树上，要作双旋处理
rd = lc->rchild; //rd指向*T的左孩子的右子树根
switch(rd->bf) //修改*T及其左孩子的平衡因子
{
case 1:
T->bf = -1;
lc->bf = 0;
break;
case 0:
T->bf = lc->bf = 0;
break;
case -1:
T->bf = 0;
lc->bf = 1;
break;
}
rd->bf = 0;
Left_Balance(T->lchild); //对*T的左子树作左旋平衡处理
Right_Balance(T); //对*T作右旋平衡处理
}
}
/*对以指针T所指结点为根的二叉树作右平衡旋转处理*/
void Right_Root_Balance(BTree &T)
{
BTree rc,ld;
rc = T->rchild; //指向*T的左子树根结点
switch(rc->bf) //检查*T的右子树的平衡度，并作相应平衡处理 {
case -1: //新结点插入在*T的右孩子的右子树上，要作单左旋处理
T->bf = rc->bf =0;
Left_Balance(T); break;
case 1: //新结点插入在*T的右孩子的左子树上，要作双旋处理
ld = rc->lchild; //ld指向*T的右孩子的左子树根
switch(ld->bf) //修改*T及其右孩子的平衡因子
{
case 1:
T->bf = 0;
rc->bf = -1;
break;
case 0:
T->bf = rc->bf =0;
break;
case -1:
T->bf = 1;
rc->bf = 0;
break;
}
ld->bf = 0;
Right_Balance(T->rchild);//对*T的右子树作左旋平衡处理
Left_Balance(T); //对*T作左旋平衡处理
}
}
/*插入结点i,若T中存在和i相同关键字的结点，则插入一个数据元素为i的新结点，并返回１，否则返回０*/
bool InsertAVL(BTree &T,int i,bool &taller)
{
if(!T)//插入新结点，树“长高”，置taller为true
{
T = (BTree)malloc(sizeof(BTNode));
T->data = i;
T->lchild = T->rchild =NULL;
T->bf = 0;
taller = true;
}
else
{
if(i==T->data) //树中已存在和有相同关键字的结点 {
taller = 0;
printf("已存在相同关键字的结点\n");
return 0;
}
if(idata) //应继续在*T的左子树中进行搜索 {
if(!InsertAVL(T->lchild,i,taller))
return 0;
}
else //应继续在*T的右子树中进行搜索
{
if(!InsertAVL(T->rchild,i,taller))
return 0;
}
}
return 1;
}
/*输出二叉树*/
void PrintBT(BTree T)
{
if(T)
{
printf("%d",T->data);
if(T->lchild||T->rchild)
{
printf("(");
PrintBT(T->lchild);
printf(",");
PrintBT(T->rchild);
printf(")");
}
}
}
/*删除结点时左平衡旋转处理*/
void Left_Root_Balance_det(BTree &p,int &shorter)
{
BTree p1,p2;
if(p->bf==1) //p结点的左子树高，删除结点后p的bf减,树变矮
{
p->bf=0;
shorter=1;
}
else if(p->bf==0)//p结点左、右子树等高，删除结点后p的bf减,树高不变 {
p->bf=-1;
shorter=0;
}
else //p结点的右子树高
{
p1=p->rchild;//p1指向p的右子树
if(p1->bf==0)//p1结点左、右子树等高,删除结点后p的bf为-2,进行左旋处理，树高不变
{
Left_Balance(p);
p1->bf=1;
p->bf=-1;
shorter=0;
}
else if(p1->bf==-1)//p1的右子树高，左旋处理后，树变矮
{
Left_Balance(p);
p1->bf=p->bf=0;
shorter=1;
}
else //p1的左子树高,进行双旋处理(先右旋后左旋)，树变矮 {
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)
{
p->bf=1;
p1->bf=0;
}
else
{
p->bf=0;
p1->bf=-1;
}
p2->bf=0;
p=p2;
shorter=1;
}
}
}
/*删除结点时右平衡旋转处理*/
void Right_Root_Balance_det(BTree &p,int &shorter)
{
BTree p1,p2;
if(p->bf==-1)
{
p->bf=0;
shorter=1;
}
else if(p->bf==0)
{
p->bf=1;
shorter=0;
}
else
{
p1=p->lchild;
if(p1->bf==0)
{
Right_Balance(p);
p1->bf=-1;
p->bf=1;
shorter=0;
}
else if(p1->bf==1)
Right_Balance(p);
p1->bf=p->bf=0;
shorter=1;
}
else
{
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)
{
p->bf=-1;
p1->bf=0;
}
else
{
p->bf=0;
p1->bf=1;
}
p2->bf=0;
p=p2;
shorter=1;
}
}
}
/*删除结点*/
void Delete(BTree q,BTree &r,int &shorter)
{
if(r->rchild==NULL)
{
q->data=r->data;
q=r;
r=r->lchild;
free(q);
shorter=1;
}
{
Delete(q,r->rchild,shorter);
if(shorter==1)
Right_Root_Balance_det(r,shorter);
}
}
/*二叉树的删除操作*/
int DeleteAVL(BTree &p,int x,int &shorter)
{
int k;
BTree q;
if(p==NULL)
{
printf("不存在要删除的关键字!!\n");
return 0;
}
else if(x
data)//在p的左子树中进行删除
{
k=DeleteAVL(p->lchild,x,shorter);
if(shorter==1)
Left_Root_Balance_det(p,shorter);
return k;
}
else if(x>p->data)//在p的右子树中进行删除
{
k=DeleteAVL(p->rchild,x,shorter);
if(shorter==1)
Right_Root_Balance_det(p,shorter);
return k;
}
else
{
q=p;
if(p->rchild==NULL) //右子树空则只需重接它的左子树
{
p=p->lchild;
free(q);
shorter=1;
}
else if(p->lchild==NULL)//左子树空则只需重接它的右子树
{
p=p->rchild;
free(q);
shorter=1;
}
else//左右子树均不空
{
Delete(q,q->lchild,shorter);
if(shorter==1)
Left_Root_Balance_det(p,shorter);
p=q;
}
return 1;
}
}
/*调平二叉树具体方法*/
bool SetAVL(BTree &T,int i,bool &taller)
{
if(!T)//插入新结点，树“长高”，置taller为true
{
T = (BTree)malloc(sizeof(BTNode));
T->data = i;
T->lchild = T->rchild =NULL;
T->bf = 0;
taller = true;
}
else
{
if(i==T->data) //树中已存在和有相同关键字的结点 {
taller = false;
printf("已存在相同关键字的结点\n");
return 0;
}
if(idata) //应继续在*T的左子树中进行搜索 {
if(!SetAVL(T->lchild,i,taller))
return 0;
if(taller) //已插入到*T的左子树中且左子树“长高”
switch(T->bf) //检查*T的平衡度
{
case 1: //原本左子树比右子树高，需要作左平衡处理
Left_Root_Balance(T);
taller = false;
break;
case 0: //原本左子树、右子等高，现因左子树增高而使树增高
T->bf = 1;
taller = true;
break;
case -1: //原本右子树比左子树高，现左、右子树等高
T->bf = 0;
taller = false;
break;
}
}
else //应继续在*T的右子树中进行搜索
{
if(!SetAVL(T->rchild,i,taller))
return 0;
if(taller) //已插入到*T的右子树中且右子树“长高”
switch(T->bf) //检查*T的平衡度
{
case 1: //原本左子树比右子树高，现左、右子树等高
T->bf = 0;
taller = false;
break;
case 0: //原本左子树、右子等高，现因右子树增高而使树增高
T->bf = -1;
taller = true;
break;
case -1: //原本右子树比左子树高，需要作右平衡处理
Right_Root_Balance(T);
taller = false;
break;
}
}
return 1;
}
}
/*二叉树调平操作*/
void Adj_balance(BTree &T)
{
int i;
bool taller=false;
T = NULL;
printf("\n请输入关键字(以-1结束建立平衡二叉树):");
scanf("%d",&i);
getchar();
while(i != -1)
{
SetAVL(T,i,taller);
printf("\n请输入关键字(以-1结束建立平衡二叉树):");
scanf("%d",&i);
getchar();
taller=false;
}
printf("平衡二叉树创建结束.\n");
if(T)
PrintBT(T);
else
printf("这是一棵空树.\n");
}
/*菜单函数*/
int menu( )
{
int m;
printf("..........................2015年7月1日......................\n\n");
printf(" 平衡二叉树\n");
printf(" ________________________________\n\n"); printf(" 1 创建平衡二叉树\n");
printf(" 2 在平衡二叉树上增加新结点并调衡\n"); printf(" 3 在平衡二叉树上删除一个结点并调衡\n"); printf(" 0 退出\n");
printf(" ________________________________\n\n"); printf(" 请输入所选功能0-3\n");
scanf("%d",&m);
return m;
}
4．测试
/*主函数*/
void main()
{
int input,search;
bool taller=0;
int shorter=0;
BTree T;
T=(BTree)malloc(sizeof(BTNode));
T=NULL;
while(1)
{
printf("\n请选择需要的二叉树操作\n");
input=menu( );
switch(input)
{
case 1:
Adj_balance(T);
break;
case 2:
printf("请输入你要增加的关键字");
scanf("%d",&search);
getchar();
SetAVL(T,search,taller);
PrintBT(T);
break;
case 3:
printf("请输入你要删除的关键字");
scanf("%d",&search);
getchar();
DeleteAVL(T,search,shorter);
PrintBT(T);
break;
case 0:
break;
default:
printf("输入错误，请重新选择。");
break;
}
if(input == 0)
break;
printf("按任意键继续.");
getchar();
}
}
测试截图:
1.界面：
2.创建平衡二叉树：
3.增加节点并调衡：
4.删除节点并调衡：
5. 思考与小结
在平衡二叉树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。
#include
#include
typedef struct BTNode
{
int data;
int bf; //平衡因子
struct BTNode *lchild,*rchild;//左、右孩子
}BTNode,*BTree;
/*对以*p为根的二叉排序树作右旋处理*/
void Right_Balance(BTree &p)
{
BTree lc;
lc =p->lchild; //lc指向的*p左子树根结点
p->lchild = lc->rchild; //rc的右子树挂接为*p的左子树
lc->rchild = p;
p = lc; //p指向新的结点
}
/*对以*p为根的二叉排序树作左旋处理*/
void Left_Balance(BTree &p)
{
BTree rc;
rc = p->rchild; //指向的*p右子树根结点
p->rchild = rc->lchild; //rc左子树挂接到*p的右子树
rc->lchild = p;
p = rc; //p指向新的结点
}
/*对以指针T所指结点为根的二叉树作左平衡旋转处理*/
void Left_Root_Balance(BTree &T)
{
BTree lc,rd;
lc = T->lchild; //指向*T的左子树根结点
switch(lc->bf) //检查*T的左子树的平衡度，并作相应平衡处理 {
case 1: //新结点插入在*T的左孩子的左子树上，要作单右旋处理
T->bf = lc->bf = 0;
Right_Balance(T);
break;
case -1: //新结点插入在*T的左孩子的右子树上，要作双旋处理
rd = lc->rchild; //rd指向*T的左孩子的右子树根
switch(rd->bf) //修改*T及其左孩子的平衡因子
case 1:
T->bf = -1;
lc->bf = 0;
break;
case 0:
T->bf = lc->bf = 0;
break;
case -1:
T->bf = 0;
lc->bf = 1;
break;
}
rd->bf = 0;
Left_Balance(T->lchild); //对*T的左子树作左旋平衡处理
Right_Balance(T); //对*T作右旋平衡处理
}
}
/*对以指针T所指结点为根的二叉树作右平衡旋转处理*/
void Right_Root_Balance(BTree &T)
{
BTree rc,ld;
rc = T->rchild; //指向*T的左子树根结点
switch(rc->bf) //检查*T的右子树的平衡度，并作相应平衡处理 {
case -1: //新结点插入在*T的右孩子的右子树上，要作单左旋处理
T->bf = rc->bf =0;
Left_Balance(T); break;
case 1: //新结点插入在*T的右孩子的左子树上，要作双旋处理
ld = rc->lchild; //ld指向*T的右孩子的左子树根
switch(ld->bf) //修改*T及其右孩子的平衡因子
{
case 1:
T->bf = 0;
rc->bf = -1;
break;
case 0:
T->bf = rc->bf =0;
break;
case -1:
T->bf = 1;
rc->bf = 0;
break;
}
ld->bf = 0;
Right_Balance(T->rchild);//对*T的右子树作左旋平衡处理
Left_Balance(T); //对*T作左旋平衡处理
}
}
/*插入结点i,若T中存在和i相同关键字的结点，则插入一个数据元素为i的新结点，并返回１，否则返回０*/
bool InsertAVL(BTree &T,int i,bool &taller)
{
if(!T)//插入新结点，树“长高”，置taller为true
{
T = (BTree)malloc(sizeof(BTNode));
T->data = i;
T->lchild = T->rchild =NULL;
T->bf = 0;
taller = 1;
}
else
{
if(i==T->data) //树中已存在和有相同关键字的结点 {
taller = 0;
printf("已存在相同关键字的结点\n");
return 0;
}
if(idata) //应继续在*T的左子树中进行搜索 {
if(!InsertAVL(T->lchild,i,taller))
return 0;
}
else //应继续在*T的右子树中进行搜索
{
if(!InsertAVL(T->rchild,i,taller))
return 0;
}
}
return 1;
}
/*输出平衡二叉树*/
void PrintBT(BTree T)
{
{
printf("%d",T->data);
if(T->lchild||T->rchild)
{
printf("(");
PrintBT(T->lchild);
printf(",");
PrintBT(T->rchild);
printf(")");
}
}
}
/*删除结点时左平衡旋转处理*/
void Left_Root_Balance_det(BTree &p,int &shorter)
{
BTree p1,p2;
if(p->bf==1) //p结点的左子树高，删除结点后p的bf减,树变矮
{
p->bf=0;
shorter=1;
}
else if(p->bf==0)//p结点左、右子树等高，删除结点后p的bf减,树高不变 {
p->bf=-1;
shorter=0;
}
else //p结点的右子树高
{
p1=p->rchild;//p1指向p的右子树
if(p1->bf==0)//p1结点左、右子树等高,删除结点后p的bf为-2,进行左旋处理，树高不变
{
Left_Balance(p);
p1->bf=1;
p->bf=-1;
shorter=0;
}
else if(p1->bf==-1)//p1的右子树高，左旋处理后，树变矮
{
Left_Balance(p);
p1->bf=p->bf=0;
shorter=1;
else //p1的左子树高,进行双旋处理(先右旋后左旋)，树变矮 {
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)
{
p->bf=1;
p1->bf=0;
}
else
{
p->bf=0;
p1->bf=-1;
}
p2->bf=0;
p=p2;
shorter=1;
}
}
}
/*删除结点时右平衡旋转处理*/
void Right_Root_Balance_det(BTree &p,int &shorter)
{
BTree p1,p2;
if(p->bf==-1)
{
p->bf=0;
shorter=1;
}
else if(p->bf==0)
{
p->bf=1;
shorter=0;
}
else
{
p1=p->lchild;
if(p1->bf==0)
{
Right_Balance(p);
p1->bf=-1;
p->bf=1;
shorter=0;
}
else if(p1->bf==1)
{
Right_Balance(p);
p1->bf=p->bf=0;
shorter=1;
}
else
{
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)
{
p->bf=-1;
p1->bf=0;
}
else
{
p->bf=0;
p1->bf=1;
}
p2->bf=0;
p=p2;
shorter=1;
}
}
}
/*删除结点*/
void Delete(BTree q,BTree &r,int &shorter)
{
if(r->rchild==NULL)
{
q->data=r->data;
q=r;
r=r->lchild;
free(q);
shorter=1;
}
else
{
Delete(q,r->rchild,shorter);
if(shorter==1)
Right_Root_Balance_det(r,shorter);
}
}
/*二叉树的删除操作*/
int DeleteAVL(BTree &p,int x,int &shorter)
{
int k;
BTree q;
if(p==NULL)
{
printf("不存在要删除的关键字!!\n");
return 0;
}
else if(x
data)//在p的左子树中进行删除
{
k=DeleteAVL(p->lchild,x,shorter);
if(shorter==1)
Left_Root_Balance_det(p,shorter);
return k;
}
else if(x>p->data)//在p的右子树中进行删除
{
k=DeleteAVL(p->rchild,x,shorter);
if(shorter==1)
Right_Root_Balance_det(p,shorter);
return k;
}
else
{
q=p;
if(p->rchild==NULL) //右子树空则只需重接它的左子树
{
p=p->lchild;
free(q);
shorter=1;
}
else if(p->lchild==NULL)//左子树空则只需重接它的右子树
{
p=p->rchild;
free(q);
shorter=1;
}
else//左右子树均不空
{
Delete(q,q->lchild,shorter);
if(shorter==1)
Left_Root_Balance_det(p,shorter);
p=q;
}
return 1;
}
}
/*调平二叉树具体方法*/
bool SetAVL(BTree &T,int i,bool &taller)
{
if(!T)//插入新结点，树“长高”，置taller为true
{
T = (BTree)malloc(sizeof(BTNode));
T->data = i;
T->lchild = T->rchild =NULL;
T->bf = 0;
taller = 1;
}
else
{
if(i==T->data) //树中已存在和有相同关键字的结点 {
taller = false;
printf("已存在相同关键字的结点\n");
return 0;
}
if(idata) //应继续在*T的左子树中进行搜索 {
if(!SetAVL(T->lchild,i,taller))
return 0;
if(taller) //已插入到*T的左子树中且左子树“长高”
switch(T->bf) //检查*T的平衡度
{
case 1: //原本左子树比右子树高，需要作左平衡处理
Left_Root_Balance(T);
taller = false;
break;
case 0: //原本左子树、右子等高，现因左子树增高而使树增高
T->bf = 1;
taller = 1;
break;
case -1: //原本右子树比左子树高，现左、右子树等高
T->bf = 0;
taller = false;
break;
}
}
else //应继续在*T的右子树中进行搜索
{
if(!SetAVL(T->rchild,i,taller))
return 0;
if(taller) //已插入到*T的右子树中且右子树“长高”
switch(T->bf) //检查*T的平衡度
{
case 1: //原本左子树比右子树高，现左、右子树等高
T->bf = 0;
taller = false;
break;
case 0: //原本左子树、右子等高，现因右子树增高而使树增高
T->bf = -1;
taller = 1;
break;
case -1: //原本右子树比左子树高，需要作右平衡处理
Right_Root_Balance(T);
taller = 0;
break;
}
}
return 1;
}
}
/*二叉树调平操作*/
void Adj_balance(BTree &T)
{
int i;
bool taller=0;
T = NULL;
printf("\n请输入关键字(以-1结束建立平衡二叉树):");
scanf("%d",&i);
getchar();
while(i != -1)
{
SetAVL(T,i,taller);
printf("\n请输入关键字(以-1结束建立平衡二叉树):");
scanf("%d",&i);
getchar();
taller=0;
}
printf("平衡二叉树创建结束.\n");
if(T)
PrintBT(T);
else
printf("这是一棵空树.\n");
}
/*菜单函数*/
int menu( )
{
int m;
printf("..........................2015年7月1日......................\n\n");
printf(" 平衡二叉树\n");
printf(" ________________________________\n\n"); printf(" 1 创建平衡二叉树\n");
printf(" 2 在平衡二叉树上增加新结点并调平衡\n"); printf(" 3 删除一个结点\n");
printf(" 0 退出\n");
printf(" ________________________________\n\n"); printf(" 请输入所选功能0-3\n");
scanf("%d",&m);
return m;
}
/*主函数*/
void main()
{
int input,search;
bool taller=0;
int shorter=0;
BTree T;
T=(BTree)malloc(sizeof(BTNode));
T=NULL;
while(1)
{
printf("\n请选择需要的二叉树操作\n"); input=menu( );
switch(input)
{
case 1:
Adj_balance(T);
break;
case 2:
printf("请输入你要增加的关键字"); scanf("%d",&search);
getchar();
SetAVL(T,search,taller); PrintBT(T);
break;
case 3:
printf("请输入你要删除的关键字"); scanf("%d",&search);
getchar();
DeleteAVL(T,search,shorter); PrintBT(T);
break;
case 0:
break;
default:
printf("输入错误，请重新选择。"); break;
}
if(input == 0)
break;
printf("按任意键继续."); getchar();
}
}
数据结构实验报告
题目：平衡二叉树
学 院 专 业 年级班别
学 号
学生姓名 指导教师
2015年7月1日
1.题目：采用字符类型为整型类型和链式存储结构，实现抽象数据类型BTree。 ADT BTree{
数据对象：D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0 }
数据关系：R1＝{ |ai-1, ai∈D, i=2,...,n }
基本操作：
Adj_balance(T)
操作结果：创建平衡二叉树。
InsertAVL(T,search,taller)
初始条件：二叉树T已存在。
操作结果：增加新结点。
SetAVL(T,search,taller)
初始条件：二叉树T已存在。
操作结果：在平衡二叉树上增加新结点并调平衡。
DeleteAVL(T,search,shorter)
初始条件：二叉树T已存在。
操作结果：删除结点。
} ADT BTree
2．存储结构定义
公用头文件DS0.h:
#include
#include
树的内部变量
typedef struct BTNode
{
int data;
int bf; //平衡因子
struct BTNode *lchild,*rchild;//左、右孩子
}BTNode,*BTree;
/*需要的函数声明*/
void Right_Balance(BTree &p);
void Left_Balance(BTree &p);
void Left_Root_Balance(BTree &T);
void Right_Root_Balance(BTree &T);
bool InsertAVL(BTree &T,int i,bool &taller);
void PrintBT(BTree T);
void Left_Root_Balance_det(BTree &p,int &shorter);
void Right_Root_Balance_det(BTree &p,int &shorter);
void Delete(BTree q,BTree &r,int &shorter);
int DeleteAVL(BTree &p,int x,int &shorter);
void Adj_balance(BTree &T);
bool SetAVL(BTree &T,int i,bool &taller);
bool Insert_Balance_AVL(BTree &T,int i,bool &taller);
int menu( );
3. 算法设计
/*对以*p为根的二叉排序树作右旋处理*/
void Right_Balance(BTree &p)
{
BTree lc;
lc =p->lchild; //lc指向的*p左子树根结点
p->lchild = lc->rchild; //rc的右子树挂接为*p的左子树
lc->rchild = p;
p = lc; //p指向新的结点
}
/*对以*p为根的二叉排序树作左旋处理*/
void Left_Balance(BTree &p)
{
BTree rc;
rc = p->rchild; //指向的*p右子树根结点
p->rchild = rc->lchild; //rc左子树挂接到*p的右子树
rc->lchild = p;
p = rc; //p指向新的结点
}
/*对以指针T所指结点为根的二叉树作左平衡旋转处理*/
void Left_Root_Balance(BTree &T)
{
BTree lc,rd;
lc = T->lchild; //指向*T的左子树根结点
switch(lc->bf) //检查*T的左子树的平衡度，并作相应平衡处理 {
case 1: //新结点插入在*T的左孩子的左子树上，要作单右旋处理
T->bf = lc->bf = 0;
Right_Balance(T);
break;
case -1: //新结点插入在*T的左孩子的右子树上，要作双旋处理
rd = lc->rchild; //rd指向*T的左孩子的右子树根
switch(rd->bf) //修改*T及其左孩子的平衡因子
{
case 1:
T->bf = -1;
lc->bf = 0;
break;
case 0:
T->bf = lc->bf = 0;
break;
case -1:
T->bf = 0;
lc->bf = 1;
break;
}
rd->bf = 0;
Left_Balance(T->lchild); //对*T的左子树作左旋平衡处理
Right_Balance(T); //对*T作右旋平衡处理
}
}
/*对以指针T所指结点为根的二叉树作右平衡旋转处理*/
void Right_Root_Balance(BTree &T)
{
BTree rc,ld;
rc = T->rchild; //指向*T的左子树根结点
switch(rc->bf) //检查*T的右子树的平衡度，并作相应平衡处理 {
case -1: //新结点插入在*T的右孩子的右子树上，要作单左旋处理
T->bf = rc->bf =0;
Left_Balance(T); break;
case 1: //新结点插入在*T的右孩子的左子树上，要作双旋处理
ld = rc->lchild; //ld指向*T的右孩子的左子树根
switch(ld->bf) //修改*T及其右孩子的平衡因子
{
case 1:
T->bf = 0;
rc->bf = -1;
break;
case 0:
T->bf = rc->bf =0;
break;
case -1:
T->bf = 1;
rc->bf = 0;
break;
}
ld->bf = 0;
Right_Balance(T->rchild);//对*T的右子树作左旋平衡处理
Left_Balance(T); //对*T作左旋平衡处理
}
}
/*插入结点i,若T中存在和i相同关键字的结点，则插入一个数据元素为i的新结点，并返回１，否则返回０*/
bool InsertAVL(BTree &T,int i,bool &taller)
{
if(!T)//插入新结点，树“长高”，置taller为true
{
T = (BTree)malloc(sizeof(BTNode));
T->data = i;
T->lchild = T->rchild =NULL;
T->bf = 0;
taller = true;
}
else
{
if(i==T->data) //树中已存在和有相同关键字的结点 {
taller = 0;
printf("已存在相同关键字的结点\n");
return 0;
}
if(idata) //应继续在*T的左子树中进行搜索 {
if(!InsertAVL(T->lchild,i,taller))
return 0;
}
else //应继续在*T的右子树中进行搜索
{
if(!InsertAVL(T->rchild,i,taller))
return 0;
}
}
return 1;
}
/*输出二叉树*/
void PrintBT(BTree T)
{
if(T)
{
printf("%d",T->data);
if(T->lchild||T->rchild)
{
printf("(");
PrintBT(T->lchild);
printf(",");
PrintBT(T->rchild);
printf(")");
}
}
}
/*删除结点时左平衡旋转处理*/
void Left_Root_Balance_det(BTree &p,int &shorter)
{
BTree p1,p2;
if(p->bf==1) //p结点的左子树高，删除结点后p的bf减,树变矮
{
p->bf=0;
shorter=1;
}
else if(p->bf==0)//p结点左、右子树等高，删除结点后p的bf减,树高不变 {
p->bf=-1;
shorter=0;
}
else //p结点的右子树高
{
p1=p->rchild;//p1指向p的右子树
if(p1->bf==0)//p1结点左、右子树等高,删除结点后p的bf为-2,进行左旋处理，树高不变
{
Left_Balance(p);
p1->bf=1;
p->bf=-1;
shorter=0;
}
else if(p1->bf==-1)//p1的右子树高，左旋处理后，树变矮
{
Left_Balance(p);
p1->bf=p->bf=0;
shorter=1;
}
else //p1的左子树高,进行双旋处理(先右旋后左旋)，树变矮 {
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)
{
p->bf=1;
p1->bf=0;
}
else
{
p->bf=0;
p1->bf=-1;
}
p2->bf=0;
p=p2;
shorter=1;
}
}
}
/*删除结点时右平衡旋转处理*/
void Right_Root_Balance_det(BTree &p,int &shorter)
{
BTree p1,p2;
if(p->bf==-1)
{
p->bf=0;
shorter=1;
}
else if(p->bf==0)
{
p->bf=1;
shorter=0;
}
else
{
p1=p->lchild;
if(p1->bf==0)
{
Right_Balance(p);
p1->bf=-1;
p->bf=1;
shorter=0;
}
else if(p1->bf==1)
Right_Balance(p);
p1->bf=p->bf=0;
shorter=1;
}
else
{
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)
{
p->bf=-1;
p1->bf=0;
}
else
{
p->bf=0;
p1->bf=1;
}
p2->bf=0;
p=p2;
shorter=1;
}
}
}
/*删除结点*/
void Delete(BTree q,BTree &r,int &shorter)
{
if(r->rchild==NULL)
{
q->data=r->data;
q=r;
r=r->lchild;
free(q);
shorter=1;
}
{
Delete(q,r->rchild,shorter);
if(shorter==1)
Right_Root_Balance_det(r,shorter);
}
}
/*二叉树的删除操作*/
int DeleteAVL(BTree &p,int x,int &shorter)
{
int k;
BTree q;
if(p==NULL)
{
printf("不存在要删除的关键字!!\n");
return 0;
}
else if(x
data)//在p的左子树中进行删除
{
k=DeleteAVL(p->lchild,x,shorter);
if(shorter==1)
Left_Root_Balance_det(p,shorter);
return k;
}
else if(x>p->data)//在p的右子树中进行删除
{
k=DeleteAVL(p->rchild,x,shorter);
if(shorter==1)
Right_Root_Balance_det(p,shorter);
return k;
}
else
{
q=p;
if(p->rchild==NULL) //右子树空则只需重接它的左子树
{
p=p->lchild;
free(q);
shorter=1;
}
else if(p->lchild==NULL)//左子树空则只需重接它的右子树
{
p=p->rchild;
free(q);
shorter=1;
}
else//左右子树均不空
{
Delete(q,q->lchild,shorter);
if(shorter==1)
Left_Root_Balance_det(p,shorter);
p=q;
}
return 1;
}
}
/*调平二叉树具体方法*/
bool SetAVL(BTree &T,int i,bool &taller)
{
if(!T)//插入新结点，树“长高”，置taller为true
{
T = (BTree)malloc(sizeof(BTNode));
T->data = i;
T->lchild = T->rchild =NULL;
T->bf = 0;
taller = true;
}
else
{
if(i==T->data) //树中已存在和有相同关键字的结点 {
taller = false;
printf("已存在相同关键字的结点\n");
return 0;
}
if(idata) //应继续在*T的左子树中进行搜索 {
if(!SetAVL(T->lchild,i,taller))
return 0;
if(taller) //已插入到*T的左子树中且左子树“长高”
switch(T->bf) //检查*T的平衡度
{
case 1: //原本左子树比右子树高，需要作左平衡处理
Left_Root_Balance(T);
taller = false;
break;
case 0: //原本左子树、右子等高，现因左子树增高而使树增高
T->bf = 1;
taller = true;
break;
case -1: //原本右子树比左子树高，现左、右子树等高
T->bf = 0;
taller = false;
break;
}
}
else //应继续在*T的右子树中进行搜索
{
if(!SetAVL(T->rchild,i,taller))
return 0;
if(taller) //已插入到*T的右子树中且右子树“长高”
switch(T->bf) //检查*T的平衡度
{
case 1: //原本左子树比右子树高，现左、右子树等高
T->bf = 0;
taller = false;
break;
case 0: //原本左子树、右子等高，现因右子树增高而使树增高
T->bf = -1;
taller = true;
break;
case -1: //原本右子树比左子树高，需要作右平衡处理
Right_Root_Balance(T);
taller = false;
break;
}
}
return 1;
}
}
/*二叉树调平操作*/
void Adj_balance(BTree &T)
{
int i;
bool taller=false;
T = NULL;
printf("\n请输入关键字(以-1结束建立平衡二叉树):");
scanf("%d",&i);
getchar();
while(i != -1)
{
SetAVL(T,i,taller);
printf("\n请输入关键字(以-1结束建立平衡二叉树):");
scanf("%d",&i);
getchar();
taller=false;
}
printf("平衡二叉树创建结束.\n");
if(T)
PrintBT(T);
else
printf("这是一棵空树.\n");
}
/*菜单函数*/
int menu( )
{
int m;
printf("..........................2015年7月1日......................\n\n");
printf(" 平衡二叉树\n");
printf(" ________________________________\n\n"); printf(" 1 创建平衡二叉树\n");
printf(" 2 在平衡二叉树上增加新结点并调衡\n"); printf(" 3 在平衡二叉树上删除一个结点并调衡\n"); printf(" 0 退出\n");
printf(" ________________________________\n\n"); printf(" 请输入所选功能0-3\n");
scanf("%d",&m);
return m;
}
4．测试
/*主函数*/
void main()
{
int input,search;
bool taller=0;
int shorter=0;
BTree T;
T=(BTree)malloc(sizeof(BTNode));
T=NULL;
while(1)
{
printf("\n请选择需要的二叉树操作\n");
input=menu( );
switch(input)
{
case 1:
Adj_balance(T);
break;
case 2:
printf("请输入你要增加的关键字");
scanf("%d",&search);
getchar();
SetAVL(T,search,taller);
PrintBT(T);
break;
case 3:
printf("请输入你要删除的关键字");
scanf("%d",&search);
getchar();
DeleteAVL(T,search,shorter);
PrintBT(T);
break;
case 0:
break;
default:
printf("输入错误，请重新选择。");
break;
}
if(input == 0)
break;
printf("按任意键继续.");
getchar();
}
}
测试截图:
1.界面：
2.创建平衡二叉树：
3.增加节点并调衡：
4.删除节点并调衡：
5. 思考与小结
在平衡二叉树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。
#include
#include
typedef struct BTNode
{
int data;
int bf; //平衡因子
struct BTNode *lchild,*rchild;//左、右孩子
}BTNode,*BTree;
/*对以*p为根的二叉排序树作右旋处理*/
void Right_Balance(BTree &p)
{
BTree lc;
lc =p->lchild; //lc指向的*p左子树根结点
p->lchild = lc->rchild; //rc的右子树挂接为*p的左子树
lc->rchild = p;
p = lc; //p指向新的结点
}
/*对以*p为根的二叉排序树作左旋处理*/
void Left_Balance(BTree &p)
{
BTree rc;
rc = p->rchild; //指向的*p右子树根结点
p->rchild = rc->lchild; //rc左子树挂接到*p的右子树
rc->lchild = p;
p = rc; //p指向新的结点
}
/*对以指针T所指结点为根的二叉树作左平衡旋转处理*/
void Left_Root_Balance(BTree &T)
{
BTree lc,rd;
lc = T->lchild; //指向*T的左子树根结点
switch(lc->bf) //检查*T的左子树的平衡度，并作相应平衡处理 {
case 1: //新结点插入在*T的左孩子的左子树上，要作单右旋处理
T->bf = lc->bf = 0;
Right_Balance(T);
break;
case -1: //新结点插入在*T的左孩子的右子树上，要作双旋处理
rd = lc->rchild; //rd指向*T的左孩子的右子树根
switch(rd->bf) //修改*T及其左孩子的平衡因子
case 1:
T->bf = -1;
lc->bf = 0;
break;
case 0:
T->bf = lc->bf = 0;
break;
case -1:
T->bf = 0;
lc->bf = 1;
break;
}
rd->bf = 0;
Left_Balance(T->lchild); //对*T的左子树作左旋平衡处理
Right_Balance(T); //对*T作右旋平衡处理
}
}
/*对以指针T所指结点为根的二叉树作右平衡旋转处理*/
void Right_Root_Balance(BTree &T)
{
BTree rc,ld;
rc = T->rchild; //指向*T的左子树根结点
switch(rc->bf) //检查*T的右子树的平衡度，并作相应平衡处理 {
case -1: //新结点插入在*T的右孩子的右子树上，要作单左旋处理
T->bf = rc->bf =0;
Left_Balance(T); break;
case 1: //新结点插入在*T的右孩子的左子树上，要作双旋处理
ld = rc->lchild; //ld指向*T的右孩子的左子树根
switch(ld->bf) //修改*T及其右孩子的平衡因子
{
case 1:
T->bf = 0;
rc->bf = -1;
break;
case 0:
T->bf = rc->bf =0;
break;
case -1:
T->bf = 1;
rc->bf = 0;
break;
}
ld->bf = 0;
Right_Balance(T->rchild);//对*T的右子树作左旋平衡处理
Left_Balance(T); //对*T作左旋平衡处理
}
}
/*插入结点i,若T中存在和i相同关键字的结点，则插入一个数据元素为i的新结点，并返回１，否则返回０*/
bool InsertAVL(BTree &T,int i,bool &taller)
{
if(!T)//插入新结点，树“长高”，置taller为true
{
T = (BTree)malloc(sizeof(BTNode));
T->data = i;
T->lchild = T->rchild =NULL;
T->bf = 0;
taller = 1;
}
else
{
if(i==T->data) //树中已存在和有相同关键字的结点 {
taller = 0;
printf("已存在相同关键字的结点\n");
return 0;
}
if(idata) //应继续在*T的左子树中进行搜索 {
if(!InsertAVL(T->lchild,i,taller))
return 0;
}
else //应继续在*T的右子树中进行搜索
{
if(!InsertAVL(T->rchild,i,taller))
return 0;
}
}
return 1;
}
/*输出平衡二叉树*/
void PrintBT(BTree T)
{
{
printf("%d",T->data);
if(T->lchild||T->rchild)
{
printf("(");
PrintBT(T->lchild);
printf(",");
PrintBT(T->rchild);
printf(")");
}
}
}
/*删除结点时左平衡旋转处理*/
void Left_Root_Balance_det(BTree &p,int &shorter)
{
BTree p1,p2;
if(p->bf==1) //p结点的左子树高，删除结点后p的bf减,树变矮
{
p->bf=0;
shorter=1;
}
else if(p->bf==0)//p结点左、右子树等高，删除结点后p的bf减,树高不变 {
p->bf=-1;
shorter=0;
}
else //p结点的右子树高
{
p1=p->rchild;//p1指向p的右子树
if(p1->bf==0)//p1结点左、右子树等高,删除结点后p的bf为-2,进行左旋处理，树高不变
{
Left_Balance(p);
p1->bf=1;
p->bf=-1;
shorter=0;
}
else if(p1->bf==-1)//p1的右子树高，左旋处理后，树变矮
{
Left_Balance(p);
p1->bf=p->bf=0;
shorter=1;
else //p1的左子树高,进行双旋处理(先右旋后左旋)，树变矮 {
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)
{
p->bf=1;
p1->bf=0;
}
else
{
p->bf=0;
p1->bf=-1;
}
p2->bf=0;
p=p2;
shorter=1;
}
}
}
/*删除结点时右平衡旋转处理*/
void Right_Root_Balance_det(BTree &p,int &shorter)
{
BTree p1,p2;
if(p->bf==-1)
{
p->bf=0;
shorter=1;
}
else if(p->bf==0)
{
p->bf=1;
shorter=0;
}
else
{
p1=p->lchild;
if(p1->bf==0)
{
Right_Balance(p);
p1->bf=-1;
p->bf=1;
shorter=0;
}
else if(p1->bf==1)
{
Right_Balance(p);
p1->bf=p->bf=0;
shorter=1;
}
else
{
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)
{
p->bf=-1;
p1->bf=0;
}
else
{
p->bf=0;
p1->bf=1;
}
p2->bf=0;
p=p2;
shorter=1;
}
}
}
/*删除结点*/
void Delete(BTree q,BTree &r,int &shorter)
{
if(r->rchild==NULL)
{
q->data=r->data;
q=r;
r=r->lchild;
free(q);
shorter=1;
}
else
{
Delete(q,r->rchild,shorter);
if(shorter==1)
Right_Root_Balance_det(r,shorter);
}
}
/*二叉树的删除操作*/
int DeleteAVL(BTree &p,int x,int &shorter)
{
int k;
BTree q;
if(p==NULL)
{
printf("不存在要删除的关键字!!\n");
return 0;
}
else if(x
data)//在p的左子树中进行删除
{
k=DeleteAVL(p->lchild,x,shorter);
if(shorter==1)
Left_Root_Balance_det(p,shorter);
return k;
}
else if(x>p->data)//在p的右子树中进行删除
{
k=DeleteAVL(p->rchild,x,shorter);
if(shorter==1)
Right_Root_Balance_det(p,shorter);
return k;
}
else
{
q=p;
if(p->rchild==NULL) //右子树空则只需重接它的左子树
{
p=p->lchild;
free(q);
shorter=1;
}
else if(p->lchild==NULL)//左子树空则只需重接它的右子树
{
p=p->rchild;
free(q);
shorter=1;
}
else//左右子树均不空
{
Delete(q,q->lchild,shorter);
if(shorter==1)
Left_Root_Balance_det(p,shorter);
p=q;
}
return 1;
}
}
/*调平二叉树具体方法*/
bool SetAVL(BTree &T,int i,bool &taller)
{
if(!T)//插入新结点，树“长高”，置taller为true
{
T = (BTree)malloc(sizeof(BTNode));
T->data = i;
T->lchild = T->rchild =NULL;
T->bf = 0;
taller = 1;
}
else
{
if(i==T->data) //树中已存在和有相同关键字的结点 {
taller = false;
printf("已存在相同关键字的结点\n");
return 0;
}
if(idata) //应继续在*T的左子树中进行搜索 {
if(!SetAVL(T->lchild,i,taller))
return 0;
if(taller) //已插入到*T的左子树中且左子树“长高”
switch(T->bf) //检查*T的平衡度
{
case 1: //原本左子树比右子树高，需要作左平衡处理
Left_Root_Balance(T);
taller = false;
break;
case 0: //原本左子树、右子等高，现因左子树增高而使树增高
T->bf = 1;
taller = 1;
break;
case -1: //原本右子树比左子树高，现左、右子树等高
T->bf = 0;
taller = false;
break;
}
}
else //应继续在*T的右子树中进行搜索
{
if(!SetAVL(T->rchild,i,taller))
return 0;
if(taller) //已插入到*T的右子树中且右子树“长高”
switch(T->bf) //检查*T的平衡度
{
case 1: //原本左子树比右子树高，现左、右子树等高
T->bf = 0;
taller = false;
break;
case 0: //原本左子树、右子等高，现因右子树增高而使树增高
T->bf = -1;
taller = 1;
break;
case -1: //原本右子树比左子树高，需要作右平衡处理
Right_Root_Balance(T);
taller = 0;
break;
}
}
return 1;
}
}
/*二叉树调平操作*/
void Adj_balance(BTree &T)
{
int i;
bool taller=0;
T = NULL;
printf("\n请输入关键字(以-1结束建立平衡二叉树):");
scanf("%d",&i);
getchar();
while(i != -1)
{
SetAVL(T,i,taller);
printf("\n请输入关键字(以-1结束建立平衡二叉树):");
scanf("%d",&i);
getchar();
taller=0;
}
printf("平衡二叉树创建结束.\n");
if(T)
PrintBT(T);
else
printf("这是一棵空树.\n");
}
/*菜单函数*/
int menu( )
{
int m;
printf("..........................2015年7月1日......................\n\n");
printf(" 平衡二叉树\n");
printf(" ________________________________\n\n"); printf(" 1 创建平衡二叉树\n");
printf(" 2 在平衡二叉树上增加新结点并调平衡\n"); printf(" 3 删除一个结点\n");
printf(" 0 退出\n");
printf(" ________________________________\n\n"); printf(" 请输入所选功能0-3\n");
scanf("%d",&m);
return m;
}
/*主函数*/
void main()
{
int input,search;
bool taller=0;
int shorter=0;
BTree T;
T=(BTree)malloc(sizeof(BTNode));
T=NULL;
while(1)
{
printf("\n请选择需要的二叉树操作\n"); input=menu( );
switch(input)
{
case 1:
Adj_balance(T);
break;
case 2:
printf("请输入你要增加的关键字"); scanf("%d",&search);
getchar();
SetAVL(T,search,taller); PrintBT(T);
break;
case 3:
printf("请输入你要删除的关键字"); scanf("%d",&search);
getchar();
DeleteAVL(T,search,shorter); PrintBT(T);
break;
case 0:
break;
default:
printf("输入错误，请重新选择。"); break;
}
if(input == 0)
break;
printf("按任意键继续."); getchar();
}
}