// File: Tree_ADT.cpp
// Binary Tree ADT implementation

#include <iostream.h>
#include <string.h>
#include "Tree_ADT.h"

// Constructor
template <class TreeEltType> BinaryTree<TreeEltType>::BinaryTree()
{Root=NULL;}

// Place Element into Tree
// Returns 1 if inserted, 0 if Data already in tree
template <class TreeEltType>
	  int BinaryTree<TreeEltType>::InsertToTree(TreeEltType Data)
{TreeNode<TreeEltType> *T=Root,*Back,*NewNode;
 if (!T) { // Empty Tree
  NewNode=new TreeNode<TreeEltType>;
  NewNode->Info=Data;
  NewNode->Left=NewNode->Right=NULL;
  Root=NewNode;
  return(1);
 }
 // Search for spot to put Data
 while(1) {
  if (!T) { // Nothing Here...Do the Insertion
   NewNode=new TreeNode<TreeEltType>;
   NewNode->Info=Data;
   NewNode->Left=NewNode->Right=NULL;
   if (Data<Back->Info) Back->Left=NewNode;
   else Back->Right=NewNode;
   return(1);
  }
  if (T->Info==Data) return(0); // Data already in Tree
  Back=T; // Set the trail pointer to the ancestor of where we're going
  if (Data<T->Info) T=T->Left;
  else T=T->Right;
 }
}

// Search for Element in Tree
// Assumes == is defined for TreeEltType
// Returns Ptr to Elt if Found, NULL otherwise
template <class TreeEltType>
	    TreeEltType *BinaryTree<TreeEltType>::TreeSearch(TreeEltType Key)
{TreeNode<TreeEltType> *T;
 for (T=Root;T && T->Info!=Key;)
  if (Key<T->Info) T=T->Left;
  else T=T->Right;
 return(&(T->Info));
}

// Retrieve Element from Tree (leaving Tree Intact)
// Precondition: Item is in Tree
template <class TreeEltType>
      TreeEltType BinaryTree<TreeEltType>::RetrieveFromTree(TreeEltType Key)
{TreeNode<TreeEltType> *T;
 for (T=Root;T->Info!=Key;)
  if (Key<T->Info) T=T->Left;
  else T=T->Right;
 return(T->Info);
}

// Remove an Element from the tree
// Pre: Element is in the Tree
template <class TreeEltType>
      void BinaryTree<TreeEltType>::DeleteFromTree(TreeEltType Data)
{TreeNode <TreeEltType> *NodeWithData,*NodeToDelete,*T,*TrailT=NULL;
 for (T=Root;T->Info!=Data;) {
  TrailT=T;
  if (Data<T->Info) T=T->Left;
  else T=T->Right;
 }
 NodeWithData=T;  // Hold onto the Data Node
 if (!(NodeWithData->Left) && !(NodeWithData->Right)) {
  // No Subtree, node is leaf...Wipe it
  // Is it the root?
  if (NodeWithData==Root)
   Root=NULL;
  else if (TrailT->Right==NodeWithData) TrailT->Right=NULL;
  else TrailT->Left=NULL;
  NodeToDelete=NodeWithData;
 }
 else if (!(NodeWithData->Left)) {  // No Left Subtree of Node to Delete
  if (!TrailT) { // Node to delete is root and there is no left subtree
   NodeToDelete=Root;
   Root=Root->Right;
  }
  else {// Otherwise, move up the right subtree
   if (TrailT->Right==NodeWithData) TrailT->Right=NodeWithData->Right;
   else TrailT->Left=NodeWithData->Right;
   NodeToDelete=NodeWithData;
  }
 }
 else { // Left Subtree exists...
   // Go to rightmost node in left subtree
  for (TrailT=NodeWithData,T=NodeWithData->Left;T->Right!=NULL;TrailT=T,T=T->Right);
   // Place node data in NodeWithData
  NodeWithData->Info=T->Info;
   // Set the parent of rightmost node to point at rightmost's left child
   //   (We know it hasn't a right child. Also takes care if no left child.
  if (TrailT==NodeWithData)
   TrailT->Left=T->Left;
  else
   TrailT->Right=T->Left;
  NodeToDelete=T;
 }

 delete NodeToDelete;
}
 // Now, go to rightmost node in left subtree



// Need Helper to Recursively Print the Tree
template <class TreeEltType>
      void BinaryTree<TreeEltType>::PrintInorder(TreeNode<TreeEltType> *T)
//void PrintTheTree(TreeNode *T)
{if (T) {
  PrintInorder(T->Left);
  cout << T->Info << endl;
  PrintInorder(T->Right);
 }
}

// Display Tree using InOrder Traversal
template <class TreeEltType> void BinaryTree<TreeEltType>::Inorder()
{PrintInorder(Root);}

// Need Helper to Recursively Print the Tree
template <class TreeEltType>
      void BinaryTree<TreeEltType>::PrintPreorder(TreeNode<TreeEltType> *T)
//void PrintTheTree(TreeNode *T)
{if (T) {
  PrintPreorder(T->Left);
  cout << T->Info << endl;
  PrintPreorder(T->Right);
 }
}

// Display Tree using InOrder Traversal
template <class TreeEltType> void BinaryTree<TreeEltType>::Preorder()
{PrintInorder(Root);}

// Need Helper to Recursively Print the Tree
template <class TreeEltType>
      void BinaryTree<TreeEltType>::PrintPostorder(TreeNode<TreeEltType> *T)
//void PrintTheTree(TreeNode *T)
{if (T) {
  PrintPostorder(T->Left);
  cout << T->Info << endl;
  PrintPostorder(T->Right);
 }
}

// Display Tree using InOrder Traversal
template <class TreeEltType> void BinaryTree<TreeEltType>::Postorder()
{PrintInorder(Root);}


#pragma option -Jgd
typedef BinaryTree<int> FakeTree;