//---------------------------------------------------------
// ExtraCredit.cpp
//
// An application to test a tree class.
//
// D Searls &
// Asbury College
// April/May 2010
// --------------------------------------------------------

#include<iostream>
#include<string>

using namespace std;

template<class T>
class binaryTree
{

private:

	struct node;
	typedef node* nodePtr;
	struct node
    {
		nodePtr lchild;
        nodePtr rchild;
		T info;
	};

	nodePtr theRoot;  // Pointer to the root of the tree

public:

	// Constructor
	binaryTree()
	{
		theRoot = NULL;
	}

	// Destructor
	~binaryTree()
	{
		reset(theRoot);
	}

	//----------------------------------------------------------
	// Insert
	//
	// Purpose: Insert a new item into the tree in sort order
	//
	// In Parameter: item
	//----------------------------------------------------------
	void insert(const T& item)
	{
		insertInOrder(theRoot, item);
	}

	//----------------------------------------------------------
	// traverse
	//
	// Purpose: Perform an in-order traversal sending the item
	//   values to the standard output.
	//----------------------------------------------------------
	void traverse()
	{
		inOrderTraverse(theRoot);
	}

	//----------------------------------------------------------
	// Clear
	//
	// Clear the tree of all of its nodes
	//----------------------------------------------------------
	void clear()
	{
		reset(theRoot);
	}

private:

	//----------------------------------------------------------
	// insertInOrder
	//
	// Purpose: Insert a new item into this tree in sort order.
	//
	// In/Out Parameter: root
	//
	// In Parameter: item
	//----------------------------------------------------------
	void insertInOrder(nodePtr& root, const T& item)
	{

	}

	//----------------------------------------------------------
	// inOrderTraverse
	//
	// Purpose: Perform an in-order traversal sending the item
	//   values to the standard output.
	//----------------------------------------------------------
	void inOrderTraverse(nodePtr root)
	{

	}


	//----------------------------------------------------------
	// reset
	//
	// Purpose: reset the tree to an empty tree
	//----------------------------------------------------------
	void reset(nodePtr& root)
	{

	}

};
//*********************************************************
//                  M A I N   D R I V E R
//*********************************************************

int main()
{
    binaryTree<string> myTree;

    myTree.insert("dog");
    myTree.insert("frog");
    myTree.insert("cat");
    myTree.insert("goat");
    myTree.insert("rhino");
    myTree.insert("giraffe");
    myTree.insert("horse");
    myTree.insert("sheep");
    myTree.insert("cow");
    myTree.insert("chicken");
    myTree.insert("hamster");
    myTree.insert("buffalo");
    myTree.insert("elephant");
    myTree.insert("walrus");
    myTree.insert("seal");
    myTree.insert("whale");
    myTree.insert("mouse");
    myTree.insert("rat");

    cout << "The tree contains:\n\n";
    myTree.traverse();
    cout << endl;

	// Let's reuse the tree

    myTree.clear();

	myTree.insert("one");
	myTree.insert("two");
	myTree.insert("three");
	myTree.insert("four");
	myTree.insert("five");
	myTree.insert("six");
	myTree.insert("seven");
	myTree.insert("eight");
	myTree.insert("nine");
	myTree.insert("ten");

    cout << "The tree contains:\n\n";
	myTree.traverse();
    cout << endl;
    
    return 0;
}