那位大神给个平衡二叉树的代码给小弟参考参考下
那位大神给个平衡二叉树的代码给小弟参考参考下
#include <stdio.h> #include <math.h> #include <stdlib.h> #define MAX 10 #define ADD 5 typedef struct node { int bf;//平衡因子 int data;//结点存储的数据 int depth;//结点的深度 struct node *lchild, *rchild; }*AVL_T; typedef struct { AVL_T *base; AVL_T *top; int stack_size; }AVL_Stack; typedef struct { AVL_T *base; int front; int rear; int q_size; }AVL_Queue; /* *判断二叉树是否平衡 平衡返回1值 否则返回0值 */ int Balance( AVL_T T ) { if( T ) { if( abs(T->bf) > 1 ) { return 0; } else { return Balance(T->rchild) | Balance(T->lchild); } } else {//当为空树的时候 为平衡状态 return 1; } } /* *计算出数的平衡因子 */ void Count_bf( AVL_T T ) { if( T ) { int l, r; if( T->rchild ) { r = T->rchild->depth; } else { r = 0; } if( T->lchild ) { l = T->lchild->depth; } else { l = 0; } T->bf = l - r; Count_bf( T->lchild ); Count_bf( T->rchild ); } } /* *得出两个整数中较大的那个数 */ int Max( int a, int b ) { return a>b?a:b; } /* *计算树中结点的深度 */ int Count_depth( AVL_T T ) { if( T ) { return T->depth = 1 + Max( Count_depth(T->rchild), Count_depth(T->lchild) ); } else { return 0; } } /* *查找p的双亲 找到就赋值为f 否则f为NULL 找到则返回1 否则返回0 */ int Searchf( AVL_T T, AVL_T &f, int p ) { if( T ) { if( T->data == p ) { f = NULL; return 0; } else if( T->data > p ) { if( T->lchild ) { if( T->lchild->data == p ) { f = T; return 1; } else { Searchf( T->lchild, f, p ); } } else { f = NULL; return 0; } } else { if( T->rchild ) { if( T->rchild->data == p ) { f = T; return 1; } else { Searchf( T->rchild, f, p ); } } else { f = NULL; return 0; } } } else { f = NULL; return 0; } } /* *找到和i相同的返回1 否则0 */ int Search_AVL( AVL_T T, int i, AVL_T &p ) { if( T ) { p = T; if( T->data == i ) { return 1; } else if( i > T->data ) { return Search_AVL( T->rchild, i, p ); } else { return Search_AVL( T->lchild, i, p ); } } else { return 0; } } /* *在树种插入结点i */ int Insert_AVL( AVL_T &T, int i ) { AVL_T p; if( !Search_AVL( T, i, p ) ) {//表示相同的结点值是不进行插入操作 AVL_T temp; temp = (AVL_T) malloc (sizeof(AVL_T)); temp->bf = 0; temp->data = i; temp->depth = 1; temp->lchild = temp->rchild = NULL; if( !T ) { T = temp; } else if( p->data > i ) { p->lchild = temp; } else { p->rchild = temp; } return 1; } else { return 0; } } ///////////栈的操作/////////////////////// void Init_Stack( AVL_Stack &S ) { S.base = (AVL_T*) malloc (MAX*sizeof(AVL_T)); if( !S.base ) exit(0); S.top = S.base; S.stack_size = MAX; } void Push_Stack( AVL_Stack &S, AVL_T temp ) { if( S.top - S.base >= S.stack_size ) { S.base = (AVL_T*) realloc (S.base, (ADD+S.stack_size)*sizeof(AVL_T)); S.top = S.base + S.stack_size; S.stack_size += ADD; } *S.top++ = temp; } void Pop_Stack( AVL_Stack &S, AVL_T &temp ) { if( S.base == S.top ) return; temp = *--S.top; } int Empty_Stack( AVL_Stack S ) { if( S.base == S.top ) return 1; else return 0; } ///////////// ///////////队的基本操作///////////////// void Init_Queue( AVL_Queue &Q ) { Q.base = (AVL_T *) malloc (MAX*sizeof(AVL_T)); if( !Q.base ) exit( 0 ); Q.front = Q.rear = 0; Q.q_size = MAX; } void Enter_Queue( AVL_Queue &Q, AVL_T temp ) { if( Q.rear >= Q.q_size-1 ) { Q.base = ( AVL_T * ) realloc (Q.base,(Q.q_size+ADD)*sizeof(AVL_T)); if( !Q.base ) exit( 0 ); Q.q_size += ADD; } Q.base[Q.rear++] = temp; } void Delete_Queue( AVL_Queue &Q, AVL_T &temp ) { if( Q.front == Q.rear ) return ; temp = Q.base[Q.front++]; } int Empty_Queue( AVL_Queue Q ) { if( Q.front == Q.rear ) return 1; else return 0; } void Destroy_Queue( AVL_Queue &Q ) { if( Q.base ) { free( Q.base ); Q.front = Q.rear = 0; Q.q_size = 0; } } /* *将所有的不平衡的点压入栈S中 层序遍历 */ void Traverse_AVL( AVL_T T, AVL_Stack &S ) { AVL_Queue Q; AVL_T temp; Init_Queue( Q ); if( T ) { Enter_Queue( Q, T ); while( !Empty_Queue( Q ) ) { Delete_Queue( Q, temp ); if( abs( temp->bf ) > 1 ) Push_Stack( S, temp ); if( temp->lchild ) Enter_Queue( Q, temp->lchild ); if( temp->rchild ) Enter_Queue( Q, temp->rchild ); } } } /* *进行调整 */ void Change_AVL( AVL_T &T ) { AVL_Stack S;//压入所有的不平衡点 AVL_T f = NULL;//如果不为NULL 就表示当前不平衡点的双亲 AVL_T p;//表示当前不平衡点 AVL_T pl, pr;//表示当前不平衡点的左、右孩子 AVL_T plr, prl;//表示当前不平衡点的左(右)孩子的右(左)孩子 Init_Stack( S ); Traverse_AVL( T, S ); Pop_Stack( S, p ); Searchf( T, f, p->data ); if( p->bf == 2 )//L { pl = p->lchild; plr = pl->rchild; if( f == NULL ) { if( pl->bf == 1 )//L { p->lchild = pl->rchild; pl->rchild = p; T = pl; } else if( pl->bf == -1 )//R { p->lchild = plr->rchild; pl->rchild = plr->lchild; plr->rchild = p; plr->lchild = pl; T = plr; } else if( pl->bf == 0 ) { p->lchild = pl->rchild; pl->rchild = p; T = pl; } } else { if( pl->bf == 1 )//L { p->lchild = pl->rchild; pl->rchild = p; if( f->data > p->data ) f->lchild = pl; else f->rchild = pl; } else if( pl->bf == -1 )//R { p->lchild = plr->rchild; pl->rchild = plr->lchild; plr->rchild = p; plr->lchild = pl; if( f->data > p->data ) f->lchild = plr; else f->rchild = plr; } else if( pl->bf == 0 ) { p->lchild = pl->rchild; pl->rchild = p; if( f->data > p->data ) f->lchild = pl; else f->rchild = pl; } } } else if( p->bf == -2 )//R { pr = p->rchild; prl = pr->lchild; if( f == NULL ) { if( pr->bf == -1 )//R { p->rchild = pr->lchild; pr->lchild = p; T = pr; } else if( pr->bf == 1 )//L { p->rchild = prl->lchild; pr->lchild = prl->rchild; prl->lchild = p; prl->rchild = pr; T = prl; } else if( pr->bf == 0 ) { p->rchild = pr->lchild; pr->lchild = p; T = pr; } } else { if( pr->bf == -1 )//R { p->rchild = pr->lchild; pr->lchild = p; if( f->data > p->data ) f->lchild = pr; else f->rchild = pr; } else if( pr->bf == 1 )//L { p->rchild = prl->lchild; pr->lchild = prl->rchild; prl->lchild = p; prl->rchild = pr; if( f->data > p->data ) f->lchild = prl; else f->rchild = prl; } else if( pr->bf == 0 )// { p->rchild = pr->lchild; pr->lchild = p; if( f->data > p->data ) f->lchild = pr; else f->rchild = pr; } } } } /* *打印结果 */ void Show( AVL_T T ) { if(T) { printf("%d %d %d\n", T->data, T->depth, T->bf); Show( T->lchild ); Show( T->rchild ); } } int main() { AVL_T T = NULL; int temp; while( scanf("%d", &temp) ) { if( Insert_AVL(T, temp) )//插入成功返回1值 { Count_depth(T); Count_bf(T); while( !Balance(T) ) {//到达平衡时才退出 Change_AVL(T); Count_depth(T); Count_bf(T); } } } Show( T ); return 0; }没有删除操作