#include <fstream.h>
#include <stdlib.h>
#include <iostream.h>
#include <conio.h>
#include <string.h>
#include <ctype.h>

class TreeNode
  {
   friend class Tree;
  public:
   TreeNode( char * & ); // constructor
   char * getData() const { return data; } // return data
   TreeNode *getLeftPtr() const { return leftPtr; }
   TreeNode *getRightPtr() const { return rightPtr; }
   void setLeftPtr( TreeNode *ptr ) { leftPtr = ptr; }
   void setRightPtr( TreeNode *ptr ) { rightPtr = ptr; }

  private:
   TreeNode *leftPtr; // pointer to left subtree
   char * data;
   TreeNode *rightPtr; // pointer to right subtree
  };

  TreeNode::TreeNode( char * & d )
  {
   data = d;
   leftPtr = rightPtr = 0;
  }

////////////////////////////////////////////////////////////////////////////////

class Tree
 {
  public:
    Tree( );
    void insertNode( char * & );  // 2
    void preOrder() const;
    void inOrder() const;
    void postOrder() const;
    void printOrder( );  // 3
    void read( );

  protected:
    TreeNode *rootPtr;

    void insertNodeHelper( TreeNode **, char * & );
    void preOrderHelper( TreeNode * ) const;
    void inOrderHelper( TreeNode * ) const;
    void postOrderHelper( TreeNode * ) const;
 };

  Tree::Tree() { rootPtr = 0; }


  void Tree::insertNode( char * & value )
  {
   insertNodeHelper( & rootPtr , value );
  }

  void Tree::insertNodeHelper( TreeNode **ptr , char * & value )
  {
   if ( *ptr == 0 )
   {               // tree is empty
   *ptr = new TreeNode( value );
   }
  else if ( strcmp( value , ( *ptr ) -> data ) < 0 )     // tree is not empty
   insertNodeHelper( &( ( *ptr ) -> leftPtr ), value );

  else
   insertNodeHelper( &( ( *ptr ) -> rightPtr ), value );
  }

  void Tree::preOrder() const { preOrderHelper( rootPtr ); }

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

  void Tree::inOrder() const { inOrderHelper( rootPtr ); }

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

  void Tree::postOrder( ) const { postOrderHelper( rootPtr );}

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

  void Tree::printOrder( )
{
 int n ;
 cout<< "\n Enter 1,2,3,or 4 : 1.preOrder 2.inOrder 3.postOrder 4.print both: ";
 cin>> n ;
 switch( n )
 {
  case 1 : preOrder( );
           break;
  case 2 : inOrder( );
           break;
  case 3 : postOrder( );
           break;
  case 4 : preOrder( );  cout<< "preOrder\n";
           inOrder( );   cout<< "inOrder\n";
           postOrder( ); cout<< "postOrder\n";
           break;
 }
}


void Tree::read( )
{
 //char * names[20];  // 20 elements

 ifstream inf( "data.txt" , ios::in );
 if ( !inf )
 {
  cout<< "could not be opened\n";
  exit(0);
 }
 char name[20];
 char symbol[10];
 int charge;

 while( inf>> name >> symbol >> charge )
 {
  insertNode( name );
 }
 inf.close( );
}

/******************************************************************************/


void main( )
  {
  Tree tree;
  tree.read( );

  /*cout<< "Element in the file : \n";
  for ( int i = 0 ; i < 20 ; i++ )
  {
   cout<< element[i] << ' ' ;
   tree.
  }        */

  tree.printOrder( );

  }


 // Test  6.17 sat