//****************************************************
// Header file tree.h for the modified ADT binary tree.
// Pointer-based implementation.
// Programming Project 8
// CS 241 Data Structures
// Fall 2002
//****************************************************
#ifndef __TREE_H
#define __TREE_H

using namespace std;
#include <string>
#include <stdexcept>

const int TREE_ARRAY_SIZE = 100;
// maximum number of nodes in the treeArray data structure.

typedef int treeItemType;
const int MISSING_NODE = 0;
// Marks an array position used to represent a node that would
// be considered "missing" were the tree is a complete binary tree.

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

class treeNode 
{
private:
  treeNode(): Item(0), LChildPtr(NULL), RChildPtr(NULL){}
  treeNode(const treeItemType& NodeItem, treeNode* L, treeNode* R)
    : Item(NodeItem), LChildPtr(L), RChildPtr(R){}
  
  treeItemType Item;
  treeNode* LChildPtr;
  treeNode* RChildPtr;

  friend class tree;
};  

class tree {
public:
 // constructors:
  tree();
  tree(const tree& Tree);
  tree(const char* fname);
  // Creates a tree from the file fname.  It is assumed that this file
  //  contains a full-tree representation of the tree with zeros for
  //  empty nodes.  Creates both the array instance and the pointer
  //  instance.

  ~tree();

  int NodeCount() const;
  // Precondition: none
  // Postcondition: returns the number of nodes in the tree.

  treeItemType MaxElement() const;
  // Precondition: none
  // Postcondition: returns the element with maximum value in the
  //  tree.  If the tree is empty, returns MISSING_NODE.

  bool Member(const treeItemType& Target) const;
  // Precondition: none
  // Postcondition: returns true if Target is in the tree, false
  //  otherwise

  int Height() const;
  // Precondition: none
  // Postcondition: returns the height of the tree

  bool BinaryTreeIsEmpty() const;
  // Precondition: none
  // Postcondition: returns true if the tree is empty, false otherwise

  void PreorderTraverse(functionType Visit);
  // Traverses the tree in preorder, calling function Visit once for
  //  each item.
  // Precondition: The function represented by Visit exists outside of
  //  the class implementation.
  // Postcondition: Visits action occurred once for each item in the
  //  tree.  Note: Visit can alter the tree.

  void InorderTraverse(functionType Visit);
  // Traverse the tree in order, calling function Visit once for each
  //  item
  // Precondition: The function represented by Visit exists outside of
  //  the class implementation.
  // Postcondition: Visits action occurred once for each item in the
  //  tree.  Note: Visit can alter the tree.

  void PostorderTraverse(functionType Visit);
  // Traverses the tree in postorder, calling function Visit once for
  //  each item.
  // Precondition: The function represented by Visit exists outside of
  //  the class implementation.
  // Postcondition: Visits action occurred once for each item in the
  //  tree.  Note: Visit can alter the tree.

  tree& operator=(const tree& Rhs);

private:

  int FindNodeCount(treeNode* TreePtr) const;
  // Precondition: TreePtr is a valid tree
  // Postcondition: calculates (recursively) the number of nodes in
  //  the tree rooted at TreePtr.

  treeItemType FindMaxElement(treeNode* TreePtr) const;
  // Precondition: TreePtr is a valid tree
  // Postcondition: calculates (recursively) the maximum element in
  //  the tree rooted at TreePtr.  If the tree is empty, return
  //  MISSING_NODE.

  bool FindMember(treeNode* TreePtr, const treeItemType& Target) const;
  // Precondition: TreePtr is a valid tree
  // Postcondition: determines (recursively) if Target is contained in
  //  the tree rooted at TreePtr.  Returns true if Target is found,
  //  false otherwise

  int FindHeight(treeNode* TreePtr) const;
  // Precondition: TreePtr is a valid tree
  // Postcondition: calculates (recursively) the height of the tree
  //  rooted at TreePtr

  void ReadTreeAsArray(const char* fname);
  // Precondition: fname is the name of a file containing a tree
  // Postcondition: reads entries for a binary tree from the external
  //  file fname and store in the treeArray.  The elements in the
  //  binary tree are assumed to be strictly positive (greater than
  //  zero).  The file is assumed to contain positive integers for data
  //  elements and zeros for non-existent elements.

  treeNode* ArrayToPtr(int i);
  // Precondition: none
  // Postcondition: copies (recursively) the tree represented in
  //  treeArray into a pointer representation.  Returns a pointer to
  //  the root of the tree.

  void CopyTree(treeNode* TreePtr, treeNode*& NewTreePtr);
  // Precondition: TreePtr points to a valid tree.  NewTreePtr points
  //  to NULL or is uninitialized.
  // Postcondition: copies the tree rooted at TreePtr into a tree
  //  rooted at NewTreePtr.

  void DestroyTree(treeNode*& TreePtr);
  // Precondition: TreePtr points to a valid tree.
  // Postcondition: deallocates memory for a tree.

  // Recursive functions to traverse the tree
  void Preorder(treeNode* TreePtr, functionType Visit);
  void Inorder(treeNode* TreePtr, functionType Visit);
  void Postorder(treeNode* TreePtr, functionType Visit);

 // Data Members

  treeNode* Root;       
  // pointer to root of tree

  treeItemType treeArray[TREE_ARRAY_SIZE];
  // array representation of tree

  int treeArraySize;  // number of nodes in use in treeArray
  // This is *NOT* the number of nodes in the tree since the array
  //  contains zero-entries representing non-existent nodes
};

#endif