// TREENODE.H
// Definition of class TreeNode
#ifndef TREENODE_H
#define TREENODE_H

template<class NODETYPE>
class TreeNode {
   friend class Tree<NODETYPE>;
public:
   TreeNode(const NODETYPE &);  // constructor
   NODETYPE getData() const;    // return data
private:
   TreeNode *leftPtr;   // pointer to left subtree
   NODETYPE data;
   TreeNode *rightPtr;  // pointer to right subtree
};

// Constructor
template<class NODETYPE>
TreeNode<NODETYPE>::TreeNode(const NODETYPE &d)
{
   data = d;
   leftPtr = rightPtr = 0;
}

//Return a copy of the data value
template<class NODETYPE>
NODETYPE TreeNode<NODETYPE>::getData() const { return data; }

#endif
------
// TREE.H
// Definition of template class Tree
#ifndef TREE_H
#define TREE_H

#include <iostream.h>
#include <assert.h>
#include "treenode.h"

template<class NODETYPE>
class Tree {
public:
   Tree();
   void insertNode(const NODETYPE &);
   void preOrderTraversal() const;
   void inOrderTraversal() const;
   void postOrderTraversal() const;
private:
   TreeNode<NODETYPE> *rootPtr;

   // utility functions
   void insertNodeHelper(TreeNode<NODETYPE> **, const NODETYPE &);
   void preOrderHelper(TreeNode<NODETYPE> *) const;
   void inOrderHelper(TreeNode<NODETYPE> *) const;
   void postOrderHelper(TreeNode<NODETYPE> *) const;
};

template<class NODETYPE>
Tree<NODETYPE>::Tree() { rootPtr = 0; }

template<class NODETYPE>
void Tree<NODETYPE>::insertNode(const NODETYPE &value)
   { insertNodeHelper(&rootPtr, value); }

// This function receives a pointer to a pointer so the
// pointer can be modified.
template<class NODETYPE>
void Tree<NODETYPE>::insertNodeHelper(TreeNode<NODETYPE> **ptr,
                                       const NODETYPE &value)
{
   if (*ptr == 0) {                   // tree is empty
      *ptr = new TreeNode<NODETYPE>(value);
      assert(*ptr != 0);
   }
   else                              // tree is not empty
      if (value < (*ptr)->data)
         insertNodeHelper( &((*ptr)->leftPtr), value);
      else
         if (value > (*ptr)->data)
            insertNodeHelper(&((*ptr)->rightPtr), value);
         else
            cout << value << " dup" << endl;
}

template<class NODETYPE>
void Tree<NODETYPE>::preOrderTraversal() const
   { preOrderHelper(rootPtr); }

template<class NODETYPE>
void Tree<NODETYPE>::preOrderHelper(TreeNode<NODETYPE> *ptr) const
{
   if (ptr != 0) {
      cout << ptr->data << ' ';
      preOrderHelper(ptr->leftPtr);
      preOrderHelper(ptr->rightPtr);
   }
}

template<class NODETYPE>
void Tree<NODETYPE>::inOrderTraversal() const
   { inOrderHelper(rootPtr); }

template<class NODETYPE>
void Tree<NODETYPE>::inOrderHelper(TreeNode<NODETYPE> *ptr) const
{
   if (ptr != 0) {
      inOrderHelper(ptr->leftPtr);
      cout << ptr->data << ' ';
      inOrderHelper(ptr->rightPtr);
   }
}

template<class NODETYPE>
void Tree<NODETYPE>::postOrderTraversal() const
   { postOrderHelper(rootPtr); }

template<class NODETYPE>
void Tree<NODETYPE>::postOrderHelper(TreeNode<NODETYPE> *ptr) const
{
   if (ptr != 0) {
      postOrderHelper(ptr->leftPtr);
      postOrderHelper(ptr->rightPtr);
      cout << ptr->data << ' ';
   }
}

#endif
------
// Driver to test class Tree
#include <iostream.h>
#include <iomanip.h>
#include "tree.h"

main()
{
   Tree<int> intTree;
   int intVal;

   cout << "Enter 10 integer values:" << endl;
   for(int i = 0; i < 10; i++) {
      cin >> intVal;
      intTree.insertNode(intVal);
   }

   cout << endl << "Preorder traversal" << endl;
   intTree.preOrderTraversal();

   cout << endl << "Inorder traversal" << endl;
   intTree.inOrderTraversal();

   cout << endl << "Postorder traversal" << endl;
   intTree.postOrderTraversal();

   Tree<float> floatTree;
   float floatVal;

   cout << endl << endl << endl << "Enter 10 float values:"
        << endl << setiosflags(ios::fixed | ios::showpoint)
        << setprecision(1);
   for(i = 0; i < 10; i++) {
      cin >> floatVal;
      floatTree.insertNode(floatVal);
   }

   cout << endl << "Preorder traversal" << endl;
   floatTree.preOrderTraversal();

   cout << endl << "Inorder traversal" << endl;
   floatTree.inOrderTraversal();

   cout << endl << "Postorder traversal" << endl;
   floatTree.postOrderTraversal();

   return 0;
}