,只有想清楚全部情况后,才能对BF进行判断
#include<stdio.h> #include<stdlib.h> typedef struct BiTre{ int data; int bf; struct BiTre *rchild,*lchild; }BiTnood,*BiTree; void R_Rotate(BiTree *p) { BiTree l = (*p)->lchild; (*p)->lchild = l->rchild; l->rchild = (*p); (*p) = l; } void L_Rotate(BiTree *p) { BiTree l = (*p)->rchild; (*p)->rchild = l->lchild; l->lchild = (*p); (*p)= l; } void LeftBalance(BiTree *T)//改变左子树的状态 { BiTree L,Lr; L = (*T)->lchild; switch(L->bf) { case 1: L->bf=0; (*T)->bf = 0; R_Rotate(T); break; case -1: Lr = L->rchild; switch(Lr->bf) { case 0: L->bf=0; (*T)->bf=0; break; case 1: (*T)->bf = 1; L->bf = 0; break; case -1: (*T)->bf = 0; L->bf = -1; break; } Lr->bf = 0; L_Rotate(&((*T)->lchild)); R_Rotate(T); } } void ReftBalance(BiTree *T)//改变右子树的状态 { BiTree R,Rl; R = (*T)->rchild; switch(R->bf) { case -1: (*T)->bf = 0; R->bf = 0; R_Rotate(T); break; case 1: Rl = R->lchild; switch(Rl->bf) { case 0: (*T)->bf=0; R->bf=0; break; case 1: (*T)->bf = 0; R->bf = -1; break; case -1: (*T)->bf = 1; R->bf = 0; } Rl->bf=0; R_Rotate(&((*T)->rchild)); L_Rotate(T); } } int main() { return 0; }