avltree.cpp

平衡二叉树的建立,增加,删除,有问题还可以请联系我,联系方式在程序中.

//*******三月四号写于上海交通大学*****,有指教之处请联系[e-mail],本人不承诺都能予以回复//
#include "avltreenode.h"
#include "avltree.h"
#include <vector>
#include <math.h>

#define LEFT 0
#define RIGHT 1

template<typename X>
void avlTree<X>::insert(X value)
{
	avlTreeNode<X> *p=new avlTreeNode<X>,*child;
	p->data=value;
	vector<bool> tracer;
	if(!head)
	{
		head=p;
		return;
	}
	child=head;
	while(child)
	{
		cursor=child;
		if(value<=cursor->data)
		{
			child=cursor->lchild;
			tracer.push_back(LEFT);
		}
		else
		{
			child=cursor->rchild;
			tracer.push_back(RIGHT);
		}
	}
	int count=tracer.size();
	p->father=cursor;
	if(tracer[count-1]==LEFT)
	{
		cursor->lchild=p;
	}
	else
	{
		cursor->rchild=p;
	}
	countDifference(head);
	int reverseCount=0;
	for(cursor=p->father;cursor&&cursor->difference<2&&cursor->difference>-2;cursor=cursor->father)
	{
		reverseCount++;
	}
	if(!cursor)
		return;
	int position=count-reverseCount-1;
	bool frontFlag,backFlag;
	frontFlag=tracer[position];
	backFlag=tracer[position+1];
	if(frontFlag==LEFT&&backFlag==LEFT)
	{
		turnRight(cursor);
	}
	if(frontFlag==RIGHT&&backFlag==RIGHT)
	{
		turnLeft(cursor);
	}
	if(frontFlag==LEFT&&backFlag==RIGHT)
	{
		turnLeft(cursor->lchild);
		turnRight(cursor);
	}
	if(frontFlag==RIGHT&&backFlag==LEFT)
	{
		turnRight(cursor->rchild);
		turnLeft(cursor);
	}
	countDifference(head);
}

template<typename X>
int avlTree<X>::countDifference(avlTreeNode<X> *treehead)
{
	if(!treehead)
		return 0;
	int lHeight,rHeight,treeHeight;
	lHeight=countDifference(treehead->lchild);
	rHeight=countDifference(treehead->rchild);
	treehead->difference=lHeight-rHeight;
	treeHeight=lHeight>=rHeight?(1+lHeight):(1+rHeight);
	return treeHeight;
}

template<typename X>
void avlTree<X>::printDifference(avlTreeNode<X> *treehead)
{
	if(!treehead)
		return;
	cout<<"The difference is :"<<treehead->difference<<endl;
	printDifference(treehead->lchild);
	printDifference(treehead->rchild);
}

template<typename X>
void avlTree<X>::turnRight(avlTreeNode<X> *treehead)
{
	avlTreeNode<X> *temp=treehead->lchild;
	if(!treehead->father)
	{
		head=temp;
	}
	else
	{
		if(treehead==treehead->father->lchild)
			treehead->father->lchild=temp;
		else
			treehead->father->rchild=temp;
	}
	temp->father=treehead->father;
	treehead->lchild=temp->rchild;
	if(temp->rchild)
	{
		temp->rchild->father=treehead;
	}
	temp->rchild=treehead;
	treehead->father=temp;
}

template<typename X>
void avlTree<X>::turnLeft(avlTreeNode<X> *treehead)
{
	avlTreeNode<X> *temp=treehead->rchild;
	if(!treehead->father)
	{
		head=temp;
	}
	else
	{
		if(treehead==treehead->father->lchild)
			treehead->father->lchild=temp;
		else
			treehead->father->rchild=temp;
	}
	temp->father=treehead->father;
	treehead->rchild=temp->lchild;
	if(temp->lchild)
	{
		temp->lchild->father=treehead;
	}
	temp->lchild=treehead;
	treehead->father=temp;
}

template<typename X>
void avlTree<X>::traverse(avlTreeNode<X> *treehead)
{
	if(!treehead)
		return;
	if(treehead->father)
		cout<<"The father of "<<treehead->data<<" is :"<<treehead->father->data<<endl;
	else
		cout<<"The node of "<<treehead->data<<"is :"<<"head node"<<endl;
	traverse(treehead->lchild);
	traverse(treehead->rchild);
}

template<typename X>
void avlTree<X>::del(X value)
{
	if(!head)
		return;
	avlTreeNode<X> *p,*q,*r;
	p=head;
	q=0;
	while(p&&p->data!=value)
	{
		q=p;
		if(p->data>value)
		{
			p=p->lchild;
		}
		else
		{
			p=p->rchild;
		}
	}
	if(!p)
		return;
	//此节点是叶子节点
	if(!p->lchild&&!p->rchild)
	{
		if(p->father)
		{
			if(p->father->lchild==p)
			{
				p->father->lchild=0;
			}
			else
			{
				p->father->rchild=0;
			}
		}
		else
		{
			head=0;
		}
		delete(p);
	}
	else
	{
		//此节点同时有左右节点
		if(p->lchild&&p->rchild)
		{
			q=p->lchild;
			while(q->rchild)
			{
				q=q->rchild;
			}
			p->data=q->data;
			r=q->father;
			if(r->lchild==q)
				r->lchild=q->lchild;
			else
				r->rchild=q->lchild;
			if(q->lchild)
				q->lchild->father=r;
			delete(q);
			countDifference(head);
			adjust(p->lchild);
		}
		//只有左节点和右节点中的一个
		else
		{				
			if(p->lchild)
				r=p->lchild;
			else
				r=p->rchild;
			if(p==head)
			{
				head=r;
				r->father=0;
			}
			else
			{
				if(p->father->lchild==p)
					p->father->lchild=r;
				else
					p->father->rchild=r;
				r->father=p->father;
				delete(p);
			}
		}
	}
	countDifference(head);
	adjust(head);
}

//假设只需调整一处
template<typename X>
void avlTree<X>::adjust(avlTreeNode<X> *treehead)
{
	avlTreeNode<X> *theFirstInBalance=findTheFirstInBalance(treehead);
	avlTreeNode<X> *p,*q;
	if(!theFirstInBalance)
	{
		return;
	}
	if(theFirstInBalance->difference>0)
		p=theFirstInBalance->lchild;
	else
		p=theFirstInBalance->rchild;
	while(abs(p->difference)==2)
	{
		if(p->difference>0)
			p=p->lchild;
		else
			p=p->rchild;
	}
	bool direction1,direction2;
	if(p->father->difference==2)
		direction1=LEFT;
	if(p->father->difference==-2)
		direction1=RIGHT;
	if(p->difference==1)
		direction2=LEFT;
	if(p->difference==-1)
		direction2=RIGHT;
	if(direction1==LEFT&&direction2==LEFT)
	{
		turnRight(p->father);
	}
	if(direction1==RIGHT&&direction2==RIGHT)
	{
		turnLeft(p->father);
	}
	q=p->father;
	if(direction1=LEFT&&direction2==RIGHT)
	{
		turnLeft(p);
		turnRight(q);
	}
	if(direction1==RIGHT&&direction2==LEFT)
	{
		turnRight(p);
		turnLeft(q);
	}
	countDifference(head);
}

template<typename X>
avlTreeNode<X>* avlTree<X>::findTheFirstInBalance(avlTreeNode<X> *treehead)
{
	if(!treehead)
		return 0;
	if(abs(treehead->difference)==2)
		return treehead;
	avlTreeNode<X> *p;
	p=findTheFirstInBalance(treehead->lchild);
	if(p)
		return p;
	else
	{
		p=findTheFirstInBalance(treehead->rchild);
		if(p)
			return p;
	}
	return 0;
}