二叉平衡树算法c语言,算法9-9~9-12：平衡二叉树的基本操作 （C语言代码）
參考代碼:
#include
#include
#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?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?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;
}
}
總結(jié)
以上是生活随笔為你收集整理的二叉平衡树算法c语言,算法9-9~9-12：平衡二叉树的基本操作 （C语言代码）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 99用c语言怎么写出来的,c语言的书写格
- 下一篇： 消除类游戏ccf c语言,ccf试题 消