平衡二叉树的实现算法
孤风一剑
2月 08, 2014
226
平衡二叉树的实现算法
- /*
- 首先平衡二叉树是一个二叉排序树；
- 其基本思想是：
- 在构建二叉排序树的过程中，当每插入一个节点时，
- 先检查是否因为插入而破坏了树的平衡性，若是，
- 找出最小不平衡树，进行适应的旋转，使之成为新的平衡二叉树。
- */
- #include<cstdio>
- #include<cstdlib>
- #define LH 1
- #define EH 0
- #define RH -1
- using namespace std;
- typedef struct BTNode
- {
- int data;
- int BF;//平衡因子（balance factor）
- struct BTNode *lchild,*rchild;
- }BTNode,*BTree;
- void R_Rotate(BTree *p)//以p为根节点的二叉排序树进行右旋转
- {
- BTree L;
- L=(*p)->lchild;
- (*p)->lchild=L->rchild;
- L->rchild=(*p);
- *p=L;//p指向新的根节点
- }
- void L_Rotate(BTree *p)//以p为根节点的二叉排序树进行左旋转
- {
- BTree R;
- R=(*p)->rchild;
- (*p)->rchild=R->lchild;
- R->lchild=(*p);
- *p=R;
- }
- void LeftBalance(BTree *T)
- {
- BTree L,Lr;
- L=(*T)->lchild;
- switch(L->BF)
- {
- //检查T的左子树平衡度，并作相应的平衡处理
- case LH://新节点插入在T的左孩子的左子树上，做单右旋处理
- (*T)->BF=L->BF=EH;
- R_Rotate(T);
- break;
- case RH://新插入节点在T的左孩子的右子树上，做双旋处理
- Lr=L->rchild;
- switch(Lr->BF)
- {
- case LH:
- (*T)->BF=RH;
- L->BF=EH;
- break;
- case EH:
- (*T)->BF=L->BF=EH;
- break;
- case RH:
- (*T)->BF=EH;
- L->BF=LH;
- break;
- }
- Lr->BF=EH;
- L_Rotate(&(*T)->lchild);
- R_Rotate(T);
- }
- }
- void RightBalance(BTree *T)
- {
- BTree R,Rl;
- R=(*T)->rchild;
- switch(R->BF)
- {
- case RH://新节点插在T的右孩子的右子树上，要做单左旋处理
- (*T)->BF=R->BF=EH;
- L_Rotate(T);
- break;
- case LH://新节点插在T的右孩子的左子树上，要做双旋处理
- Rl=R->lchild;
- switch(Rl->BF)
- {
- case LH:
- (*T)->BF=EH;
- R->BF=RH;
- break;
- case EH:
- (*T)->BF=R->BF=EH;
- break;
- case RH:
- (*T)->BF=LH;
- R->BF=EH;
- break;
- }
- Rl->BF=EH;
- R_Rotate(&(*T)->rchild);
- L_Rotate(T);
- }
- }
- bool InsertAVL(BTree *T,int e,bool *taller)//变量taller反应T长高与否
- {
- if(!*T)
- {
- *T=(BTree)malloc(sizeof(BTNode));
- (*T)->data=e;
- (*T)->lchild=(*T)->rchild=NULL;
- (*T)->BF=EH;
- *taller=true;
- }
- else
- {
- if(e==(*T)->data)//不插入
- {
- *taller=false;
- return false;
- }
- if(e<(*T)->data)
- {
- if(!InsertAVL(&(*T)->lchild,e,taller))//未插入
- return false;
- if(*taller)//以插入左子树，且左子树变高
- {
- switch((*T)->BF)
- {
- case LH://原本左子树比右子树高，需要做左平衡处理
- LeftBalance(T);
- *taller=false;
- break;
- case EH://原本左右子树等高，现因左子树增高而树增高
- (*T)->BF=LH;
- *taller=true;
- break;
- case RH://原本右子树比左子树高，现在左右子树等高
- (*T)->BF=EH;
- *taller=false;
- break;
- }
- }
- }
- else
- {
- //应在T的右子树中搜寻
- if(!InsertAVL(&(*T)->rchild,e,taller))
- return false;
- if(*taller)//插入右子树，且右子树长高
- {
- switch((*T)->BF)
- {
- case LH://原本左子树比右子树高，现在左右子树等高
- (*T)->BF=EH;
- *taller=false;
- break;
- case EH://原本左右子树等高，现在右子树变高
- (*T)->BF=RH;
- *taller=true;
- break;
- case RH://原本右子树比左子树高，现在需做右平衡处理
- RightBalance(T);
- *taller=false;
- break;
- }
- }
- }
- }
- return true;
- }
- bool Find(BTree T,int key)
- {
- if(!T)
- return false;
- else if(T->data==key)
- return true;
- else if(T->data<key)
- return Find(T->rchild,key);
- else
- return Find(T->lchild,key);
- }
- void Output(BTree T)
- {
- if(T)
- {
- printf(“%d”,T->data);
- if(T->lchild||T->rchild)
- {
- printf(“(“);
- Output(T->lchild);
- printf(“,”);
- Output(T->rchild);
- printf(“)”);
- }
- }
- }
- int main(int argc,char *argv[])
- {
- int i;
- int A[]={3,2,1,4,5,6,7,10,9,8};
- BTree T=NULL;
- bool taller;
- for(i=0;i<sizeof(A)/sizeof(int);i++)
- InsertAVL(&T,A[i],&taller);
- Output(T);
- printf(“\n”);
- if(Find(T,6))
- printf(“6 is find in the AVL tree!\n”);
- else
- printf(“6 is not find in the AVL tree!\n”);
- return 0;
- }
