Population

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

    ¡¡