main.cpp

C++ 模板方法实现树结构成员添加和去除 关键字 template tr

#include <cassert>
#include <iostream>


using namespace std;

template < class ET >
class BSTree;

template < class ET >
class Node;

template < class ET >
class BSTree{
	public:
		BSTree();
		~BSTree();
		
		 void insert ( const ET &newEntry );
		 void remove ( ET &newEntry );
		 bool find ( const ET &newEntry );
		 void writeKeys () const;
		 void clear ();
		 bool empty ();
		 void showTree () const;
	private:
		void removeRec (Node<ET> *&r,Node<ET> *r2,ET &newEntry);
		ET leftMax(Node<ET> *r);
		void insertRec ( Node<ET> *&root, const ET &newEntry );
		void clearRec(Node<ET> *p);
		void showRec(Node<ET> *p, int level ) const;
		void writeKeysRec (const Node<ET> *root) const;
		void error(const char *s){  
     	cout << s << endl;
      	exit(1);
   	} 
   	Node<ET> *root;
		 
};

template < class ET >
class Node{                								
friend class BSTree<ET>;
private:
    Node (const ET &elem,Node *leftPtr,Node *rightPtr);
   
    ET element;      			
    Node *left;
    Node *right;		
};
//159.201-S1 2006
//some member functions to help you solve the problem for Lab 4 
//*******************************************
//	creats the node for the tree
//****************************************************************
template <class ET>
Node<ET>::Node(const ET &elem,Node *leftPtr,Node *rightPtr){
	element = elem;
   left = leftPtr;
   right = rightPtr;
}



//	code form here down is for the BSTree Class
//****************************************************************
//	creaints an empty tree
//****************************************************************
template <class ET>
BSTree<ET>::BSTree(){
		root = NULL;
}

//****************************************************************
//	Destroys the tree and returns the memory
//****************************************************************
template <class ET>
BSTree<ET>::~BSTree (){
	clear();
}

//****************************************************************
//	clears the tree and returns the memory
//****************************************************************
template <class ET>
void BSTree<ET>::clear(){
	if(root == NULL) return;
	clearRec(root);
	root = NULL;
}

//****************************************************************
//		recursive partner to clear
//****************************************************************
template <class ET>
void BSTree<ET>::clearRec(Node<ET> *p){
	if(p->left != NULL ) clearRec(p->left); 
   if(p->right != NULL) clearRec(p->right);
   if(p != NULL) delete p;
}
// Outputs the keys in a binary search tree. The tree is output
// rotaintd counintrclockwise 90 degrees from its conventional
// orientation using a "reverse" inorder traversal. This operation is
// inintnded for intsting and debugging purposes only.

template < class ET >
void BSTree<ET>:: showTree () const{
    if ( root == NULL )
       cout << "Empty tree" << endl;
    else{
       cout << endl;
       showRec(root,1);
       cout << endl;
    }
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// Recursive partner of the showTree() function. Outputs the
// subtree whose root node is poinintd to by p. Parameintr level is the
// level of this node within the tree.
template < class ET >
void BSTree<ET>:: showRec(Node<ET> *p, int level ) const {
     int j;   // Loop counintr

     if ( p != 0 ) {
        showRec(p->right,level+1);         // Output right subtree
        for ( j = 0 ; j < level ; j++ )    // Tab over to level
            cout << "\t";
        cout << " " << p->element;   // Output key
        if ( ( p->left != NULL ) &&           // Output "connector"
             ( p->right != NULL ) )
           cout << "<";
        else if ( p->right != NULL )
           cout << "/";
        else if ( p->left != NULL )
           cout << "\\";
        cout << endl;
        showRec(p->left,level+1);          // Output left subtree
    }
}

template <class ET>
void BSTree<ET>::insert (const ET &newEntry ){
	insertRec(root,newEntry);
}

template <class ET>
void BSTree<ET>::insertRec (Node<ET> *&root,const ET &newEntry ){
	if(root==NULL){
		root=new Node<ET>(newEntry,NULL,NULL);
	}else if(root->element>newEntry){
		insertRec(root->left,newEntry);
	}else if(root->element<newEntry){
		insertRec(root->right,newEntry);
	}
}

template <class ET>
void BSTree<ET>::remove ( ET &newEntry ){
	Node<ET> *curren;
	curren=NULL;
	removeRec(root,curren,newEntry);
}

template <class ET>
void BSTree<ET>::removeRec (Node<ET> *&r,Node<ET> *c,ET &newEntry){
	if(r->element!=newEntry){
		if(r->element>newEntry){
			c=r;
			removeRec(r->left,c,newEntry);
		}else if(r->element<newEntry){
			c=r;
			removeRec(r->right,c,newEntry);
		}
	}else{
		//cout<<"parent node "<<c->element<<endl;
		if(r==root&&r->left==NULL&&r->right==NULL){
			delete c;
			r=NULL;
		}else	if(r->left==NULL&&r->right==NULL){
			if(c->left==r){
				c->left=NULL;
			}else{
				c->right=NULL;
			}
		}else	if(r->left!=NULL&&r->right!=NULL){
			r->element=leftMax(r->left);
			removeRec(r->left,r,r->element);
		}else	if(r->left!=NULL||r->right!=NULL){
			if(r->left==NULL){
				r=r->right;
			}else {
				r->element=leftMax(r->left);
				removeRec(r->left,r,r->element);
			}
		}
	}
}	


template <class ET>
ET BSTree<ET>::leftMax(Node<ET> *r){
	Node<ET>*p=r;
   if(p->right!=NULL){
	   p=p->right;
	   if(p->right==NULL){
		   return p->element;
		}else{
	   	leftMax(p);
	   }
	}else if(p->left!=NULL){
		leftMax(p->left);
	}else{
		return p->element;
	}
		   return p->element;	   
} 

template <class ET>
bool BSTree<ET>::find ( const ET &newEntry){
	Node<ET> *temp;
	temp=root;
	while(temp!=NULL){
		if (temp->element==newEntry){
			return true;
		}else if(temp->element>newEntry){
			temp=temp->left;
		}else if(temp->element<newEntry){
			temp=temp->right;
		}else{
			return false;
		}
	}return false;
}

template <class ET>
void BSTree<ET>::writeKeys () const{
	if(root!=NULL){
		writeKeysRec(root);
	}else{
		cout<<"no any keys in the tree"<<endl;
	}
}	

template <class ET>
void BSTree<ET>::writeKeysRec (const Node<ET> *root) const{
	if (root->left==NULL){
		cout<<root->element<<endl;
	}else{
		writeKeysRec (root->left);
		cout<<root->element<<endl;
		
	}
	if(root->right!=NULL){
			writeKeysRec(root->right);
		}
}	

template <class ET>
bool BSTree<ET>::empty(){
	if (root==NULL){
		return true;
	}else {
		return false;
	}
}			
		

//********************************************************************
//**********code to be used for demo for marking----------------------
//********************************************************************
void info();
void displayMenu();
void testTree();
int main(){
	 info();
	 displayMenu();
    testTree();
}

void info(){
	 cout<<"***************************"<<endl;
	 cout<<"     159.201 Lab 4"<<endl;
	 cout<<"Student Name: ZHAI Ziming"<<endl;
	 cout<<"Student ID  : 03320995	"<<endl;
	 cout<<"***************************"<<endl;
}
void displayMenu(){
	cout << endl << "Commands:" << endl;
    cout << "  +key : Insert (or update) element" << endl;
    cout << "  -key : Remove element" << endl;
    cout << "  K    : Write keys in ascending order" << endl;
    cout << "  C    : Clear the tree" << endl;
    cout << "  E    : Empty tree?" << endl;
    cout << "  Q    : Quit the program" << endl;
    cout << endl;
}

void testTree(){
	BSTree<int> testTree;   			// binary search tree for testing
    int inputData;                    // User input 
    char cmd;                        // Input command
    do {
        testTree.showTree();                     // Output tree

        cout << endl << "Command: ";                  // Read command
        cin >> cmd;
        if ( cmd == '+'  ||  cmd == '?'  ||
             cmd == '-'  ||  cmd == '<'    )
           cin >> inputData;

        switch ( cmd ){
          case '+' :                                  // insert
              
               cout << "Insert : key = " << inputData;
               testTree.insert(inputData);
               break;
         
          case '-' :                                  // remove
               
              if (testTree.find(inputData)) {
	              testTree.remove(inputData);
                  cout << "Removed element" << endl;
              }
               else{
                  cout << "Not found" << endl; 
               }
              break; 

          case 'K' : case 'k' :                       // writeKeys
               cout << "Keys:" << endl;
               testTree.writeKeys();
               break;

          case 'C' : case 'c' :                       // clear
               cout << "Clear the tree" << endl;
               testTree.clear();
               break;

          case 'E' : case 'e' :                       // empty
               if ( testTree.empty() )
                  cout << "Tree is empty" << endl;
               else
                  cout << "Tree is NOT empty" << endl;
               break;


          case 'Q' : case 'q' :                   // Quit intst program
               break;

          default :                               // Invalid command
               cout << "Inactive or invalid command" << endl;
        }
    }
    while ( ( cmd != 'Q' ) && ( cmd != 'q' ) );
}