binarytree.h

本程序是实现二叉树跟树的常用算法

			 if(*rpos==*ppos)

				 break;

			 k=rpos-ipos;

			 p->LeftChild=pre_and_in_creatbinary(ppos+1,ipos,k);

			 p->RightChild=pre_and_in_creatbinary(ppos+k+1,rpos+1,n-1-k);

			 root=p;
			 
			 return p;
}
template<typename T>void BinaryTree<T>::InThread(BinaryTreeNode<T> *t)
{
	BinaryTreeNode<T> *p=root,*temp=NULL;

	stack<BinaryTreeNode<T> *> s;

	while(1)
	{
		while(p!=NULL)
		{
			s.Push(p);

			p=p->LeftChild;
		}

        if(s.IsEmpty())

			break;
	
		p=s.GetTop();

		s.Pop();
		
		if(temp!=NULL)
		{
			if(temp->RightChild==NULL)
			{
				temp->RightChild=p;

				temp->rTag=1;
			}

		    if(p->LeftChild==NULL)
			{
				p->LeftChild=temp;

				p->lTag=1;
			}
		}

		temp=p;

		p=p->RightChild;
	
		}
}

template<typename T>void BinaryTree<T>::In_thread_Order(BinaryTreeNode<T> *t)
{
	BinaryTreeNode<T> *p=t;

	if(p==NULL)

		return;

	while(p->LeftChild!=NULL)

		p=p->LeftChild;

	while(1)
	{
		cout<<p->element<<'\t';

		if(p->RightChild==NULL)

			break;
		
		if(p->rTag==1)

			p=p->RightChild;

		else{

			p=p->RightChild;

			while(p->lTag==0)

				p=p->LeftChild;
		}
	}
}

template<typename T> BinaryTreeNode<T> *BinaryTree<T>::FindNextinInorderTree(BinaryTreeNode<T> *t,T data)
{
	BinaryTreeNode<T> *p=t,*temp=NULL;

	if(p==NULL)

		return NULL;

	while(p->LeftChild!=NULL)

		p=p->LeftChild;

	while(1)
	{
		if(p->element==data)

			break;

		if(p->RightChild==NULL)

			break;
		
		if(p->rTag==1)

			p=p->RightChild;

		else{

			p=p->RightChild;

			while(p->lTag==0)

				p=p->LeftChild;
		}
	}
   
    if(p->LeftChild!=NULL&&p->lTag==0)

		return p->LeftChild;

    if(p->rTag==0&&p->RightChild==NULL)
	{
		cout<<"找不到!"<<endl<<endl;

		return NULL;
	}

	
	else

		temp=p;

	while(temp->rTag==1)

		temp=temp->RightChild;

    temp=temp->RightChild;

	return temp;
}

template<typename T> BinaryTreeNode<T>* BinaryTree<T>::Is_PostOrder_first_Node(BinaryTreeNode<T> *t)
{

   stack<BinaryTreeNode<T>*> s;

	BinaryTreeNode<T> *p=t;

	int tag[255],top=-1;
	
	while(!s.IsEmpty()||p!=NULL)
	{
        while(p)
		{
			s.Push(p);
			
			tag[++top]=0;
			
			if(p->lTag==0)
			
			p=p->LeftChild;

			else p=NULL;

		}
	if(top>-1)

		if(tag[top]==1)
        
		return s.GetTop();
			
		
		else{

			p=s.GetTop();

			tag[top]=1;

			if(p->rTag==0)

			p=p->RightChild;

			else p=NULL;
		}
	}
}
		 
template<typename T> BinaryTreeNode<T> *BinaryTree<T>::FindBeforeinInorderTree(BinaryTreeNode<T> *t,T data)
{
 
	BinaryTreeNode<T> *p=t,*temp=NULL,*p1;

	if(p==NULL)

		return NULL;

	while(p->LeftChild!=NULL)
	
		p=p->LeftChild;

	while(1)
	{
		if(p->element==data)

			break;

		if(p->RightChild==NULL)

			break;
		
		if(p->rTag==1)

			p=p->RightChild;

		else{

			p=p->RightChild;

			while(p->lTag==0)

				p=p->LeftChild;
		}
	}

	p1=Is_PostOrder_first_Node(t);

	if(p1->element==p->element)

		return NULL;
   
    if(p->RightChild!=NULL&&p->rTag==0)
	{
		temp=p;

		temp=temp->RightChild;

		if(temp->LeftChild!=NULL&&temp->lTag==1)

			return temp;
	}

    else if(p->LeftChild!=NULL)
	{
        temp=p;

		temp=temp->LeftChild;
		
		if(temp->LeftChild==NULL)
		
		return p->LeftChild;

		else
		{
			temp=temp->LeftChild;
	
			return temp;
	
		}
	}
}

template<typename T> void BinaryTree<T>::Post_Thread_Order(BinaryTreeNode<T> *t)
{
    stack<BinaryTreeNode<T>*> s;

	BinaryTreeNode<T> *p=t;

	int tag[255],top=-1;
	
	while(!s.IsEmpty()||p!=NULL)
	{
        while(p)
		{
			s.Push(p);
			
			tag[++top]=0;
			
			if(p->lTag==0)
			
			p=p->LeftChild;

			else p=NULL;

		}
	if(top>-1)

		if(tag[top]==1)
        
		{
			cout<<s.GetTop()->element<<'\t';

			s.Pop();

			top--;
		}
		else{

			p=s.GetTop();

			tag[top]=1;

			if(p->rTag==0)

			p=p->RightChild;

			else p=NULL;
		}
	}
}

template<typename T> void BinaryTree<T>::Del_BinaryTreeNode(BinaryTreeNode<T> *t,T data)
{	
	BinaryTreeNode<T> *temp=NULL,*p=t,*parent=NULL;
 
	while(p->element!=data)
	{
		parent=p;

		if(p->element<data)

			p=p->RightChild;

		else
			p=p->LeftChild;
	}

	

	if(p->LeftChild==NULL)
	{
		if(parent==NULL)

			t=p->RightChild;

		else if(parent->LeftChild==p)

			parent->LeftChild=p->RightChild;

		else 
			parent->RightChild=p->RightChild;
	
	    delete p;

		p=NULL;

		return;
	}

	else 
	{
		temp=p->LeftChild;

	while(temp->RightChild!=NULL)

		temp=temp->RightChild;

	temp->RightChild=p->RightChild;

	if(parent==NULL)

		t=p->LeftChild;

	else if(parent->LeftChild==p)

		parent->LeftChild=p->LeftChild;

	else
		parent->RightChild=p->LeftChild;

    delete p;

	p=NULL;

	return;
	}
}

template<typename T>void BinaryTree<T>::Del_BinaryTreeNode_EX(BinaryTreeNode<T> *t,T data)
{
    BinaryTreeNode<T> *temp=NULL,*p=t,*parent=NULL,*tempparent=NULL;
 
	while(p->element!=data)
	{
		parent=p;

		if(p->element<data)

			p=p->RightChild;

		else
			p=p->LeftChild;
	}

	if(p->LeftChild==NULL)
	{
		if(parent==NULL)

			t=p->RightChild;

		else if(parent->LeftChild==p)

			parent->LeftChild=p->RightChild;

		else 
			parent->RightChild=p->RightChild;
	
	    delete p;

		p=NULL;

		return;
	}

	else{
		temp=p->LeftChild;

		while(temp->RightChild!=NULL)
		{
			tempparent=temp;

			temp=temp->RightChild;
		}

		if(tempparent==NULL)

			p->LeftChild=temp->LeftChild;

		else 
			tempparent->RightChild=temp->RightChild;

		if(parent==NULL)

			t=temp;

		else if(parent->LeftChild==p)

			parent->LeftChild=temp;

		else 
			parent->RightChild=temp;

		temp->LeftChild=p->LeftChild;

		temp->RightChild=p->RightChild;

		delete p;

		p=NULL;
	}
}

template<typename T>void BinaryTree<T>::InsertNode_in_Inthread(BinaryTreeNode<T> *t,T find_data,T insert_data)
{                                                    //在中序周游中插入的结点在指定结点后面
   BinaryTreeNode<T> *p=t,*temp=NULL,*newNode;

	if(p==NULL)

		return ;

	while(p->LeftChild!=NULL)

		p=p->LeftChild;

	while(1)
	{
		if(p->element==find_data)

			break;

		if(p->RightChild==NULL)

			break;
		
		if(p->rTag==1)

			p=p->RightChild;

		else{

			p=p->RightChild;

			while(p->lTag==0)

				p=p->LeftChild;
		}
	}
	   
    newNode=new BinaryTreeNode<T>(insert_data);

	if(p->RightChild==NULL)

		temp=NULL;

	else if(p->rTag==1)

		temp=p->RightChild;

	else{
		temp=p->RightChild;

		while(temp->lTag==0)

        temp=temp->LeftChild;
	}

	if(temp!=NULL && temp->lTag==1)

		temp->LeftChild=newNode;

	newNode->rTag=p->rTag;

	newNode->RightChild=p->RightChild;

	p->rTag=0;

	p->RightChild=newNode;

	newNode->lTag=1;

	newNode->LeftChild=p;
}

template<typename T>void BinaryTree<T>::Ancestor(BinaryTreeNode<T> *t,T data)
{
	BinaryTreeNode<T> *p=t;

	stack<BinaryTreeNode<T> *> s,s1;

	int tag[100],top=-1,flag=0;

	while(p!=NULL||!s.IsEmpty())
	{
		while(p!=NULL)
		{
			s.Push(p);

			if(p->element!=data)

				s1.Push(p);

			else 
			{
				flag=1;

				break;
			}

			tag[++top]=0;

			p=p->LeftChild;
		}
         
        if(flag==1)

           break;

		if(tag[top]>-1)

			if(tag[top]==1)
			{	
				s.Pop();

				top--;

				s1.Pop();
			}

			else{

				p=s.GetTop();

				if(p->element==data)

					break;

				tag[top]=1;

				p=p->RightChild;
			}
	}

	cout<<endl;

	cout<<"输出祖先结点:"<<endl<<endl;
	
	while(!s1.IsEmpty())
	{
		cout<<s1.GetTop()->element<<"\t";

		s1.Pop();
	}
}

template<typename T>void BinaryTree<T>::Closed_Ancestor(BinaryTreeNode<T> *t,T data1,T data2)
{
    BinaryTreeNode<T> *p=t;

	stack<BinaryTreeNode<T> *> s,s1,s2;

	int tag[100],top=-1,flag1=0,flag2=0;

	while(p!=NULL||!s.IsEmpty())
	{
		while(p!=NULL)
		{
			s.Push(p);

			if(p->element!=data1 && flag1==0)

				s1.Push(p);

			else 
				
				flag1=1;

			if(p->element!=data2 && flag2==0)

				s2.Push(p);

			else 

				flag2=1;

			if(flag1==1 && flag2==1)

				break;

			tag[++top]=0;

			p=p->LeftChild;
		}
         
        if(flag1==1 && flag2==1)

           break;

		if(tag[top]>-1)

			if(tag[top]==1)
			{	
				s.Pop();

				top--;

				if(flag1!=1)

				s1.Pop();

				s2.Pop();
			}

			else{

				p=s.GetTop();

				if(flag2==1 && flag2==1)

					break;

				tag[top]=1;

				p=p->RightChild;
			}
	}
	
    T ancesstor1[100];

	T ancesstor2[100];

	int i=0,j=0;

	if(s1.IsEmpty())
	{
		cout<<"两个结点不可以找出最近共同祖先!"<<endl;

		return;
	}
	
	while(!s1.IsEmpty())

		ancesstor1[i++]=s1.Pop()->element;

	while(!s2.IsEmpty())

		ancesstor2[j++]=s2.Pop()->element;
	
	int top1=0,top2=0,flag=0;

	cout<<endl;

	for(top1=0;top1<i;top1++)
	{
		for(top2=0;top2<j;top2++)

			if(ancesstor1[top1]==ancesstor2[top2])
			{
				flag=1;

				break;
			}

			if(flag==1)

				break;
	}

	cout<<"这两个指定结点的最近的祖先是:"<<ancesstor1[top1]<<endl<<endl;

	
	cout<<"这两个结点的距离是:"<<i+j<<endl<<endl;

}

template<typename T>void BinaryTree<T>::PreOrder_Ex(BinaryTreeNode<T> *t)
{
	stack<BinaryTreeNode<T> *> s;

	BinaryTreeNode<T> *p=t;

	s.Push(NULL); //这个是周游结束标志，当周游到最后一个结点的时候发挥作用

	while(p!=NULL)
	{
		cout<<p->element<<"\t";

		if(p->RightChild!=NULL)

			s.Push(p->RightChild);

		if(p->LeftChild!=NULL)

			p=p->LeftChild;

		else
		    
			p=s.Pop();						
	}
}