Turning Binary Search Tree into Ternary Search Tree

I need to turn the code for a Binary Search Treee into a Ternary search tree.  The file will not complile and states that the insert function does not accet four variables.  I also think that the atElement is wrong.  Can someone look this over an tell me what is wrong with it.  I don't know much about Ternary Search Trees and have been guessing at what needs to be modified.


        #ifndef _TERNARY_SEARCH_TREE_H_
        #define _TERNARY_SEARCH_TREE_H_

        #include "dsexceptions.h"
        #include <iostream>       // For NULL

          // Ternary node and forward declaration because g++ does
          // not understand nested classes.
        template <class Comparable>
        class TernarySearchTree;

        template <class Comparable>
        class TernaryNode
        {
//old Binary form
//          Comparable element;
//          TernaryNode *left;
//          TernaryNode *right;

            Comparable key1;
            Comparable key2;
            TernaryNode *left;
            TernaryNode *middle;
            TernaryNode *right;

//old Binary form
//            TernaryNode( const Comparable & theElement, TernaryNode *lt, TernaryNode *rt )
//              : element( theElement ), left( lt ), right( rt ) { }
//            friend class TernarySearchTree<Comparable>;

            TernaryNode( const Comparable & theKey1, const Comparable & theKey2,
                       TernaryNode *lt, TernaryNode *mid, TernaryNode *rt )
              : key1( theKey1 ), key2( theKey2), left( lt ), middle(mid), right( rt ) { }
            friend class TernarySearchTree<Comparable>;

        };


        // TernarySearchTree class
        //
        // CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds
        //
        // ******************PUBLIC OPERATIONS*********************
        // void insert( x )       --> Insert x
        // void remove( x )       --> Remove x
        // Comparable find( x )   --> Return item that matches x
        // Comparable findMin( )  --> Return smallest item                        //remove
        // Comparable findMax( )  --> Return largest item                        //remove
        // boolean isEmpty( )     --> Return true if empty; else false
        // void makeEmpty( )      --> Remove all items
        // void printTree( )      --> Print tree in sorted order
        // int countNodes( )      --> Return number of nodes in tree  //added


        template <class Comparable>
        class TernarySearchTree
        {
          public:
            explicit TernarySearchTree( const Comparable & notFound );
            TernarySearchTree( const TernarySearchTree & rhs );
            ~TernarySearchTree( );

                  int GetLeftLinksFollowed() const;
                  int GetMiddleLinksFollowed() const;
                  int GetRightLinksFollowed() const;
                  double exp_path_len();

                  int card_of() const;
            const Comparable & findMin( ) const;
            const Comparable & findMax( ) const;
            const Comparable & find( const Comparable & x ) const;
            bool isEmpty( ) const;
            void printTree( ) const;
            int countNodes( ) const;

            void makeEmpty( );
            void insert( const Comparable & x );
            void remove( const Comparable & x );

            const TernarySearchTree & operator=( const TernarySearchTree & rhs );

          private:
            TernaryNode<Comparable> *root;
            const Comparable ITEM_NOT_FOUND;

                  mutable int num_nodes;
                  mutable int LeftLinksFollowed;
                  mutable int MiddleLinksFollowed;
                  mutable int RightLinksFollowed;
                  
                  const Comparable & elementAt( TernaryNode<Comparable> *t ) const;  
                  
            void insert( const Comparable & x, TernaryNode<Comparable> * & t ) const;
            void remove( const Comparable & x, TernaryNode<Comparable> * & t ) const;
            TernaryNode<Comparable> * findMin( TernaryNode<Comparable> *t ) const;
            TernaryNode<Comparable> * findMax( TernaryNode<Comparable> *t ) const;
            TernaryNode<Comparable> * find( const Comparable & x, TernaryNode<Comparable> *t ) const;
            void makeEmpty( TernaryNode<Comparable> * & t ) const;
            void printTree( TernaryNode<Comparable> *t ) const;
                  int countNodes( TernaryNode<Comparable> *t ) const;
            TernaryNode<Comparable> * clone( TernaryNode<Comparable> *t ) const;
        };


//Add your code for the TernarySearchTree class here


       /**
         * Implements an unbalanced Ternary search tree.
         * Note that all "matching" is based on the < method.
         */

        /**MMZ-OK
            * Construct the tree.
         */
        template <class Comparable>
        TernarySearchTree<Comparable>::TernarySearchTree( const Comparable & notFound ) :
          ITEM_NOT_FOUND( notFound ), root( NULL )
        {
                    LeftLinksFollowed = 0;
                    MiddleLinksFollowed = 0;
                    RightLinksFollowed = 0;
                    num_nodes = 0;
        }


        /**MMZ-OK
            * Copy constructor.
         */
        template <class Comparable>
        TernarySearchTree<Comparable>::
        TernarySearchTree( const TernarySearchTree<Comparable> & rhs ) :
          root( NULL ), ITEM_NOT_FOUND( rhs.ITEM_NOT_FOUND )
        {
            *this = rhs;
        }

        /**MMZ-OK
            * Destructor for the tree.
         */
        template <class Comparable>
        TernarySearchTree<Comparable>::~TernarySearchTree( )
        {
            makeEmpty( );
        }

        /**MMZ-OK
         * Insert x into the tree; duplicates are ignored.
         */
        template <class Comparable>
        void TernarySearchTree<Comparable>::insert( const Comparable & x )
        {
            insert( x, root );
        }

        /**MMZ-OK
         * Remove x from the tree. Nothing is done if x is not found.
         */
        template <class Comparable>
        void TernarySearchTree<Comparable>::remove( const Comparable & x )
        {
            remove( x, root );
        }

        /**MMZ-OK
         * Returns the number of left links followed so far in the tree.
         */
        template <class Comparable>
        int TernarySearchTree<Comparable>::GetLeftLinksFollowed( ) const
        {
            return LeftLinksFollowed;
        }

        /**MMZ-OK
         * Returns the number of middle links followed so far in the tree.
         */
        template <class Comparable>
        int TernarySearchTree<Comparable>::GetMiddleLinksFollowed( ) const
        {
            return MiddleLinksFollowed;
        }

        /**MMZ-OK
         * Returns the number of right links followed so far in the tree.
         */
        template <class Comparable>
        int TernarySearchTree<Comparable>::GetRightLinksFollowed( ) const
        {
            return RightLinksFollowed;
        }

        /**MMZ-OK
            * Returns the cardinality (number of nodes) in the tree.
            */
        template <class Comparable>
                  int TernarySearchTree<Comparable>::card_of( ) const
        {
            return num_nodes;
        }
            
            template <class Comparable>
                  double TernarySearchTree<Comparable>::exp_path_len( )
                  /*
                  **  Calculate the expected path length of the tree
                  **  This is the public version, without a parameter.
                  **  NOTE that it recursively invokes int_path_length()
                  */
        {
                  // YOUR CODE HERE
                  return -99.0;  // stub, remove after writing your code
        }
            
        /**MMZ-OK
            * Find the smallest item in the tree.
            * Return smallest item or ITEM_NOT_FOUND if empty.
            */
        template <class Comparable>
        const Comparable & TernarySearchTree<Comparable>::findMin( ) const
        {
            return elementAt( findMin( root ) );
        }

        /**MMZ-OK
         * Find the largest item in the tree.
         * Return the largest item of ITEM_NOT_FOUND if empty.
         */
        template <class Comparable>
        const Comparable & TernarySearchTree<Comparable>::findMax( ) const
        {
            return elementAt( findMax( root ) );
        }

        /**MMZ-OK
         * Find item x in the tree.
         * Return the matching item or ITEM_NOT_FOUND if not found.
         */
        template <class Comparable>
        const Comparable & TernarySearchTree<Comparable>::
                                 find( const Comparable & x ) const
        {
            return elementAt( find( x, root ) );
        }

        /**MMZ-OK
         * Make the tree logically empty.
         */
        template <class Comparable>
        void TernarySearchTree<Comparable>::makeEmpty( )
        {
            makeEmpty( root );
        }

        /**MMZ-OK
         * Test if the tree is logically empty.
         * Return true if empty, false otherwise.
         */
        template <class Comparable>
        bool TernarySearchTree<Comparable>::isEmpty( ) const
        {
            return root == NULL;
        }

        /**MMZ-OK
         * Print the tree contents in sorted order.
         */
        template <class Comparable>
        void TernarySearchTree<Comparable>::printTree( ) const
        {
            if( isEmpty( ) )
                cout << "Empty tree" << endl;
            else
                printTree( root );
        }

        /**MMZ-OK
         * Deep copy.
         */
        template <class Comparable>
        const TernarySearchTree<Comparable> &
        TernarySearchTree<Comparable>::
        operator=( const TernarySearchTree<Comparable> & rhs )
        {
            if( this != &rhs )
            {
                makeEmpty( );
                root = clone( rhs.root );
            }
            return *this;
        }


/////////////////////////////////////////
        /**MMZ-??????
         * Internal method to get element field in node t.
         * Return the element field or ITEM_NOT_FOUND if t is NULL.
         */
        template <class Comparable>
        const Comparable & TernarySearchTree<Comparable>::
        elementAt( TernaryNode<Comparable> *t ) const
        {
/*                  orginal code
            return t == NULL ? ITEM_NOT_FOUND : t->element; */
              return t == NULL ? ITEM_NOT_FOUND : t->key1 ? t->key2;

//Maybe something like this????
//          return ITEM_NOT_FOUND : t->key1;  ///?????
//          return ITEM_NOT_FOUND : t->key2;  ///?????

        }

        /**MMZ-?????
            * Internal method to insert into a subtree.
            * x is the item to insert.
            * t is the node that roots the tree.
            * Set the new root.
            */
        template <class Comparable>
                  void TernarySearchTree<Comparable>::
                  insert( const Comparable & x, TernaryNode<Comparable> * & t ) const
        {
            if( t == NULL )
                  {
/*                  orginal code
                t = new BinaryNode<Comparable>( x, NULL, NULL ); */
                t = new TernaryNode<Comparable>( x, NULL, NULL, NULL ); //?????????
                  }
            else if( x < t->key1 )
                  {
                insert( x, t->left );
                  }
            else if((x > t->key1) && (x < t->key2))
                  {
                insert( x, t->middle );
                  }
                  else if( x > t->key2 )
                  {
                insert( x, t->right );
                  }
            else; // Duplicate; do nothing
             
        }

       /**
         * Internal method to remove from a subtree.
         * x is the item to remove.
         * t is the node that roots the tree.
         * Set the new root.
         */
        template <class Comparable>
        void TernarySearchTree<Comparable>::
        remove( const Comparable & x, TernaryNode<Comparable> * & t ) const
        {
            if( t == NULL )
                return;   // Item not found; do nothing
            if( x < t->key1 )
                remove( x, t->left );
            if((x > t->key1) && (x < t->key2))
                remove( x, t->middle );
            else if( x > t->key2 )
                remove( x, t->right );
            else if( t->left !=NULL && t->middle !=NULL && t->right !=NULL ) // Three children
            {
                t->key2 = findMin( t->right )->key2;
                remove( t->key2, t->right );
            }
            else
            {
                TernaryNode<Comparable> *oldNode = t; ///????????????
                t = ( t->left != NULL ) ? t->left : t->right;
                delete oldNode;
            }
        }


        /**MMZ-OK because smallest is still in left tree
         * Internal method to find the smallest item in a subtree t.
         * Return node containing the smallest item.
         */
        template <class Comparable>
        TernaryNode<Comparable> *
        TernarySearchTree<Comparable>::findMin( TernaryNode<Comparable> *t ) const
        {
            if( t == NULL )
                return NULL;
            if( t->left == NULL )
                return t;
            return findMin( t->left );
        }

        /**MMZ-OK because largest is still in right tree
         * Internal method to find the largest item in a subtree t.
         * Return node containing the largest item.
         */
        template <class Comparable>
        TernaryNode<Comparable> *
        TernarySearchTree<Comparable>::findMax( TernaryNode<Comparable> *t ) const
        {
            if( t != NULL )
                while( t->right != NULL )
                    t = t->right;
            return t;
        }

        /**MMZ-OK
         * Internal method to find an item in a subtree.
         * x is item to search for.
         * t is the node that roots the tree.
         * Return node containing the matched item.
         */
        template <class Comparable>
        TernaryNode<Comparable> *
        TernarySearchTree<Comparable>::
        find( const Comparable & x, TernaryNode<Comparable> *t ) const
        {
            if( t == NULL )
                return NULL;
            else if( x < t->key1 )
                  {
                return find( x, t->left );
            }
                  else if((x > t->key1) && (x < t->key2))
                  {
                        return find( x, t->middle );
            }
                  else if( t->element < x )
                  {
                        return find( x, t->right );
            }

                  else
                return t;    // Match
        }


        /**MMZ-OK
         * Internal method to make subtree empty.
         */
        template <class Comparable>
        void TernarySearchTree<Comparable>::
        makeEmpty( TernaryNode<Comparable> * & t ) const
        {
            if( t != NULL )
            {
                makeEmpty( t->left );
                makeEmpty( t->middle );
                makeEmpty( t->right );
                delete t;
            }
            t = NULL;
        }

        /**MMZ-OK
         * Internal method to print a subtree rooted at t in sorted order.
         */
        template <class Comparable>
        void TernarySearchTree<Comparable>::printTree( TernaryNode<Comparable> *t ) const
        {
            if( t != NULL )
            {
                printTree( t->left );
                        cout << t->key1 << endl;
                printTree( t->middle );
                        cout << t->key2 << endl;
                printTree( t->right );
            }
        }

        /**MMZ-OK
         * Internal method to clone subtree.
         */
        template <class Comparable>
        TernaryNode<Comparable> *
        TernarySearchTree<Comparable>::clone( TernaryNode<Comparable> * t ) const
        {
            if( t == NULL )
                return NULL;
            else
                return new TernaryNode<Comparable>( t->key1, t->key2, clone( t->left ), clone( t->middle ), clone( t->right ) );
        }

       /**MMZ-OK
         * Return the #nodes in the tree.
         */
        template <class Comparable>
        int TernarySearchTree<Comparable>::countNodes( ) const
        {
            if( isEmpty( ) )
                return 0 ;
            else
                return countNodes( root );
        }

        /**MMZ-OK
         * Internal method to count #nodes in tree rooted at t.
         */
        template <class Comparable>
        int TernarySearchTree<Comparable>::countNodes( TernaryNode<Comparable> *t ) const
        {
            if( t == NULL )
            return 0 ;
          return countNodes(t->left) + countNodes(t->middle) + countNodes(t->right) + 1 ;
        }

        #endif