LevelPrint

A.First Edition
This is first edition of first question in assignment 3 of comp352 and it is a simple test.
B.The problem
How to print a binary tree level by level?
C.The idea of program
 
Use a queue.
D.The major functions
C.Further improvement
The problem is that for such a simple question I have used 7 classes, not including their base abstract classes.
And I haven't mentioned that several classes are template class and I already used some I/O class like ofstream
for I/O. Such deluxry!
//the file name is Levelprint.cpp
#include <iostream>
#include <fstream>
#include "book.h"
#include "Compare.h"
#include "BST.h"

#include "BinNode.h"



//#include "queue.h"
#include "AQueue.h"

using namespace std;

class LevelBST: public BST<int, Int, intIntCompare, IntIntCompare>
{
private:
	ifstream in;
	AQueue<BinNode<Int>*> Que;
public:
	void readFile(const char* fileName);
	void preOrder(BinNode<Int>* ptr, void (*visit)(BinNode<Int>*node));
	void LevelPrint();
};




int main()
{
	LevelBST L;
	L.readFile("c:\\mytree.txt");
	L.LevelPrint();
	return 0;
}



void LevelBST::LevelPrint()
{
	BinNode<Int>* son;

	Que.enqueue(root);

	while (Que.dequeue(son))
	{
	
		cout<<son->val().key()<<endl;
		if (son->left()!=NULL)
		{
			Que.enqueue(son->left());
	
		}
		if (son->right()!=NULL)
		{
			Que.enqueue(son->right());
		
		}
	}
}



void LevelBST::preOrder(BinNode<Int>* ptr, void (*visit)(BinNode<Int>*node))
{
	if (ptr!=NULL)
	{
		visit(ptr);
		preOrder(ptr->left(), visit);
		preOrder(ptr->right(), visit);
	}
}

void LevelBST::readFile(const char* fileName)
{
	in.open(fileName);
	Int *myInt;
	int i;
	while (!in.eof())
	{
		in>>i;
		myInt= new Int(i);
		insert(*myInt);
	}
}



//file name AQueue.h
// This is the file to include in your code if you want access to the
// complete AQueue template class

// First, get the declaration for the base stack class
#include "queue.h"

// Array-based queue implementation
template <class Elem> class AQueue: public Queue<Elem> {
private:
  int size;                  // Maximum size of queue
  int front;                 // Index of front element
  int rear;                  // Index of rear element
  Elem *listArray;           // Array holding queue elements
public:
  AQueue(int sz =DefaultListSize) { // Constructor 
    // Make list array one position larger for empty slot
    size = sz+1;
    rear = 0;  front = 1;
    listArray = new Elem[size];
  }
  ~AQueue() { delete [] listArray; } // Destructor
  void clear() { front = rear; }
  bool enqueue(const Elem& it) {
    if (((rear+2) % size) == front) return false;  // Full
    rear = (rear+1) % size; // Circular increment
    listArray[rear] = it;
    return true;
  }
  bool dequeue(Elem& it) {
    if (length() == 0) return false;  // Empty
    it = listArray[front];
    front = (front+1) % size; // Circular increment
    return true;
  }
  bool frontValue(Elem& it) const {
    if (length() == 0) return false;  // Empty
    it = listArray[front];
    return true;
  }
  virtual int length() const
   { return ((rear+size) - front + 1) % size; }
};
 
//file name Binnode.h
#ifndef BINNODE_H
#define BINNODE_H

// Binary tree node abstract class
template <class Elem> class BinNode {
public:
  // Return the node's element
  virtual Elem& val() = 0;
  // Set the node's element
  virtual void setVal(const Elem&) = 0;
  // Return the node's left child
  virtual BinNode* left() const = 0;
  // Set the node's left child
  virtual void setLeft(BinNode*) = 0;
  // Return the node's right child
  virtual BinNode* right() const = 0;
  // Set the node's right child
  virtual void setRight(BinNode*) = 0;
  // Return true iff the node is a leaf
  virtual bool isLeaf() = 0;
};

// Binary tree node class
template <class Elem>
class BinNodePtr : public BinNode<Elem> {
private:
  Elem it;                     // The node's value
  BinNodePtr* lc;              // Pointer to left child
  BinNodePtr* rc;              // Pointer to right child
public:
  // Two constructors -- with and without initial values
  BinNodePtr() { lc = rc = NULL; }
  BinNodePtr(Elem e, BinNodePtr* l =NULL,
                     BinNodePtr* r =NULL)
    { it = e; lc = l; rc = r; }
  ~BinNodePtr() {}             // Destructor
  Elem& val() { return it; }
  void setVal(const Elem& e) { it = e; }
  inline BinNode<Elem>* left() const { return lc; }
  void setLeft(BinNode<Elem>* b) { lc = (BinNodePtr*)b; }
  inline BinNode<Elem>* right() const { return rc; }
  void setRight(BinNode<Elem>* b) { rc = (BinNodePtr*)b; }
  bool isLeaf() { return (lc == NULL) && (rc == NULL); }
};

#endif
//filename BST.h
// This file includes all of the pieces of the BST implementation

#include "dictionary.h"

#include "binnode.h"

// Binary Search Tree implementation for the Dictionary ADT
template <class Key, class Elem, class KEComp, class EEComp>
class BST : public Dictionary<Key, Elem, KEComp, EEComp> {
protected:
  BinNode<Elem>* root;   // Root of the BST
  int nodecount;         // Number of nodes in the BST
  // Private "helper" functions
  void clearhelp(BinNode<Elem>*);
  BinNode<Elem>* inserthelp(BinNode<Elem>*, const Elem&);
  BinNode<Elem>* deletemin(BinNode<Elem>*, BinNode<Elem>*&);
  BinNode<Elem>* removehelp(BinNode<Elem>*, const Key&,
                            BinNode<Elem>*&);
  bool findhelp(BinNode<Elem>*, const Key&, Elem&) const;
  void printhelp(BinNode<Elem>*, int) const;
public:
  BST() { root = NULL; nodecount = 0; }  // Constructor
  ~BST() { clearhelp(root); }            // Destructor
  void clear()
    { clearhelp(root); root = NULL; nodecount = 0; }
  bool insert(const Elem& e) {
    root = inserthelp(root, e);
    nodecount++;
    return true;
  }
  bool remove(const Key& K, Elem& e) {
    BinNode<Elem>* t = NULL;
    root = removehelp(root, K, t);
    if (t == NULL) return false;  // Nothing found
    e = t->val();
    nodecount--;
    delete t;
    return true;
  }
  bool removeAny(Elem& e) { // Delete min value
    if (root == NULL) return false; // Empty tree
    BinNode<Elem>* t;
    root = deletemin(root, t);
    e = t->val();
    delete t;
    nodecount--;
    return true;
  }
  bool find(const Key& K, Elem& e) const
    { return findhelp(root, K, e); }
  int size() { return nodecount; }
  void print() const {
    if (root == NULL) cout << "The BST is empty.\n";
    else printhelp(root, 0);
  }
};

template <class Key, class Elem, class KEComp, class EEComp>
void BST<Key, Elem, KEComp, EEComp>::
clearhelp(BinNode<Elem>* subroot) {
  if (subroot == NULL) return;
  clearhelp(subroot->left());
  clearhelp(subroot->right());
  delete subroot;
}

template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* BST<Key, Elem, KEComp, EEComp>::
inserthelp(BinNode<Elem>* subroot, const Elem& val) {
  if (subroot == NULL)            // Empty tree: create node
    return (new BinNodePtr<Elem>(val, NULL, NULL));
  if (EEComp::lt(val, subroot->val())) // Insert on left
    subroot->setLeft(inserthelp(subroot->left(), val));
  else subroot->setRight(inserthelp(subroot->right(), val));
  return subroot;  // Return subtree with node inserted
}

template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* BST<Key, Elem, KEComp, EEComp>::
deletemin(BinNode<Elem>* subroot, BinNode<Elem>*& min) {
  if (subroot->left() == NULL) { // Found min
    min = subroot;
    return subroot->right();
  }
  else {                         // Continue left
    subroot->setLeft(deletemin(subroot->left(), min));
    return subroot;
  }
}

template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* BST<Key, Elem, KEComp, EEComp>::
removehelp(BinNode<Elem>* subroot, const Key& K,
           BinNode<Elem>*& t) {
  if (subroot == NULL) return NULL; // Val is not in tree
  else if (KEComp::lt(K, subroot->val())) // Check left
    subroot->setLeft(removehelp(subroot->left(), K, t));
  else if (KEComp::gt(K, subroot->val())) // Check right
    subroot->setRight(removehelp(subroot->right(), K, t));
  else {                           // Found it: remove it
    BinNode<Elem>* temp;
    t = subroot;
    if (subroot->left() == NULL)       // Only a right child
      subroot = subroot->right();      //  so point to right
    else if (subroot->right() == NULL) // Only a left child
      subroot = subroot->left();       //  so point to left
    else {                    // Both children are non-empty
      subroot->setRight(deletemin(subroot->right(), temp));
      Elem te = subroot->val();
      subroot->setVal(temp->val());
      temp->setVal(te);
      t = temp;
    }
  }
  return subroot;
}

template <class Key, class Elem, class KEComp, class EEComp>
bool BST<Key, Elem, KEComp, EEComp>:: findhelp(
      BinNode<Elem>* subroot, const Key& K, Elem& e) const {
  if (subroot == NULL) return false;         // Empty tree
  else if (KEComp::lt(K, subroot->val()))    // Check left
    return findhelp(subroot->left(), K, e);
  else if (KEComp::gt(K, subroot->val()))    // Check right
    return findhelp(subroot->right(), K, e);
  else { e = subroot->val();  return true; } // Found it
}

template <class Key, class Elem, class KEComp, class EEComp>
void BST<Key, Elem, KEComp, EEComp>::
printhelp(BinNode<Elem>* subroot, int level) const {
  if (subroot == NULL) return;          // Empty tree
  printhelp(subroot->left(), level+1);  // Do left subtree
  for (int i=0; i<level; i++)           // Indent to level
    cout << "  ";
  cout << subroot->val() << "\n";       // Print node value
  printhelp(subroot->right(), level+1); // Do right subtree
}
//file name book.h
#include <time.h>  // Used by timing functions
#include <iostream>
using namespace std;
// Utility functions and macros

// Return true iff x is even
inline bool EVEN(int x) { return (x % 2) == 0; }

// Return true iff x is odd
inline bool ODD(int x) { return (x & 1) != 0; }

const int DefaultListSize = 10; // Lists, etc. default size 

// Assert: If boolean expression is false, print a message
//   and terminate the program
void Assert(bool val, char* string) {
  if (!val) { // Assertion failed -- close the program
    cout << "Assertion Failed: " << string << endl;
    exit(-1);
  }
}

// Random number generator functions

inline void Randomize() // Seed the generator
  { srand(1); }

// Return a random value in range 0 to n-1
inline int Random(int n)
  { return rand() % (n); }

// Swap two elements in a generic array
template<class Elem>
inline void swap(Elem A[], int i, int j) {
  Elem temp = A[i];
  A[i] = A[j];
  A[j] = temp;
}

// Swap two objects passed by reference
template<class Elem>
inline void swap(Elem &e1, Elem &e2) {
  Elem temp = e1;
  e1 = e2;
  e2 = temp;
}

// Timing variables and functions
clock_t tstart = 0;  // Time at beginning of timed section

// Initialize the program timer
void Settime()
  { tstart = clock(); }

// Return the elapsed time since the last call to Settime
double Gettime()
  { return (double)((double)clock() - (double)tstart)/
           (double)CLOCKS_PER_SEC; }

// Your basic int type as an object.
class Int {
private:
  int val;
public:
  Int(int input=0) { val = input; }
  // The following is for those times when we actually
  //   need to get a value, rather than compare objects.
  int key() const { return val; }
  // Overload = to support Int foo = 5 syntax
  operator= (int input) { val = input; }
};

// Let us print out Ints easily
ostream& operator<<(ostream& s, const Int& i)
  { return s << i.key(); }
ostream& operator<<(ostream& s, const Int* i)
  { return s << i->key(); }
 
//file name compare.h
// Some definitions for Comparator classes
class intintCompare {
public:
  static bool lt(int x, int y) { return x < y; }
  static bool eq(int x, int y) { return x == y; }
  static bool gt(int x, int y) { return x > y; }
};

class IntIntCompare {
public:
  static bool lt(Int x, Int y) { return x.key() < y.key(); }
  static bool eq(Int x, Int y) { return x.key() == y.key(); }
  static bool gt(Int x, Int y) { return x.key() > y.key(); }
};

class intIntCompare {
public:
  static bool lt(int x, Int y) { return x < y.key(); }
  static bool eq(int x, Int y) { return x == y.key(); }
  static bool gt(int x, Int y) { return x > y.key(); }
};

class intIntsCompare {
public:
  static bool lt(int x, Int* y) { return x < y->key(); }
  static bool eq(int x, Int* y) { return x == y->key(); }
  static bool gt(int x, Int* y) { return x > y->key(); }
};

class IntsIntsCompare {
public:
  static bool lt(Int* x, Int* y) { return x->key() < y->key(); }
  static bool eq(Int* x, Int* y) { return x->key() == y->key(); }
  static bool gt(Int* x, Int* y) { return x->key() > y->key(); }
};

class CCCompare {
public:
  static bool lt(char* x, char* y) { return strcmp(x, y) < 0; }
  static bool eq(char* x, char* y) { return strcmp(x, y) == 0; }
  static bool gt(char* x, char* y) { return strcmp(x, y) > 0; }
};
 
 
//here is the tree input
54 34 2 99 23 33 1 12 19 28 45 55
//the output of level printing is like following:
54
34
99
2
45
55
1
23
12
33
19
28
Press any key to continue

 


                                 back.gif (341 bytes)       up.gif (335 bytes)         next.gif (337 bytes)