2chashu.cpp

自平衡2叉树

#include <stdio.h>
#include <malloc.h>
#define LEFT  0
#define RIGHT 1
typedef struct node
{
	int data;
	int bf;                      
	struct node *lchild,*rchild;
}avlnode;
/*--------------------------------------------------------------------------------------------*/
void insert(avlnode *p,avlnode *parent,int key,int p_fx,int &c_fx,int &change)    //P为根节点也是当前节点，parent为当前节点的父亲节点，p_fx表示当前节点是父亲节点左孩子还是右孩子
{																				  //c_fx表示第当前节点下一个节点的方向，用来判断那种失衡类型，change为是否需要修改平衡因子的开关，0为不需要，1相反
	avlnode *temp;
	temp=p;                                                                       //下一个节点的父亲节点
	if(p!=NULL)
		if(key < p->data)
		{
			insert(p->lchild,temp,key,LEFT,c_fx,change);                          //递归，小于是向左探索
			/*------------------------------------------------b------------------*/
			if(change)
			{
				p->bf++;
				if(p->bf==2)
				{
					if(c_fx==LEFT)      //LL
					{
						if(p_fx==LEFT)                        //判断失衡节点是他父亲节点左孩子还是右孩子
						{
							parent->lchild=p->lchild;		  //调平
							p->lchild=parent->lchild->rchild;
							parent->lchild->rchild=p;
							p->bf=0;
							parent->lchild->bf=0;
							change=0;
						}
						else
						{
							parent->rchild=p->lchild;         //调平
							p->lchild=parent->rchild->rchild;
							parent->rchild->rchild=p;
							p->bf=0;
							parent->rchild->bf=0;
							change=0;
						}
					}
					else if(c_fx==RIGHT)//LR
					{
						if(p_fx==LEFT)
						{
							parent->lchild=p->lchild->rchild;           //调平
							p->lchild->rchild=parent->lchild->lchild;
							parent->lchild->lchild=p->lchild;
							p->lchild=parent->lchild->rchild;
							parent->lchild->rchild=p;
							if(parent->lchild->bf==-1)					//根据节点C的平衡因子情况来重新得到现三个节点的平衡因子
							{
								parent->lchild->bf=0;
								p->bf=0;
								parent->lchild->lchild->bf=1;
								change=0;
							}
							else if(parent->lchild->bf==1)
							{
								parent->lchild->bf=0;
								p->bf=-1;
								parent->lchild->lchild->bf=0;
								change=0;
							}
							else
							{
								parent->lchild->bf=0;
								p->bf=0;
								parent->lchild->lchild->bf=0;
								change=0;
							}
						}
						else
						{
							parent->rchild=p->lchild->rchild;
							p->lchild->rchild=parent->rchild->lchild;
							parent->rchild->lchild=p->lchild;
							p->lchild=parent->rchild->rchild;
							parent->rchild->rchild=p;
							if(parent->rchild->bf==-1)
							{
								parent->rchild->bf=0;
								p->bf=0;
								parent->rchild->lchild->bf=1;
								change=0;
							}
							else if(parent->rchild->bf==1)
							{
								parent->rchild->bf=0;
								p->bf=-1;
								parent->rchild->lchild->bf=0;
								change=0;
							}
							else
							{
								parent->rchild->bf=0;
								p->bf=0;
								parent->rchild->lchild->bf=0;
								change=0;
							}
						}
					}//end of LR
				}//end of if(bf==2)
				else if(p->bf==0)
					change=0;
				else;
				c_fx=0;
			}//end of if(change)
		/*---------------------------------------------------end b---此间代码可看成一条语句*/
		}//end of if(key< p ->data)
		else if(key > p->data)
		{
			insert(p->rchild,temp,key,RIGHT,c_fx,change);								//递归
			/*--------------------------------------------------------a-----------------*/
			if(change)
			{
				p->bf--;
				if(p->bf==-2)
				{
					if(c_fx==RIGHT)      //RR
					{
						if(p_fx==LEFT)
						{
							parent->lchild=p->rchild;
							p->rchild=parent->lchild->lchild;
							parent->lchild->lchild=p;
							p->bf=0;
							parent->lchild->bf=0;
							change=0;
						}
						else
						{
							parent->rchild=p->rchild;
							p->rchild=parent->rchild->lchild;
							parent->rchild->lchild=p;
							p->bf=0;
							parent->rchild->bf=0;
							change=0;
						}
					}
					else if(c_fx==LEFT)//RL
					{
						if(p_fx==LEFT)
						{
							parent->lchild=p->rchild->lchild;
							p->rchild->lchild=parent->lchild->rchild;
							parent->lchild->rchild=p->rchild;
							p->rchild=parent->lchild->lchild;
							parent->lchild->lchild=p;
							if(parent->lchild->bf==-1)
							{
								parent->lchild->bf=0;
								p->bf=1;
								parent->lchild->rchild->bf=0;
								change=0;
							}
							else if(parent->lchild->bf==1)
							{
								parent->lchild->bf=0;
								p->bf=0;
								parent->lchild->rchild->bf=-1;
								change=0;
							}
							else
							{
								parent->lchild->bf=0;
								p->bf=0;
								parent->lchild->rchild->bf=0;
								change=0;
							}
						}
						else
						{
							parent->rchild=p->rchild->lchild;
							p->rchild->lchild=parent->rchild->rchild;
							parent->rchild->rchild=p->rchild;
							p->rchild=parent->rchild->lchild;
							parent->rchild->lchild=p;
							if(parent->rchild->bf==-1)
							{
								parent->rchild->bf=0;
								p->bf=1;
								parent->rchild->rchild->bf=0;
								change=0;
							}
							else if(parent->rchild->bf==1)
							{
								parent->rchild->bf=0;
								p->bf=0;
								parent->rchild->rchild->bf=-1;
								change=0;
							}
							else
							{
								parent->rchild->bf=0;
								p->bf=0;
								parent->rchild->rchild->bf=0;
								change=0;
							}
						}
					}//end of RL
				}//end of if(bf==2)
				else if(p->bf==0)
					change=0;
				else;
				c_fx=1;
			}//end of if(change)
		/*--------------------------------------------------------end a--此间代码可看成一条语句-*/
		}//end of  else if(key>p->data)
		else                                                          //if (key==p->data)
		{
			printf("与该树中已有的接点重复");
			return;
		}//end of else end of if(p!=null)
	else															 //if(p==null)                                       
		if(p_fx==LEFT)												 //如果是父亲接点的左孩子
		{
			parent->lchild=(avlnode *)malloc(sizeof(avlnode));
			parent->lchild->data=key;
			parent->lchild->bf=0;
			parent->lchild->lchild=NULL;
			parent->lchild->rchild=NULL;
			change=1;
		}
		else														//如果是父亲接点的右孩子
		{
			parent->rchild=(avlnode *)malloc(sizeof(avlnode));
			parent->rchild->data=key;
			parent->rchild->bf=0;
			parent->rchild->lchild=NULL;
			parent->rchild->rchild=NULL;
			change=1;
		}
}//end of inster
void inorder(avlnode *p)												//中序遍历
{
	if(p!=NULL)
	{
		inorder(p->lchild);
		printf("%3d",p->data);
		//printf("bf=%d",p->bf);
		inorder(p->rchild);
	}
}
avlnode * creat_tree(avlnode *root,int a[],int n)
{
	avlnode *parent;												//定义一个根节点的父亲节点，因为insert需要一个父亲节点，如果不这样当根节点失衡时就会出错
	int i;
	int c_fx;
	int change;
	parent=(avlnode *)malloc(sizeof(avlnode));
	parent->bf=0;
	parent->data=0;
	parent->lchild=root;											//将父亲接点的左孩子指向跟接点，父亲接点相当与指针的指针
	parent->rchild=NULL;
	if(parent->lchild==NULL)										//如果当前是一棵空树
	{
		parent->lchild=(avlnode *)malloc(sizeof(avlnode));
		parent->lchild->bf=0;
		parent->lchild->data=a[0];
		parent->lchild->lchild=NULL;
		parent->lchild->rchild=NULL;
		if(n==1)													//如果只插入一个节点
			return(parent->lchild);
		else														//插如多个
		{
			for(i=1;i<n;i++)
				insert(parent->lchild,parent,a[i],0,c_fx,change);
			return(parent->lchild);
		}
	}
	else															//如果树不为空树
	{
		for(i=0;i<n;i++)
			insert(parent->lchild,parent,a[i],0,c_fx,change);
		return(parent->lchild);
	}
}
void main()
{
	int a[100];														 //将要插入的节点的DATA植放如次数组中
	//int a[10]={9,2,6,3,8,13,15,20,30,21};
	//int a[1]={1};
	avlnode *root;
	root=NULL;
	for(int i=0;i<100;i++)
		a[i]=i+1;
    root=creat_tree(root,a,100);									//创建树,第一个参数为树个跟节点，第2个为数组名，第3个数组大小
	printf("%d%4d\n",root->data,root->bf);                          //可输出任意节点的data和bf
	inorder(root);						                            //遍历生成的树	
}