bts.h

数据结构实验课中的所有实验程序

#include <iostream.h>
#include <stdlib.h>
#define N 100
template <class Type> class BST;
template <class Type> class BstNode {      //二叉搜索树结点类
friend class BST <Type>;
public:
    BstNode( ):leftChild (NULL), rightChild (NULL) { };
    BstNode (const Type d) : data (d),leftChild (NULL),rightChild (NULL){ };
    ~BstNode ( ) { } ;
protected:
     Type data;					     
     BstNode<Type> *leftChild, *rightChild; 
};

template <class Type> class BST{
private:							
    BstNode<Type> *root;  //二叉搜索树的根指针
    Type RefValue;	        //数据输入停止的标志
    BstNode<Type> *lastfound;//最近搜索到的结点的指针
    void MakeEmpty ( BstNode<Type> *& ptr );    
	void Insert ( const Type & x,BstNode<Type> *& ptr );//插入
    void Remove ( const Type & x,BstNode<Type> *& ptr );//删除    
    void PrintTree ( BstNode<Type> *ptr ) const;
    BstNode<Type> *Copy(const BstNode<Type> *ptr ); //复制
    BstNode<Type> *Find (const Type & x,BstNode<Type>* ptr)const;//搜索
	BstNode<Type> *Min ( BstNode<Type> * ptr )const;  //求最小
    BstNode<Type> *Max ( BstNode<Type> * ptr )const;//求最大    

public:
    BST ( ) : root (NULL) { };		
    BST (Type value)
	{
		//输入数据，建立二叉搜索树的算法, RefValue是
		//输入结束标志
		Type x;
		root = NULL;
		RefValue = value;
		cin >> x;
		while ( x!= RefValue )
		{
			Insert ( x, root );
			cin >> x;
		}
	}
	BST (Type value[])
	{
		//输入数据，建立二叉搜索树的算法, RefValue是
		//输入结束标志

		root = NULL;
		for(int i=0;i<N;i++)
		{
			Insert(value[i],root);
		}
	}

    ~BST ( );	
    const BST & operator = ( const BST & Value );
    void MakeEmpty ( ){ MakeEmpty (root);  root = NULL; }
    void PrintTree ( ) const { PrintTree ( root ); }
    int Find ( const Type & x )const { return Find ( x, root ) != NULL; }
	Type FindType ( const Type & x  )const { return Find ( x, root )->data;}
	Type Min ( ) { return Min ( root )->data; }
    Type Max ( ) { return Max ( root )->data };
    void Insert ( const Type & x ){ Insert ( x, root ); }
    void Remove ( const Type & x ){ Remove ( x, root ); }		     
};
////////// /////////////////


template <class Type>
BstNode<Type> * BST<Type>::Min ( BstNode<Type> * ptr )const//求最小
{
	if ( ptr == NULL )
		return NULL;//搜索失败
	else if ( ptr->leftChild!=NULL) //是否有左子树
		return Min (ptr->leftChild );
	else return ptr;	    //相等,搜索成功	
}

template <class Type>BstNode<Type> * BST<Type>::Find
(const Type &x, BstNode<Type>* ptr)const
{
//二叉搜索树的递归的搜索算法
    if ( ptr == NULL )
		return NULL;//搜索失败
	else if ( x < ptr->data ) //在左子树递归搜索
		return Find ( x, ptr->leftChild );
	else if ( x > ptr->data ) //在右子树递归搜索
		return Find ( x, ptr->rightChild );
	else 
	return ptr;//相等,搜索成功		
}

/////////////

template <class Type> void BST<Type>::
Insert (const Type & x, BstNode<Type> * & ptr) {
//递归的二叉搜索树插入算法
       if ( ptr == NULL ) //空二叉树
	   { 
		   ptr = new BstNode<Type> (x); //创建含 x 结点
		   if ( ptr == NULL )
		   {
			   cout << "Out of space" << endl;
			   exit (1);
		   }
	   }
	   else if ( x < ptr->data )    //在左子树插入
		   Insert ( x, ptr->leftChild );
	   else if ( x > ptr->data )   //在右子树插入
		   Insert ( x, ptr->rightChild );
}

template <class Type> void BST<Type> ::
Remove (const Type &x, BstNode<Type> * &ptr) {
    BstNode<Type> * temp;
    if ( ptr != NULL )
       if ( x < ptr->data )
		   Remove ( x, ptr->leftChild ); 
       else if ( x > ptr->data ) 
                  Remove ( x, ptr->rightChild );
	   else if ( ptr->leftChild != NULL &&ptr->rightChild != NULL )
	   {
		   temp = Min ( ptr->rightChild );
		   ptr->data = temp->data;
		   Remove ( ptr->data, temp );
	   }
	   else
	   {
		   temp = ptr;
		   if ( ptr->leftChild == NULL )
			   ptr = ptr->rightChild;
		   else if ( ptr->rightChild == NULL )
			   ptr = ptr->leftChild;
		   delete temp;
	   }
} 


template <class Type> BST<Type> :: ~BST ( ){
   // MakeEmpty ( );               //二叉搜索树析构函数
}