// Template della classe Albero (Tree)
#ifndef TREE_H
#define TREE_H

#include <iostream>
using std::cout;
using std::endl;

#include <new>
#include "Treenode.h"


template< typename NODETYPE > class Tree
{
public:
   Tree(); // costruttore
   void insertNode( const NODETYPE & ); // inserimento di un nodo
   void preOrderTraversal() const; // visita preorder
   void inOrderTraversal() const;  // visita inOrder
   void postOrderTraversal() const; // visita postOrder
private:
   TreeNode< NODETYPE > *rootPtr;

   // funzioni di utilità
   void insertNodeHelper( TreeNode< NODETYPE > **, const NODETYPE & );
   void preOrderHelper( TreeNode< NODETYPE > * ) const;
   void inOrderHelper( TreeNode< NODETYPE > * ) const;
   void postOrderHelper( TreeNode< NODETYPE > * ) const;
}; // end class Tree

// costruttore
template< typename NODETYPE >
Tree< NODETYPE >::Tree() 
{ 
   rootPtr = 0; // Albero vuoto
}

// inserisce un nodo nell'Albero
template< typename NODETYPE >
void Tree< NODETYPE >::insertNode( const NODETYPE &value )
{ 
   insertNodeHelper( &rootPtr, value ); 
}

// funzione di utilità chiamata da insertNode; riceve un puntatore a un puntatore in modo che la funzione possa modificarne il valore

template< typename NODETYPE >
void Tree< NODETYPE >::insertNodeHelper( 
   TreeNode< NODETYPE > **ptr, const NODETYPE &value )
{
   // il sottoalbero è vuoto, crea un nuovo TreeNode contenente il valore
   if ( *ptr == 0 )  
      *ptr = new TreeNode< NODETYPE >( value );
   else // il sottoalbero non è vuoto
   {
      // i dati da inserire sono inferiori a quelli del nodo corrente
      if ( value < ( *ptr )->data )
         insertNodeHelper( &( ( *ptr )->leftPtr ), value );
      else
      {
         // i dati da inserire sono maggiori di quelli del nodo corrente
         if ( value > ( *ptr )->data )
            insertNodeHelper( &( ( *ptr )->rightPtr ), value );
         else // valore di dati duplicato ignorato
            cout << value << " dup" << endl;
      }
   }
}

// Visita preorder dell'Albero
template< typename NODETYPE > 
void Tree< NODETYPE >::preOrderTraversal() const
{ 
   preOrderHelper( rootPtr ); 
}

// funzione di ultilità per la visita preorder
template< typename NODETYPE >
void Tree< NODETYPE >::preOrderHelper( TreeNode< NODETYPE > *ptr ) const
{
   if ( ptr != 0 ) 
   {
      cout << ptr->data << ' ';
      preOrderHelper( ptr->leftPtr );
      preOrderHelper( ptr->rightPtr );
   }
}

// Visita inorder dell'Albero
template< typename NODETYPE >
void Tree< NODETYPE >::inOrderTraversal() const
{ 
   inOrderHelper( rootPtr ); 
}

// funzione di ultilità per la visita inorder

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

// Visita postorder dell'Albero
template< typename NODETYPE >
void Tree< NODETYPE >::postOrderTraversal() const
{ 
   postOrderHelper( rootPtr ); 
}

// funzione di ultilità per la visita postorder
template< typename NODETYPE >
void Tree< NODETYPE >::postOrderHelper( 
   TreeNode< NODETYPE > *ptr ) const
{
   if ( ptr != 0 ) 
   {
      postOrderHelper( ptr->leftPtr );
      postOrderHelper( ptr->rightPtr );
      cout << ptr->data << ' ';
   }
}

#endif