cpp1.cpp

经典数据结构算法实现 平衡二叉树的建立和维护

#include<iostream.h>
#include<malloc.h>
#include<time.h>
#define LH 1
#define EH 0
#define RH -1

typedef struct BTnode{
	int data;
	int bf;
	BTnode*lchild,*rchild;
}*BSTree;

BTnode*lc,*rc,*rd,*ld;

void R_Rotate(BSTree&p)
{
	lc=p->lchild;
	p->lchild=lc->rchild;
	lc->rchild=p;
	p=lc;
}

void L_Rotate(BSTree&p)
{
	rc=p->rchild;
	p->rchild=rc->lchild;
	rc->lchild =p;
	p=rc;
}

void LeftBalance(BSTree&t)
{ 
	lc=t->lchild;
	switch(lc->bf){
	case LH:
		t->bf =lc->bf =EH;
		R_Rotate(t);
		break;
	case RH:
		rd=lc->rchild;
		switch(rd->bf){
		case LH:t->bf=RH;lc->bf =EH;break;
		case EH:t->bf=lc->bf=EH;break;
		case RH:t->bf=EH;lc->bf=LH;break;
		}
		rd->bf=EH;
		L_Rotate(t->lchild);
		R_Rotate(t);
		break;
}
}
void RightBalance(BSTree&t)
{ 
	rc=t->rchild ;
	switch(rc->bf){
	case RH:	
		t->bf =rc->bf =EH;
		L_Rotate(t);
        break;
	case LH:
		ld=rc->lchild ;
		switch(ld->bf){
		case LH:t->bf=RH;rc->bf =EH;break;
		case EH:t->bf=rc->bf=EH;break;
		case RH:t->bf=EH;rc->bf=LH;break;
		}
 		ld->bf=EH;
		R_Rotate(t->rchild );
		L_Rotate(t);
        break;		
	}	 
}

void preorder(BTnode*root)
{
 if(root!=NULL)
	{
	    cout<<" "<<root->data; 
        preorder(root->lchild); 
	    preorder(root->rchild);       	
	} 
}

void inorder(BTnode*root)
{
 if(root!=NULL)
	{	
        inorder(root->lchild); 
		cout<<" "<<root->data;		 
	    inorder(root->rchild);       	
	} 
}

void iinorder(BTnode*root)
{
 if(root!=NULL)
	{
	iinorder(root->rchild);
	cout<<" "<<root->data;
    iinorder(root->lchild);        	
	} 
}

int InsertAVL(BSTree&t,int e,int& taller)
{
	if(t==NULL){
		t=(BTnode*)malloc(100*sizeof(BTnode));
		t->data=e;
		t->lchild =NULL;
		t->rchild =NULL;
		t->bf =EH;
		taller =1;
	}
	else
	{
		if(e==t->data )
		{
			taller=0;
			cout<<"已经存在";
			return 0;
		}
		if(e<t->data)
		{
			if(InsertAVL(t->lchild,e,taller)==0)return 0;
	    
			if(taller==1)
			 
				switch(t->bf){
				case LH:					
					LeftBalance(t);taller = 0;break;
				case EH:
					t->bf =LH;taller=1;break;
				case RH:
					t->bf =EH;taller =0;break;
			}
		}
		else
		{
			if(InsertAVL(t->rchild ,e,taller)==0)return 0;
			if(taller==1)
					switch(t->bf){
				case LH:		
			 		t->bf =EH;taller =0;break;
				case EH:
					t->bf =RH;taller=1;break;
				case RH:
			 		RightBalance(t);taller = 0;break;			
				}
		}
	}
	return 1;
} 

int main()
{
	int input,flag,taller=0;
	BTnode*t;
	t=NULL;
	cout<<"输入数字 输入999结束";
    
	while(input!=999)
	{
	cout<<endl;
    cin>>input;
	if(input!=999){
flag=InsertAVL(t,input,taller);
cout<<endl<<"前序"<<endl;
preorder(t);
cout<<endl<<"中序"<<endl;
inorder(t);
cout<<endl<<"逆中序"<<endl;
iinorder(t);
	}
    }
	return 0;
}