|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
- #include<stdio.h>
- #include<stdlib.h>
- #define EH 0 /*等高*/
- #define LH 1 /*左高*/
- #define RH -1 /*右高*/
-
- typedef int ElemType; /*数据类型*/
- typedef struct BiTree{
- ElemType data; /*数据元素*/
- int BF; /*平衡因子*/
- struct BiTree *lchild,*rchild; /*左右子女指针*/
- }*Bitree,BitreeNode;
- int InsertAVL(Bitree *T,ElemType e,bool *taller);
- void LeftBalance(Bitree *T);
- void RightBalance(Bitree *T);
- void R_Rotate(Bitree *T);
- void L_Rotate(Bitree *T);
- bool *taller=(bool*)malloc(sizeof(bool));
- int main(void)
- {
- int data;
- Bitree T=NULL;
- while(1)
- {
- printf("enter the number(zero to exit):");
- scanf("%d",&data);
- if(0==data)break;
- InsertAVL(&T,data,taller);
-
- }
-
-
-
- return 0;
- }
- /*若在平衡的二叉排序树T 中不存在和e 有相同关键码的结点,则插入一个数据元素为e 的*/
- /*新结点,并反回1,否则反回0。若因插入而使二叉排序树失去平衡,则作平衡旋转处理,*/
- /*布尔型变量taller 反映T 长高与否*/
- int InsertAVL(Bitree *T,ElemType e,bool *taller)
- {
- if(!*T) /*插入新结点,树“长高”,置taller 为TURE*/
- {
- (*T)=(Bitree)malloc(sizeof(BitreeNode));
- (*T)->data = e;
- (*T)->lchild = (*T)->rchild = NULL;
- (*T)->BF = EH;
- *taller = true;
- }
- else
- {
- if(e==(*T)->data) /*树中存在和e 有相同关键码的结点,不插入*/
- {
- *taller = false;
- return 0;
- }
- if(e<(*T)->data)
- {
- if(!InsertAVL(&(*T)->lchild,e,taller)) return 0; /*未插入*/
- if(*taller)
- switch((*T)->BF)
- {
- case EH : /*原本左、右子树等高,因左子树增高使树增高*/
- (*T)->BF=LH;
- *taller=true;
- break;
-
- case LH : /*原本左子树高,需作左平衡处理*/
- LeftBalance(T);
- *taller=false;
- break;
-
- case RH : /*原本右子树高,使左、右子树等高*/
- (*T)->BF=EH;
- *taller=false;
- break;
-
- }
-
- }
- else
- {
- if(!InsertAVL(&(*T)->rchild,e,taller)) return 0; /*未插入*/
- if(*taller)
- switch((*T)->BF)
- {
- case EH : /*原本左、右子树等高,因右子树增高使树增高*/
- (*T)->BF=RH;
- *taller=true;
- break;
-
- case LH : /*原本左子树高,使左、右子树等高*/
- (*T)->BF=EH;
- *taller=false;
- break;
-
- case RH : /*原本右子树高,需作右平衡处理*/
- RightBalance(T);
- *taller=false;
- break;
-
- }
- }
- }
- return 1;
- }
- /*对以*p 指向的结点为根的子树,作左平衡旋转处理,处理之后,*p 指向的结点为子树的新根*/
- void LeftBalance(Bitree *T)
- {
- Bitree L=(*T)->lchild,Lr; /*L 指向*T左子树根结点*/
- switch(L->BF) /*检查L 平衡度,并作相应处理*/
- {
- case LH: /*新结点插在*p 左子树的左子树上,需作单右旋转处理*/
- (*T)->BF=L->BF=EH;
- R_Rotate(T);
- break;
- case EH: /*原本左、右子树等高,因左子树增高使树增高*/
- (*T)->BF=LH; //这里的EH好像没有写的必要
- *taller=true;
- break;
- case RH: /*新结点插在*T 左孩子的右子树上,需作先左后右双旋处理*/
- Lr=L->rchild; /*Lr 指向*p 左孩子的右子树根结点*/
- switch(Lr->BF) /*修正*T 及其左子树的平衡因子*/
- {
- case LH:
- (*T)->BF = RH;
- L->BF = EH;
- break;
- case EH:
- (*T)->BF = L->BF= EH;
- break;
- case RH:
- (*T)->BF = EH;
- L->BF = LH;
- break;
-
- }
- Lr->BF = EH;
- L_Rotate(&L); /*对*T 的左子树作左旋转处理*/
- R_Rotate(T); /*对*T 作右旋转处理*/
- }
- }
- //这里和leftbalance一个道理,试着自己写一下
- void RightBalance(Bitree *T)
- {
- Bitree Lr= (*T)->rchild,L;
- switch(Lr->BF)
- {
- case EH:
- *taller = true;
- (*T)->BF = RH;
- break;
- case RH:
- (*T)->BF=Lr->BF=EH;
- L_Rotate(T);
- break;
- case LH:
- L = Lr->lchild;
- switch(L->BF)
- {
- case EH:
- (*T)->BF=Lr->BF= EH;
- break;
- case RH:
- Lr->BF= EH;
- (*T)->BF = LH;
- break;
- case LH:
- (*T)->BF = LH;
- Lr->BF = EH;
- break;
-
- }
- L->BF = EH;
- R_Rotate(&Lr);
- L_Rotate(T);
-
- }
- }
- /*对以*T 指向的结点为根的子树,作右单旋转处理,处理之后,*T 指向的结点为子树的新根*/
- void R_Rotate(Bitree *T)
- {
- Bitree L=(*T)->lchild; /*L 指向*T 左子树根结点*/
- (*T)->lchild=L->rchild; /*L 的右子树挂接*T 的左子树*/
- L->rchild=*T; *T=L; /* *L 指向新的根结点*/
- }
- /*对以*p 指向的结点为根的子树,作左单旋转处理,处理之后,*p 指向的结点为子树的新根*/
- void L_Rotate(Bitree *T)
- {
- Bitree Lr=(*T)->rchild; /*Lr 指向*T 右子树根结点*/
- (*T)->rchild=Lr->lchild; /*L 的左子树挂接*p 的右子树*/
- Lr->lchild=*T;
- *T=Lr; /* *L 指向新的根结点*/
- }
复制代码
|
|