//********************************************************************************
// C++ Certificate Program Intermediate Spring 1999 : Stephen Philips
//
// Final Project
// File : \\Venus\katy\C++ Certificate\intermediate\Final Project
//                \BinaryTree.h
//
// Purpose : Declaration for class BinaryTree which is a collection of
//                LeafNodes.
//
// Author : Hsin-yi F. Berg
// Date        : 6/2/99
// Update    : 6/2/99
//********************************************************************************

#ifndef BINARYTREE_H
#define BINARYTREE_H

#include "LeafNode.h"

typedef char * KEY;
typedef LeafNode *ptrLeafNode;

class LeafNode;

class BinaryTree
{
public:
    /*
        BinaryTree::BinaryTree()

        Default constructor for a BinaryTree.
        A BinaryTree is created empty.
    */
    BinaryTree();

    /*
        BinaryTree::~BinaryTree()

        Destructor for a BinaryTree.
    */
    ~BinaryTree();

    /*
        void BinaryTree::Add(KEY word)

        Add an item to the tree.
    */
    void BinaryTree::Add(KEY word);

    /*
        void BinaryTree::Delete(KEY word)

        Remove an item from the tree.
    */
    void BinaryTree::Delete(KEY word);

    /*
        bool BinaryTree::IsEmpty(void)

        Return true is the tree is empty.
    */
    bool BinaryTree::IsEmpty(void);

    /*
        LeafNode *BinaryTree::Find(KEY word)

        Locate an item in the tree.
    */
    LeafNode *BinaryTree::Find(KEY word);

    /*
        LeafNode &BinaryTree::First()

        Locate the smallest item in the tree.
    */
    LeafNode *BinaryTree::First();

//    /*
//        LeafNode &BinaryTree::Next()

//        Traverse the tree usning in-order traversal.
//    */
//    LeafNode &BinaryTree::Next();

    /*
        void BinaryTree::Print() const

        Print the internal data in the BinaryTree.
    */
    void BinaryTree::Print() const;

    /*
        int BinaryTree::GetSize() const

        Get the size of the tree (number of LeafNodes in the tree).
    */
    int BinaryTree::GetSize() const;

protected:

    // root points to a collection of LeafNodes.
    LeafNode *root;
    // size represents how many LeaNode are there in the tree.
    int size;

    /*
    void BinaryTree::Destroy(LeafNode *&rpLeafNode);
    */

    /*
        void BinaryTree::InsertLeafNode(LeafNode *pLinkNode, KEY word)

        Add the item to the left if its key is smaller, otherwise to the right.
        used in Add function.
    */
    void BinaryTree::InsertLeafNode(LeafNode *pLinkNode, KEY word);

    /*
        bool BinaryTree::smaller(KEY word1, KEY word2)

        Comparison function for AddHelper.
        Return true is key1 is smaller than key2
    */
    bool BinaryTree::smaller(KEY word1, KEY word2);

    /*
        void BinaryTree::RemoveLeafNode(LeafNode *pLeafNode, KEY word)

        Remove the item with the matching key.
        used in Delete function.
    */
    void BinaryTree::RemoveLeafNode(LeafNode *pLeafNode, KEY word);

    /*
        void BinaryTree::RemoveLeafNodeHelper(LeafNode *&rpLeafNode)

        Helper function for RemoveLeafNode to delete a specific node.
        pass reference of the pointer.
    */
    void BinaryTree::RemoveLeafNodeHelper(LeafNode *&rpLeafNode);

    /*
        void BinaryTree::FindLeftMostLeafNode(LeafNode *pLeafNode)

        Return the left most LeafNode of the LeafNode past in.
    */
    LeafNode *BinaryTree::FindLeftMostLeafNode(LeafNode *pLeafNode);

    /*
        LeafNode *BinaryTree::FindHelper(LeafNode pLeafNode, KEY word)

        Helper function for Find.
    */
    LeafNode *BinaryTree::FindHelper(LeafNode *pLeafNode, KEY word);

    /*
        void BinaryTree::PrintHelper(LeafNode *pLeafNode) const

        Helper function for tree.
    */
    void BinaryTree::PrintHelper(LeafNode *pLeafNode) const;

};

#endif

Back	Top