// File: Tree_ADT.h
// Binary Tree ADT definition

#ifndef TREE_H
#define TREE_H

 template <class EltType> class TreeNode {
 public:
  EltType Info;
  TreeNode *Left,*Right;
 };

template <class TreeEltType> class BinaryTree {

public:



 // Constructor
 BinaryTree();

 // Place Element into Tree
 // Returns 1 if inserted, 0 if Data already in tree
 int InsertToTree(TreeEltType Data);

 // Search for Element in Tree
 // Assumes == is defined for TreeEltType
 // Returns Ptr to Elt if Found, NULL otherwise
 TreeEltType *TreeSearch(TreeEltType Data);

 // Retrieve Element from Tree (leaving Tree Intact)
 // Precondition: Item is in Tree
 TreeEltType RetrieveFromTree(TreeEltType);

 // Remove an Element from the tree
 // Pre: Element is in the Tree
 void DeleteFromTree(TreeEltType Data);

 // Display Tree using InOrder Traversal
 void Inorder();

 // Display Tree using PreOrder Traversal
 void Preorder();

 // Display Tree using PostOrder Traversal
 void Postorder();


private:

 TreeNode<TreeEltType> *Root;


 // Display Tree using InOrder Traversal
 void PrintInorder(TreeNode<TreeEltType> *);

 // Display Tree using PreOrder Traversal
 void PrintPreorder(TreeNode<TreeEltType> *);

 // Display Tree using PostOrder Traversal
 void PrintPostorder(TreeNode<TreeEltType> *);

};

#endif