原题链接：数据结构-平衡二叉树的基本操作
参考代码:
#include<stdio.h>
#include<malloc.h>
#define True 1
#define False 0
#define EH 0
#define LH 1
#define RH -1
typedef int ElemType;
typedef struct BSTNode{
ElemType data;
int bf;
struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;
void LeftRotate(BSTree *p);
void RightRotate(BSTree *p);
void LeftBalance(BSTree *T);
void RightBalance(BSTree *T);
int InsertAVL(BSTree *T, ElemType key, int *taller);
int SearchKey(BSTree T, ElemType key);
void Free(BSTree *T);
int main()
{
BSTree T = NULL;
int n, k, key;
int taller;
scanf("%d%d", &n, &k);
while(n--){
scanf("%d", &key);
InsertAVL(&T, key, &taller);
}
while(k--){
scanf("%d", &key);
printf("%d ", SearchKey(T, key));
}
printf("\n");
Free(&T);
return 0;
}
void LeftRotate(BSTree *p){
BSTNode *t = (*p)->rchild;
(*p)->rchild = t->lchild;
t->lchild = *p;
*p = t;
}
void RightRotate(BSTree *p){
BSTNode *t = (*p)->lchild;
(*p)->lchild = t->rchild;
t->rchild = *p;
*p = t;
}
void LeftBalance(BSTree *T){
BSTNode *lc = (*T)->lchild;
switch(lc->bf){
case LH:{
lc->bf = (*T)->bf = EH;
RightRotate(T);
break;
}
case RH:{
BSTNode *lr = lc->rchild;
switch(lr->bf){
case EH:{
lc->bf = (*T)->bf = EH;
break;
}
case LH:{
lc->bf = EH;
(*T)->bf = RH;
break;
}
case RH:{
lc->bf = LH;
(*T)->bf = EH;
break;
}
}
lr->bf = EH;
LeftRotate(&(*T)->lchild);
RightRotate(T);
}
}
}
void RightBalance(BSTree *T){
BSTNode *rc = (*T)->rchild;
switch(rc->bf){
case RH:{
rc->bf = (*T)->bf = EH;
LeftRotate(T);
break;
}
case LH:{
BSTNode *rl = rc->lchild;
switch(rl->bf){
case EH:{
rc->bf = (*T)->bf = EH;
break;
}
case RH:{
rc->bf = EH;
(*T)->bf = LH;
break;
}
case LH:{
rc->bf = RH;
(*T)->bf = EH;
break;
}
}
rl->bf = EH;
RightRotate(&(*T)->rchild);
LeftRotate(T);
}
}
}
int InsertAVL(BSTree *T, ElemType key, int *taller){
if(!*T){
*T = (BSTNode *)malloc(sizeof(BSTNode));
(*T)->bf = EH;
(*T)->data = key;
(*T)->lchild = NULL;
(*T)->rchild = NULL;
*taller = True;
return True;
}
else if(key == (*T)->data){
*taller = False;
return False;
}
else if(key < (*T)->data){
if(InsertAVL(&(*T)->lchild, key, taller) == False){
return False;
}
if(*taller == True){
switch((*T)->bf){
case EH:{
(*T)->bf = LH;
break;
}
case RH:{
(*T)->bf = EH;
*taller = False;
break;
}
case LH:{
LeftBalance(T);
*taller = False;
break;
}
}
}
return True;
}
else{
if(InsertAVL(&(*T)->rchild, key, taller) == False){
return False;
}
if(*taller == True){
switch((*T)->bf){
case EH:{
(*T)->bf = RH;
break;
}
case LH:{
(*T)->bf = EH;
*taller = False;
break;
}
case RH:{
RightBalance(T);
*taller = False;
break;
}
}
}
}
return True;
}
int SearchKey(BSTree T, ElemType key){
BSTNode *p = T;
while(p){
if(key == p->data) return True;
else if(key < p->data) p = p->lchild;
else p = p->rchild;
}
return False;
}
void Free(BSTree *T) {
if (*T) {
Free(&(*T)->lchild);
Free(&(*T)->rchild);
free(*T);
*T = NULL;
}
}0.0分
2 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复