Population

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?

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); } }

// 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; } };

#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

// 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 }

#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(); }

// 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; } };