参考代码:
#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语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:799 |
1642题解浏览:716 |
sizeof的大作用 (C语言代码)浏览:1452 |
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:1466 |
计算质因子 (C语言代码)浏览:707 |
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:568 |
上车人数 (C语言代码)浏览:713 |
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:510 |
C语言训练-排序问题<1> (C语言代码)浏览:355 |
简单的a+b (C语言代码)浏览:454 |