| 等 级 | |
| 排 名 | 59 |
| 经 验 | 11049 |
| 参赛次数 | 2 |
| 文章发表 | 35 |
| 年 龄 | 21 |
| 在职情况 | 学生 |
| 学 校 | |
| 专 业 | 软件工程 |
自我简介：
TA的其他文章
原题链接：数据结构-平衡二叉树的基本操作
参考代码:
#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++代码）浏览：1225 |
C语言训练-列出最简真分数序列* （C语言代码）浏览：658 |
【绝对值排序】 （C语言代码）浏览：892 |
母牛的故事 （C语言代码）浏览：739 |
1113题解浏览：823 |
C语言程序设计教程（第三版）课后习题1.5 （C语言代码）浏览：645 |
1012题解浏览：938 |
关于float，double变量的几点说明浏览：1926 |
简单的a+b （C语言代码）浏览：572 |
C语言程序设计教程（第三版）课后习题9.6 （C语言代码）浏览：627 |