// ********************************************************
// Header file BT.h for the ADT binary tree.
// ********************************************************

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

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

struct treeNode;  // defined in implementation file
typedef treeNode* ptrType;  // pointer to node

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

// binary tree operations:
   virtual bool BinaryTreeIsEmpty() const;

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

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

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

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

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

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

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

protected:
   binTreeClass(ptrType NodePtr);  // constructor

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

   void DestroyTree(ptrType& TreePtr);
   // Deallocates memory for a tree.
   // The next two functions retrieve and set the value
   // of the private data member Root.
   ptrType RootPtr() const;
   void SetRootPtr(ptrType NewRoot);

   // The next two functions retrieve and set the values
   // of the left and right child pointers of a tree node.
   void GetChildPtrs(ptrType NodePtr, ptrType& LChildPtr,
                     ptrType& RChildPtr) const;
   void SetChildPtrs(ptrType NodePtr, ptrType LChildPtr,
                     ptrType RChildPtr);

   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.