Assignment 8
Binary Tree

Assignment Definition

The source files should be

• Binary.h -- the header file for the binary tree class.
• Binary.cpp -- the implementation file for the binary tree class
• Main.cpp -- your main program file.

Note:  The file names are not the same as given in class.  They were change so that a DOS batch file can handle them.

You will submit your program by coming to your instructor's office on or before May 2 and having him execute your program.  The files will be copied from your floppy disk using a batch file.  Therefore, the file names must be exact.
 

Main Program file outline

• include necessary library files
• within the main procedure
• get the name of the input file from the user
• open the input file
• while not at the end of the input file
• read a number
• insert the number into a binary tree.
• close the input file
• open the output file
• write your name on the output file followed by two blank lines
• write "Numbers in asscending order"
• write the numbers in the tree in asscending order followed by two blank lines.
• write "Numbers in descending order"
• write the numbers in the tree in descending order
• close the output file.

 

Binary Tree Header File

template <class T>
class BinaryTree {
 public:
  void Insert( T );
  void WriteAscending( fstream & );
  void WriteDescending( fstream & );
  BinaryTree();
  ~BinaryTree();
 private:
  struct node {
   T item;
   node *left, *right;
  };

  node* rootNode;
  int Size;

  void DeleteTree(node* &);
        void PrintAscending(fstream &, node*);
        void PrintDescending(fstream &, node*);
        void InsertTree(node* &, T);
};

#include "BinaryTree.cpp"
 

Binary Tree Implementation File

template <class T>
void BinaryTree<T>::PrintDescending(fstream &F, node* N)
{ if(N != NULL)
 {   PrintDescending(F, N -> right);
  F << N -> item << endl;
  PrintDescending(F, N -> left);
 }
}

template <class T>
void BinaryTree<T>::PrintAscending(fstream &F, node* N)
{ if(N != NULL)
 {   PrintAscending(F, N -> left);
  F << N -> item << endl;
  PrintAscending(F, N -> right);
 }
}

template <class T>
void BinaryTree<T>::InsertTree(node* &N, T I)
{  if (N == NULL){
  N = new node;
  (N -> left) = NULL;
  (N -> right) = NULL;
    (N -> item) = I;}
   else if ( I < N -> item)
   { InsertTree(N->left, I);}
   else
   { InsertTree(N->right, I);}
}

template <class T>
BinaryTree<T>::BinaryTree()
{ rootNode = NULL;
}

template <class T>
BinaryTree<T>::~BinaryTree()
{DeleteTree(rootNode);}

template <class T>
void BinaryTree<T>::Insert( T I)
{ InsertTree(rootNode, I);
}
 

template <class T>
void BinaryTree<T>::WriteAscending( fstream &F )
{ PrintAscending(F, rootNode);}
 

template <class T>
void BinaryTree<T>::WriteDescending( fstream &F )
{ PrintDescending(F, rootNode); }
 
 

Binary Tree Sample Main Program

void main()
{ BinaryTree<int> Tree;
  int value;

  cout << "Enter an integer: ";
  cin >> value;
  Tree.Insert(value);

  cout << "Enter an integer: ";
  cin >> value;
  Tree.Insert(value);

  cout << "Enter an integer: ";
  cin >> value;
  Tree.Insert(value);

  cout << "Enter an integer: ";
  cin >> value;
  Tree.Insert(value);

  cout << "Enter an integer: ";
  cin >> value;
  Tree.Insert(value);

  cout << "Enter an integer: ";
  cin >> value;
  Tree.Insert(value);

  fstream F;
  F.open("TreeTest.txt", ios::out);
  F << "Write in ascending order " << endl;
  Tree.WriteAscending( F );
  F << endl << endl;
  F << "Write in descending order " << endl;
  Tree.WriteDescending( F );
  F.close();

}