|
//AVL tree
/*
本文件为严蔚敏<<数据结构>>p236 avl tree算法9.9-9.12的实现
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
void print(int *str, int len)
{
int i=1;
printf("==> str: ");
while(i<=len)
printf("%d ", str[i++]);
printf("\n");
}
typedef struct BSTNode{
int data;
int bf;
struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;
//inorder print
void InOrder(BSTree T)
{
if(T){
InOrder(T->lchild);
printf("%d ",T->data);
InOrder(T->rchild);
}
}
//对以*p为根的二叉排序树作右旋处理, 处理后p指向新的树根结点,
//即旋转处理之前的左子树的根结点
void R_Rotate(BSTree *p)
{
printf("r ");
BSTNode *lc;
lc = (*p)->lchild; //lc指向ptr左子树根结点
(*p)->lchild = lc->rchild; //lc右子树挂接为ptr的左子树
lc->rchild = (*p); (*p) = lc; //p指向新的根结点
#if 0
BSTNode *ptr = *p, *lc;
lc = ptr->lchild; //lc指向ptr左子树根结点
ptr->lchild = lc->rchild; //lc右子树挂接为ptr的左子树
lc->rchild = ptr; ptr = lc; //p指向新的根结点
#endif
}
//对以*p为根的二叉排序树作左旋处理, 处理后p指向新的树根结点,
//即旋转处理之前的右子树的根结点
void L_Rotate(BSTree *p)
{
printf("l ");
BSTNode *rc;
rc = (*p)->rchild; //rc指向ptr右子树根结点
(*p)->rchild = rc->lchild; //rc左子树挂接为ptr的右子树
rc->lchild = (*p); (*p) = rc; //p指向新的根结点
#if 0
BSTNode *ptr = *p, *rc;
rc = ptr->rchild; //rc指向ptr右子树根结点
ptr->rchild = rc->lchild; //rc左子树挂接为ptr的右子树
rc->lchild = ptr; ptr = rc; //p指向新的根结点
#endif
}
#define LH +1
#define EH 0
#define RH -1
#define TRUE 1
#define FALSE 0
//对以指针T所指结点为根的二插树作左平衡旋转处理, 本算法结束时,
//指针T指向新的根结点
void LeftBalance(BSTree *T)
{
BSTNode *ptr=*T;
BSTNode *lc, *rd;
lc=ptr->lchild; //lc指向*T的左子树根结点
switch(lc->bf){ //检查*T的左子树的平衡度, 并作相应平衡处理
case LH: //新结点插入在*T的左孩子的左子树上, 要作单右旋处理
ptr->bf = lc->bf = EH;
R_Rotate(&ptr); break;
case RH: //新结点插入在*T的左孩子的右子树上, 要作双旋处理
rd=lc->rchild; //rd指向*T的左孩子的右子树
switch(rd->bf){ //修改*T及其左孩子的平衡因子
case LH: ptr->bf = RH; lc->bf = EH; break;
case EH: ptr->bf = lc->bf = EH; break;
case RH: ptr->bf = EH; lc->bf = LH; break;
}
rd->bf = EH;
L_Rotate(&(ptr->lchild)); //对*T的左子树作左旋平衡处理
R_Rotate(&ptr); //对*T作右旋平衡处理
break;
case EH:
printf("Tree is already balanced.\n");
break;
}
*T = ptr;
}
void RightBalance(BSTree *T)
{
BSTNode *ptr=*T;
BSTNode *rc, *ld;
rc=ptr->rchild;
switch(rc->bf){ //检查*T的右子树的平衡度, 并作相应平衡处理
case RH: //新结点插入在*T的右孩子的右子树上, 要作单左旋处理
ptr->bf = rc->bf = EH;
L_Rotate(&ptr); break;
case LH: //新结点插入在*T的右孩子的左子树上, 要作双旋处理
ld=rc->lchild; //ld指向*T的右孩子的左子树
switch(ld->bf){ //修改*T及其右孩子的平衡因子
case RH: ptr->bf = LH; rc->bf = EH; break;
case EH: ptr->bf = rc->bf = EH; break;
case LH: ptr->bf = EH; rc->bf = RH; break;
}
ld->bf = EH;
R_Rotate(&(ptr->rchild)); //对*T的右子树作右旋平衡处理
L_Rotate(&ptr); //对*T作左旋平衡处理
break;
case EH:
printf("Tree is already balanced.\n");
break;
}
*T = ptr;
}
//若在平衡的二叉排序树T中不存在和e有相同关键字的结点, 则插入一个数据元素
//为e的新结点, 并返回1, 否则返回0. 若因插入而使二插排序树失去平衡, 则作平衡
//旋转处理, 布尔变量taller反映T长高与否
int InsertAVL(BSTree *T, int e, int *taller)
{
BSTNode *ptr;// = *T;
if(!*T){//插入新结点, 树长高, 置taller为TRUE
ptr = (BSTree)malloc(sizeof(BSTNode));
ptr->data = e;
ptr->lchild = ptr->rchild = NULL;
ptr->bf = EH;
*taller = TRUE;
//T = &ptr;
*T=ptr;
}else{
ptr = *T;
if(e == ptr->data){//树中已存在和e有相同关键字的节点则不再插入
*taller = FALSE; return 0;
}
if(e < ptr->data){ //应继续在*T的左子树中进行搜索
if(!InsertAVL(&(ptr->lchild), e, taller)) return 0;//未插入
if(*taller){ //已插入到*T的左子树中且左子树"长高"
switch(ptr->bf){ //检查*T的平衡度
case LH: //原本左子树比右子树高, 需要作左平衡处理
LeftBalance(&ptr); *taller=FALSE; break;
case EH: //原本左, 右子树等高, 现因左子树增高而使树增高
ptr->bf=LH; *taller=TRUE; break;
case RH: //原本右子树比左子树高, 现左,右子树等高
ptr->bf=EH; *taller=FALSE; break;
}
}
}else{ //应继续在*T的右子树中进行搜索
if(!InsertAVL(&(ptr->rchild), e, taller)) return 0;//未插入
if(*taller){ //已插入到*T的右子树中且右子树"长高"
switch(ptr->bf){ //检查*T的平衡度
case LH: //原本左子树比右子树高, 现左,右子树等高
ptr->bf=EH; *taller=FALSE; break;
case EH: //原本左, 右子树等高, 现因右子树增高而使树增高
ptr->bf=RH; *taller=TRUE; break;
case RH: //原本右子树比左子树高, 需要作右平衡处理
RightBalance(&ptr); *taller=FALSE; break;
}
}
}
*T=ptr;
}//if(!T)-else
return 1;
}
int main(void)
{
int len;
int a[30];
int i;
BSTree T=NULL;
int taller = FALSE;
while(1){
printf("input string length: ");
scanf(" %d", &len);
fflush(stdin);
if(len == 0) break;
//设置rand函数所用的启始种子值，以期每次产生的随机数序列均不相同。
srand(time(NULL));
i = 0;
while(i++ < len){//a[0] 为哨岗
a[i] = rand() % 100;
printf("%d ", a[i]);
}
putchar('\n');
//a[1] = 7; a[2] = 80; a[3] = 59; a[4] = 50;
//a[5] = 29; a[6] = 41; a[7] = 4; a[8] = 8;
//a[9] = 80; a[10] = 30; a[11] = 85;
//len = 11;
i=1;
while(i<=len){
InsertAVL(&T, a[i++], &taller);
}
printf("\n=====> ");
InOrder(T);
printf("\n");
//need to destroy the tree.
i=1;
while(i<=len)
printf("%d ", a[i++]);
printf("\n");
}//while(1)
return 0;
}
|
