bst.h

学生毕业设计管理系统和图的有关操作

#include <iostream.h>
//#include "bs.h"
#include <stdlib.h>
#define N 10
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 ( const Type d=0,BstNode *L = NULL,BstNode *R = NULL):data(d),leftChild (L),
 //       rightChild (R) { };
    ~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> *FindType (const Type & x,BstNode<Type>* ptr)const;//搜索
	BstNode<Type> *Min ( BstNode<Type> * ptr )const;  //求最小
    BstNode<Type> *Max ( BstNode<Type> * ptr )const;//求最大    
//	friend class BSTIterator <Type>;   //中序游标类
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是
		//输入结束标志
//		Type x;
		root = NULL;
//		RefValue = -1;
		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>
BST <Type> :: BST (Type value)
{
//输入数据，建立二叉搜索树的算法, RefValue是
//输入结束标志
    Type x;  
    root = NULL;  RefValue = value;
    cin >> x;
    while ( x!= RefValue )
	{
		Insert ( x, root ); 
		cin >> x;
	}
}
*/
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> 
BstNode <Type> * BST <Type> :: Find 
    (const Type & x,  BstNode<Type> * ptr ) const {
//二叉搜索树的迭代的搜索算法
    if ( ptr != NULL ) {				
        BstNode<Type> * temp = ptr;
        while ( temp != NULL ) {		
	    if ( temp->data == x ) return temp;	  //成功
	    if ( temp->data < x ) 
                 temp = temp->rightChild;    //右子树
             else temp = temp->leftChild;   //左子树
        }
    }
    return NULL;             //搜索失败
}*/
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> class InorderIterator {	    public:
    InorderIterator ( BST<Type> & Tree ) : 
                                          ref (Tree) { Init ( ); }
    int Init ( );                      //迭代栈初始化
    int operator ! ( );          //判迭代栈空否
    Type operator ( ) ( );    //取栈顶元素关键码
    int operator ++ ( );       //按前序序列进栈,遍历private:
    BST<Type> & ref;        //二叉搜索树对象
    Stack < BstNode<Type> * > itrStack;    //迭代栈
}
template <class Type> 
int InorderIterator<Type> :: Init ( ) {
   itrStack.MakeEmpty ( );	          //迭代栈置空
   if ( ref.root != NULL )                //树非空,根进栈
      itrStack.Push ( ref.root );	 
      return ! itrStack.IsEmpty ( );  //栈空返回0
}

template <class Type> 
int InorderIterator<Type> :: operator ! ( ) {
    return ! itrStack.IsEmpty ( );    //栈空返回0
}

template <class Type> 
int InorderIterator<Type> :: operator ++ ( ) {
    BstNode<Type> * current = itrStack.GetTop ( );
    BstNode<Type> * next = current→leftChild;
    if ( next != NULL )           //栈顶元素左子女进栈
        { itrStack.Push ( next );  return 1; }		
    while ( ! itrStack.IsEmpty ( ) ) {   //栈非空时循环
         current = itrStack.Pop ( );  
         next = current→rightChild;		
         if ( next != NULL )                      //右子女非空
            { itrStack.Push ( next );  return 1; }	 //进栈
    }
    return 0;
}
template <class Type> 
Type InorderIterator<Type> :: operator ( ) ( ) {
    BstNode<Type> * current = itrStack.GetTop ( );
    return current→data;         //返回栈顶元素值
}

template <class Type> BST<Type> ::
BST (const BST<Type> & T) : root (NULL) {
    InorderIterator<Type> itr ( );
    for ( itr.init ( ); ! itr; itr++ ) Insert ( itr ( ) );
}*/

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