// Chap 10, pp 454 - 455
// Rename this file as BT.h

// ********************************************************
// Header file BT.h for the ADT binary tree.
// ********************************************************
#include "boolean.h"

typedef int treeItemType;  // desired-type-of-tree-item

struct treeNode;  // defined in implementation file
typedef treeNode* ptrType;

typedef void (*functionType)(treeItemType& AnItem);

class binTreeClass
{
public:
// constructors and destructor:
   binTreeClass();
   binTreeClass(treeItemType RootItem);
   binTreeClass(treeItemType RootItem,
					 binTreeClass LeftTree,
					 binTreeClass RightTree);
   binTreeClass(const binTreeClass& T);
   virtual ~binTreeClass();

// binary tree operations:
   virtual boolean BinaryTreeIsEmpty();

   virtual treeItemType RootData();
   virtual void SetRootData(treeItemType NewItem);

   virtual void AttachLeft(treeItemType NewItem,
									boolean& Success);
   virtual void AttachRight(treeItemType NewItem,
									 boolean& Success);

   virtual void AttachLeftSubtree(binTreeClass LeftTree,
											 boolean& Success);
   virtual void AttachRightSubtree(binTreeClass RightTree,
											  boolean& Success);

   virtual void DetachLeftSubtree(binTreeClass& LeftTree,
											 boolean& Success);
   virtual void DetachRightSubtree(binTreeClass& RightTree,
											  boolean& Success);

   virtual binTreeClass LeftSubtree();
   virtual binTreeClass RightSubtree();

   virtual void PreorderTraverse(functionType Visit);
   virtual void InorderTraverse(functionType Visit);
   virtual void PostorderTraverse(functionType Visit);

// overloaded operator:
   virtual void operator=(const binTreeClass& T);

protected:
   binTreeClass(ptrType NodePtr);  // constructor

   void CopyTree(ptrType TreePtr,
					  ptrType& NewTreePtr);
   // Copies the tree rooted at TreePtr into a tree rooted
   // at NewTreePtr.

   void DestroyTree(ptrType& TreePtr);
   // Deallocates memory for a tree.

   void SetRootPtr(ptrType NewRoot);
   // Sets private data member Root to NewRoot.

   ptrType RootPtr();
   // Returns a pointer to the root of the tree.

   void Preorder(ptrType TreePtr, functionType Visit);
   void Inorder(ptrType TreePtr, functionType Visit);
   void Postorder(ptrType TreePtr, functionType Visit);

private:
   ptrType Root;  // pointer to root of tree
};  // end class
// End of header file.