Binary search tree C++

//                                                    March 6, 1998
//                                                 Bert G. Wachsmuth
#include <iostream>
using namespace std;
#ifndef BINSTREE
#define BINSTREE


// you can change the type easily .
typedef int ElementType;    
typedef int ValueType;    

const int PRE_ORDER = 2;
const int IN_ORDER = 3;
const int POST_ORDER = 4;
const int LEVEL_ORDER = 5;
/*
   Node class . 
*/
class Node
{
   // Left node pointer.		
   public: Node *left;
   // right node pointer.
   public: Node *right;
   // ElementType integer in this case.	
   public: ElementType data;

   // constructor 
   public: Node(void);
   // constructor takes ElementType .
   public: Node(ElementType);
};
 
/* 
  Binary Tree class
*/

class BinSTree
{     // Fields
   private: Node *rootNode;
   private: Node *currentNode;
   private: int errorFlag;

   // default Constructor and public methods
   public: BinSTree(void);
   // insert ElementType to tree.
   public: void insert(ElementType);
   // remove ElementType.
   public: void remove(ValueType);
   // get currentNode element.
   public: ElementType retrieve(void);
   // traverse the ree,	
   public: void traverse(int order);
   // find a node by value.
   public: void find(ValueType);
   // destroy tree.
   public: void destroy(void);
   // check if the tree is full.
   public: int isFull(void);
   // check if the ree empty.
   public: int isEmpty(void);
   public: int hasError(void);

   // private functions.	
   private: void preorder(Node *, int);
   private: void postorder(Node *, int);
   private: void inorder(Node *, int);
   private: Node* findParentForNode(ValueType key);
   private: Node* findNodeByValue(ValueType key);
   // find the right node.
   private: Node* findRightNode(Node *);
   // delete a specific node.
   private: void destroyNode(Node *);
};
 
Node::Node(void)
{
   left = right = 0;
}
 
Node::Node(ElementType el)
{
   left = right = 0;
   data = el;
}
 
 
 
BinSTree::BinSTree(void)
{
   rootNode = currentNode = 0;
   errorFlag = false;
}
 

void BinSTree::find(ValueType key)
{
   Node *p = findNodeByValue(key);
   if (p == 0)
      errorFlag = true;
   else
     {
       errorFlag = false;
       currentNode = p;
     }
}
 
void BinSTree::insert(ElementType el)
{
  if (rootNode == 0)
    rootNode = new Node(el);
  else
    {
      Node *p = findNodeByValue(el);
	  // if element not found before 
      if (p == 0)                         
	{
	  // In case root node is parent.
	  Node *parent = rootNode;           
	  if (p != rootNode)                  
	    parent = findParentForNode(el);
	  if (el > parent->data)
	    {
	      parent->right = new Node(el); 
	      currentNode = parent->right;
	    }
	  else
	    {
	      parent->left = new Node(el);
	      currentNode = parent->left;
	    }
	  // everthing is ok .
	  errorFlag = false;                 
	}

      else                        
    // duplicate key.
	errorFlag = true;
    }
}
 
void BinSTree::traverse(int order)
{
   if (order == PRE_ORDER)
      preorder(rootNode, 0);
   else if (order == IN_ORDER)
      inorder(rootNode, 0);
   else if (order == POST_ORDER)
      postorder(rootNode, 0);
   else
      cout << "order doesn't exists" << endl;
}
 
ElementType BinSTree::retrieve(void)
{
  return currentNode->data;
}
 
int BinSTree::isFull(void)
{ 
  return 0;
}
 
int BinSTree::isEmpty(void)
{
  return (rootNode == 0);
}
 
int BinSTree::hasError(void)
{ 
  return errorFlag;
}
 
void BinSTree::remove(ValueType key)
{
  
  Node *p = findNodeByValue(key);      
  // check if node exists.
  if (p == 0)              
    errorFlag = true;
  // node exists .
  else                      
    {
       // delete leaf node.
      if ((p->right == 0) && (p->left == 0))        
	{
	   // (can find parent node.
	  if (p != rootNode)   
	    {
	      Node *parent = findParentForNode(key);
	      if (parent->data < key)
		parent->right = 0;
	      else
		parent->left = 0;
	    }
	  else
	    rootNode = 0;
          delete(p);
	  errorFlag = false;
	  currentNode = rootNode;
	}
      else if ((p->right == 0) && (p->left != 0))  // right subtree empty,
                                                   // left subtree not.
	{
		// can't find parent node .
	  if (p != rootNode)     
	    {
	      Node *parent = findParentForNode(key);
	      if (parent->data < key)
		parent->right = p->left;
	      else
		parent->left = p->left;
	    }
	  else
	    rootNode = rootNode->left;
	  delete(p);
	  errorFlag = false;
	  currentNode = rootNode;
	}
      else if ((p->right != 0) && (p->left == 0))  // left subtree empty,
                                                   // right subtree not.
	{
	  if (p != rootNode)    // (can find parent now ...)
	    {
	      Node *parent = findParentForNode(key);
	      if (parent->data < key)
		parent->right = p->right;
	      else
		parent->left = p->right;
	    }
	  else
	    rootNode = p->right;
	  delete(p);
	  errorFlag = false;
	  currentNode = rootNode;
	}
      else                                         // left and right 
                                                   // subtrees not empty
	{
	  Node *righty = findRightNode(p->left);
	  Node *parent = findParentForNode(righty->data);
	  p->data = righty->data;   // swapping data with righty
	  if (parent != p)
	    parent->right = righty->left;
	  else
	    p->left = righty->left;
	  delete(righty);
	  errorFlag = false;
	  currentNode = rootNode;
	}
    }
}
 
void BinSTree::destroy(void)
{
  destroyNode(rootNode);
}

 

void BinSTree::inorder(Node *p, int level)
{
   if (p != 0)
     {
       inorder(p->left, level+1);
        cout << "Node " << p->data << " at level " << level << endl;
       inorder(p->right, level+1);
     }
}
 
void BinSTree::preorder(Node *p, int level)
{
  if (p != 0)
    {
      cout << "Node " << p->data << " at level " << level << endl;
      preorder(p->left, level+1);
      preorder(p->right, level+1);
    }
}
 
void BinSTree::postorder(Node *p, int level)
{ 
  if (p != 0)
    {
      postorder(p->left, level+1);
      postorder(p->right, level+1);
      cout << "Node " << p->data << " at level " << level << endl;
    }
}
 
void BinSTree::destroyNode(Node *p)
{
  if (p != 0)
    {
      destroyNode(p->left);
      destroyNode(p->right);
      delete(p);
    }
}
 
Node* BinSTree::findParentForNode(ValueType key)
{
   Node *p = rootNode, *q = 0;
   while ((p != 0) && (p->data != key))
     {
       q = p;
       if (p->data > key)
	 p = p->left;
       else
	 p = p->right;
     }
   return q;
}
 
Node* BinSTree::findNodeByValue(ValueType key)
  /* This function returns a pointer to the node containing the key 
     value 'key' if it is in the tree. Otherwise, it returns null */
{
   Node *p = rootNode;
   while ((p != 0) && (p->data != key))
     if (p->data > key)
       p = p->left;
     else
       p = p->right;
   return p;
}
 
Node* BinSTree::findRightNode(Node *p)
{
  Node *righty = p;
  while (righty->right != 0)
    righty = righty->right;
   cout << "found right-most node to be: " << righty->data << "\n";
  return righty;
}
 
#endif


int main(void)
{

	return 0;
}