// Justin C. Miller
// made on : 11-29-2001
// made for: http://www.geocities.com/neonprimetime.geo/index.html

// Binary Tree

#include 

using namespace std ;

// a node that holds an integer
// and has a left and right child pointer
struct node{
	node(){left=NULL ; right=NULL;}
	int data ;
	node * left ;
	node * right ;
};

// the actual binary search tree
class binaryTree{
private:
	node * root ; // the root
	void preHelper(node*)const ; // preOrder traversal helper
	void inHelper(node*)const ; // inOrder traversal helper
	void postHelper(node*)const ; // postOrder traversal helper
	void destructor(node * n) ;  // destructor's helper
public:
	binaryTree(void){ root = NULL ; }  // constructor
	~binaryTree(void){destructor(root);} // desctructor
	bool insert(const int) ; // insert integer into tree
	bool remove(const int) ; // remove integer from tree
	bool search(const int) const ; // is it in the tree?
	void preOrder(void)const{preHelper(root) ; cout << endl ;}
	void inOrder(void)const{inHelper(root) ; cout << endl ;}
	void postOrder(void)const{postHelper(root) ; cout << endl ;}
};

void binaryTree::destructor(node * n){
	if(n!=NULL){
		destructor(n->left) ;
		destructor(n->right) ;
		delete n ;
	}
}

void binaryTree::preHelper(node * n)const{
	if(n!=NULL){
		cout << n->data << " " ;
		preHelper(n->left) ;
		preHelper(n->right) ;
	}
}

void binaryTree::inHelper(node * n)const{
	if(n!=NULL){
		inHelper(n->left) ;
		cout << n->data << " " ;
		inHelper(n->right) ;
	}
}

void binaryTree::postHelper(node * n)const{
	if(n!=NULL){
		postHelper(n->left) ;
		postHelper(n->right) ;
		cout << n->data << " " ;
	}
}

bool binaryTree::insert(const int newNumber){
	node * newNode = new node ;
	newNode->data = newNumber ;

	if(root == NULL){
		root = newNode ;
		return true;
	}

	node * current = root ;
	node * parent = NULL ;
	while(current != NULL && current->data != newNumber){
		parent = current ;
		if(newNumber < current->data)
			current = current->left ;
		else
			current = current->right ;
	}
	if(current != NULL && current->data == newNumber)
		return false ;
	if(newNumber < parent->data)
		parent->left = newNode ;
	else
		parent->right = newNode ;
	return true ;
}

bool binaryTree::remove(const int badNumber){
	if(root!=NULL && root->data == badNumber){
		// root is only node
		if(root->left == NULL && root->right == NULL){
			node * temp = root ;
			root = NULL ;
			delete temp ;
			return true ;
		}
		// root has one child
		if(root->left == NULL){
			node * temp = root ;
			root = root->right ;
			delete temp ;
			return true ;
		}
		// root has one child
		if(root->right == NULL){
			node * temp = root ;
			root = root->left ;
			delete temp ;
			return true ;
		}
		// root has two children
		node * successor = root->right ;
		node * successorParent = root ;
		while(successor->left != NULL){
			successorParent = successor ;
			successor = successor->left ;
		}
		if(successor->data > successorParent->data)
			successorParent->right = NULL ;
		else
			successorParent->left = NULL ;

		root->data = successor->data ;
		delete successor ;
		return true ;
	}

	node * current = root ;
	node * parent = NULL ;
	while(current != NULL && current->data != badNumber){
		parent = current ;
		if(badNumber < current->data)
			current = current->left ;
		else
			current = current->right ;
	}
	if(current == NULL)
		return false  ;
	else{
		if(current->data > parent->data){
			// leaf node
			if(current->left == NULL && current->right == NULL){
				parent->right = NULL ;
				delete current ;
				return true ;
			}
			// node has one child
			if(current->left == NULL){
				parent->right = current->right ;
				delete current; 
				return true ;
			}
			// node has one child
			if(current->right == NULL){
				parent->right = current->left ;
				delete current; 
				return true ;
			}
			// node has two children
			node * successor = current->right ;
			node * successorParent = current ;
			while(successor->left != NULL){
				successorParent = successor ;
				successor = successor->left ;
			}
			if(successor->data > successorParent->data)
				successorParent->right = NULL ;
			else
				successorParent->left = NULL ;

			current->data = successor->data ;
			delete successor ;
			return true ;
		}
		else{
			// leaf node
			if(current->left == NULL && current->right == NULL){
				parent->left = NULL ;
				delete current ;
				return true ;
			}
			// node has one child
			if(current->left == NULL){
				parent->left = current->right ;
				delete current; 
				return true ;
			}
			// node has one child
			if(current->right == NULL){
				parent->left = current->left ;
				delete current; 
				return true ;
			}
			// node has two children
			// find successor, swap, delete successor spot
			node * successor = current->right ;
			node * successorParent = current ;
			while(successor->left != NULL){
				successorParent = successor ;
				successor = successor->left ;
			}
			if(successor->data > successorParent->data)
				successorParent->right = NULL ;
			else
				successorParent->left = NULL ;

			current->data = successor->data ;
			delete successor ;
			return true ;
		}
	}
}

bool binaryTree::search(const int number)const{
	node * current = root ;
	node * parent = NULL ;
	while(current != NULL && current->data != number){
		parent = current ;
		if(number < current->data)
			current = current->left ;
		else
			current = current->right ;
	}
	if(current == NULL)
		return false  ;
	else
		return true ;
}


// main holds the driver program
// several choices, including
// insert, remove, search,
// pre, in, and post order traversals
int main(){
	binaryTree tree ;
	int number ;

	char choice ;
	while(true){
		cout << "(i)nsert" << endl ;
		cout << "(r)emove" << endl ;
		cout << "(s)earch" << endl ;
		cout << "(p)re order traversal" << endl ;
		cout << "i(n) order traversal" << endl ;
		cout << "p(o)st order traversal" << endl ;
		cout << "(q)uit" << endl ;
		cout << "Enter choice:" ; 
		cin >> choice ;

		switch(choice){
		case 'i':
		case 'I':
			cout << "Enter number to insert:" ;
			cin >> number ;
			if(!tree.insert(number)) cout << "No Duplicates!" << endl ;
			break ;
		case 'r':
		case 'R':
			cout << "Enter number to remove:" ;
			cin >> number ;
			if(!tree.remove(number)) cout << "Not Found!" << endl ;
			break ;
		case 's':
		case 'S':
			cout << "Enter number to search for:" ;
			cin >> number ;
			if(tree.search(number)) cout << "Found!" << endl; 
			else cout << "Not Found!" << endl ;
			break ;
		case 'p':
		case 'P':
			tree.preOrder() ;
			break ;
		case 'n':
		case 'N':
			tree.inOrder() ;
			break ;
		case 'o':
		case 'O':
			tree.postOrder() ;
			break ;
		case 'q':
		case 'Q': 
			return 0 ;
		}
		system("pause") ;
		system("cls") ;
	}
}

    Source: geocities.com/neonprimetime.geo/cpp/cpp_SourceCode

               ( geocities.com/neonprimetime.geo/cpp)                   ( geocities.com/neonprimetime.geo)