学步园

THIS IS THE FIRST HEAD FILE "treeNode.h"
#ifndef TREENODE_H
#define TREENODE_H

template <typename NODETYPE>
class Tree;

template <typename NODETYPE>
class TreeNode
{
friend class Tree<NODETYPE>;
public:
 TreeNode();
 TreeNode(const NODETYPE &d)
  :leftPtr(0), rightPtr(0)
 {
  setData(d);
 }
 
 void setData(NODETYPE value )
 {
  data = value;
 }
 NODETYPE getData() const
 {
  return data;
 }
private:
 TreeNode<NODETYPE> *leftPtr;
 NODETYPE data;
 TreeNode<NODETYPE> * rightPtr;
};

#endif

THIS THE SECOND HEAD FILE" tree.h"

#ifndef TREE_H
#define TREE_H
#include<iostream>
using namespace std;
#include"TreeNode.h"

template< typename NODETYPE >
class Tree
{
public:
 Tree();

 void insertNode( const NODETYPE &);
 void preOrderTranversal();
 void inOrderTranversal();
 void postOrderTranversal();

private:
 TreeNode<NODETYPE> * rootPtr;

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

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

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

template< typename NODETYPE >
void Tree<NODETYPE>::insertNodeHelper(TreeNode<NODETYPE> **ptr, const  NODETYPE &value)
{
 if( *ptr==0 )
  *ptr = new TreeNode<NODETYPE>(value);
 else
 {
  if( value <= (*ptr)->data )
   insertNodeHelper( &((*ptr)->leftPtr), value);
  else
  {
   //if( value > (*ptr)->data )
    insertNodeHelper( &((*ptr)->rightPtr), value);
  // else
   // cout << value << "dup" << endl;
  }
 }
}

template< typename NODETYPE >
void Tree<NODETYPE>::inOrderTranversal()
{
 inOrderHelper(rootPtr);
}

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

template<typename NODETYPE>
void Tree<NODETYPE>::preOrderTranversal()
{
 preOrderHelper(rootPtr);
}

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

template<typename NODETYPE>
void Tree<NODETYPE>::postOrderTranversal()
{
 postOrderHelper(rootPtr);
}

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

THIS IS THE MAIN FUNCTION

#include"Tree.h"
#include<iostream>

#include<iomanip>
using namespace std;

int main()
{
 Tree<int> intTree;
 int intValue;
 cout<<"Input 10 integer values\n";
 for( int i = 0; i < 10; i++ )
 {
  cout << "The " << i << "number is: ";
  cin >> intValue;
  intTree.insertNode(intValue);
 }

 cout << "\npreOrderTranversal:\n" ;
 intTree.preOrderTranversal();

 cout << "\ninOrderTranversal:\n" ;
 intTree.inOrderTranversal();

 cout << "\npostOrderTranversal:\n" ;
 intTree.postOrderTranversal();
 
 return 0;
}