bintree.cpp

搜索二叉树的实现

#include < iostream.h >
#include < fstream.h >
#include < iomanip.h >
#include < stdlib.h >
#include "C_Queue.h"
#include "BinTree.h" //BinaryTree成员函数定义
template<class Type> void BinaryTree < Type >::destroy( BinaryTreeNode < Type > *current )
{//私有函数：若current不空，则删除根为current 的子树
	if(current!=NULL)
	{
		destroy(current->leftchild);
		destroy(current->rightchild);
        delete current;
	}
}

template<class Type> BinaryTreeNode < Type > *BinaryTree<Type>::Parent( BinaryTreeNode < Type > *start , BinaryTreeNode < Type > *current )
{//私有函数：从start 开始，搜索current的双亲结点。若找到，则函数返回双亲结点的地址，否则返回NULL
     if( start == NULL ) return NULL;
	 if( start -> leftchild == current || start -> rightchild == current ) return start;
	 BinaryTreeNode < Type > *p;
	 if( ( p = Parent ( start -> leftchild , current ) ) != NULL )   return P;
	 else return Parent ( start -> rightchild , current );
}

template < class Type > void BinaryTree< Type > :: Traverse1( const  BinaryTreeNode < Type > *current ) const
{//前序遍历
	if(current!=NULL&&current->data!=RefValue)//相应的改变
	{
		cout<<current->data<<" ";
        Traverse1(current->leftchild);
		Traverse1(current->rightchild);
	}
}

template<class Type> void BinaryTree<Type>::Traverse1(BinaryTreeNode<Type>*current,ostream&out) const
{//前序遍历
	if(current!=NULL&&current->data!=RefValue)//相应的改变
	{
		out<<current->data<<" ";
        Traverse1(current->leftchild,out);
		Traverse1(current->rightchild,out);
	}
}

template<class Type> void BinaryTree<Type>::Traverse2( const BinaryTreeNode<Type>*current) const
{//中序遍历
	if(current!=NULL&&current->data!=RefValue)//相应的改变
	{
        Traverse1(current->leftchild);
		cout<<current->data<<" ";
		Traverse1(current->rightchild);
	}
}

template<class Type> void BinaryTree < Type >::Traverse2( BinaryTreeNode < Type > *current, ostream &out) const
{//中序遍历
	if(current!=NULL&&current->data!=RefValue)//相应的改变
	{
        Traverse2(current->leftchild,out);
		out<<current->data<<" ";
		Traverse2(current->rightchild,out);
	}
}


template <class Type> istream & operator >>(istream & in, BinaryTree <Type> &Tree ) 
{//输入重载	
	Type item;
	in>>item;
	while (item !=Tree.RefValue)
	{
		Tree.Insert(item);
		in>>item;
	}
	return in;
}

template <class Type> ostream & operator << ( ostream & out, BinaryTree<Type> &Tree )
{
//	out<<"前序遍历 ：";
	Tree.Traverse1(Tree.root,out);
	out<<0<<" \n";
//	out<<"中序遍历 ：";
	Tree.Traverse2(Tree.root,out);
	out<<0<<" \n";
    return out;
}

template<class Type> void BinaryTree<Type>:: Insert ( const Type&item,BinaryTreeNode<Type> * & current)
{//私有函数：在以current为根的二叉树中插入所含值为item 的结点。若树中已经有含item的结点则不插入
	if(current==NULL)
	{
		current=new BinaryTreeNode <Type>(item);
		if(current==NULL) {cerr<<"out of space /n";exit(1);}
	}
	else if(item<current->data)Insert(item,current->leftchild);//小于根的关键码，向左子树上插
	else if(item>current->data)Insert(item,current->rightchild);//大于根的关键码，向右子树上插
}

template<class Type> void BinaryTree<Type>:: Insert1 ( const Type&item,BinaryTreeNode<Type> * & current)
{//私有函数：在以current为根的二叉树中插入所含值为item 的结点。若树中已经有含item的结点则不插入
	if(current==NULL)
	{
		current=new BinaryTreeNode <Type>(item);
		if(current==NULL) {cerr<<"out of space /n";exit(1);}
	}
	else current ->data = item;
}

template<class Type> void BinaryTree<Type>::Remove(const Type&item,BinaryTreeNode<Type> * & current)
{
    BinaryTreeNode<Type>* temp;
	if(current!=NULL)
		if(item<current->data)Remove(item,current->leftchild);//在左子树上删除
		else if(item>current->data)Remove(item,current->rightchild);//在右子树上删除
		else if(current->leftchild!=NULL&&current->rightchild!=NULL)
		{//若有两个子女
			temp=Min(current->rightchild);//在其右子树上找最小结点
			current->data=temp->data;//用该结点的数据代替根结点的数据
			Remove(current->data,temp);//在右子树上删除该结点
		}
		else //只有一个子女
		{
			temp=current;
			if( current->leftchild==NULL )current=current->rightchild;
			else  if( current->rightchild==NULL ) current = current -> leftchild;
			temp -> SetData( RefValue );
		}
}

template<class Type> BinaryTreeNode<Type>*BinaryTree<Type>::Min(BinaryTreeNode<Type>* current)const//在其右子树上找最小结点
{
	while(current!=NULL&&current->leftchild!=NULL) {current=current->leftchild;}//鉴于所建的树自身的特点，其右子树上最小结点在其左子树的左子树上，直至左叶结点处
	return current;
}

/******************************************************************************************************************************************************/

template < class Type > void BinaryTree< Type > :: Print( const  BinaryTreeNode < Type > *current ,int &i  ) const
{//凹入表输出
	int j = i;
	if( current !=NULL && current -> data != RefValue )//相应的改变
	{
		cout <<setw( i+3 )<< current->data <<" \n";
        Print(current->leftchild , j+=3 );
		Print(current->rightchild , i+=3  );
	}
}

template <class Type> int equal ( BinaryTreeNode < Type > * a , BinaryTreeNode < Type > *b)
{//具体判断函数
	if ( a == NULL && b == NULL ) return 1;
	if ( a != NULL && b != NULL && a->data == b->data 
		&& equal ( a->leftchild, b->leftchild )
		&& equal ( a->rightchild, b->rightchild )) return 1;
	return 0;
}

template <class Type> bool operator ==( BinaryTree<Type> &ta ,BinaryTree<Type> &tb )
{//判断两棵树是否相等
    if ( equal( ta.root ,tb.root ) ) return true;
	else return false;
}

template<class Type> void BinaryTree<Type>::LevelOrder(  BinaryTreeNode < Type > *current ) const
{//层次输出
	Queue < BinaryTreeNode < Type > * > Qu ( 30 );
   	BinaryTreeNode < Type > *p;
	if ( current != NULL )
	{//不空
		p = current ;Qu.EnQueue ( current );//入队
		while ( !Qu.IsEmpty() )
		{//队不空
			current = Qu.DeQueue( ); cout <<current->data<<" ";//节点出队，访问节点数据
			
			if ( current->leftchild !=NULL ) { Qu.EnQueue( current->leftchild ) ;   }//左孩子不空，入队
			if ( current->rightchild !=NULL) { Qu.EnQueue( current->rightchild ) ;   }//右孩子不空，入队
		}
	}
	current=p;
}

template<class Type> int BinaryTree<Type>:: Size(const BinaryTreeNode<Type> * t)const
{//计算t为根的二叉树结点的个数
	if(t==NULL)return 0;
	else return 1+Size(t->leftchild)+Size(t->rightchild);
}

void PartionAndInsert( int *PreA , Da *IoA ,int  startp ,int starti ,int  end , BinaryTreeNode < int > * &current,BinaryTree < int > &tr )
{// 分子树并将对应的节点插入新树
	int j = startp;
	for ( int i = 0 ;i <= end ;i++ )
		if ( PreA[j] == IoA[i].data )
		{//前序遍历第一个节点是子树的根，在中序中的位置，左边是它的左子树，右边是它的右子树。
			if ( IoA[i].active != 1) 
			{
				tr.Insert1(  IoA[i].data,current);
				IoA[i].llen=i-starti;IoA[i].active = 1;
				if ( IoA[end].active == 1 )IoA[i].rlen=end-i-1;
				else IoA[i].rlen=end-i;
				if (  IoA[i].llen == 1 && IoA[i-1].active != 1) { IoA[i-1].active=1;	current ->leftchild = new BinaryTreeNode < int > ;tr.Insert1( IoA[i-1].data,current->leftchild);}//左子树仅有一个节点则插入根左孩子节点
				else PartionAndInsert( PreA , IoA ,++startp,starti, i , current->leftchild,tr );//否则构造左子树
				if (  IoA[i].rlen == 1 && IoA[i+1].active != 1 ){ IoA[i+1].active=1; current->rightchild = new BinaryTreeNode< int >;tr.Insert1( IoA[i+1].data,current->rightchild);}////右子树仅有一个节点则插入根右孩子节点
				else PartionAndInsert( PreA , IoA ,++i ,i, end, current->rightchild,tr );//开始位置后置1（i++），否则构造右子树
			}
			else  { j++;i =0;}
		}		
}

void ReConstruct ( BinaryTree < int >  &tr)
{
    const int arrysize  =  tr.Size( tr.GetRoot() );//树的结点个数
	int arsze = arrysize-1;
	int *PreA = new int [arrysize];//存储前序遍历结果
	Da *IoA = new Da [arrysize];//存储中序遍历结果
	ifstream fin;
    fin.open("datafile.txt",ios::nocreate);
	if ( !fin ) { cerr<<"The datafile cannot be opened!\n";exit(1);}
    for ( int i = 0; i < arrysize ; i++  ){fin >>PreA[i]; }//读入前序遍历结果
	fin.ignore(2,'0');cout<<endl;
	for ( i = 0; i<arrysize; i++ ){fin>>IoA[i].data;IoA[i].active = 0;}//读入中序遍历结果
	fin.close();
	int start = 0;
	BinaryTree < int > newtree (0) ;//构造新树newtree
	PartionAndInsert( PreA , IoA , start , start ,arsze, newtree.root,newtree );//分子树，并插入节点。
	cout<<"\n\n\n   >********************************************<\n  newtree凹入表输出：\n";
    i = 0 ;
    newtree.Print (newtree.GetRoot() , i );//凹入表输出
	cout<<"\n\n   newtree前序遍历 ：";
	newtree.Traverse1(newtree.GetRoot());
	cout<<"\n   newtree层次遍历 ：";
    newtree.LevelOrder( newtree.GetRoot() );//层次输出
	cout<<endl;
	if ( tr == newtree ) cout << "\n   newtree and tree   Equal! \nSuccessful! Reconstruct a BinaryTree  \n ";//判断两棵树相等证明还原出原来的树
	else cout << "\n   newtree and tree   Not Equal ! \n ";
	
}