EECE 330 Homework, Spring 2008

// 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); } }; #include <iostream.h> #include <stdlib.h> //#include "book.h" #include "binnode.h" // Stick these in to test the preorder routine template <class Elem> void visit(const Elem& X) {cout << X->val() << endl;}; template <class Elem> void preorder(BinNode<Elem>* subroot) { if (subroot == NULL) return; // Empty subtree, do nothing visit(subroot); // Perform whatever action is desired preorder(subroot->left()); preorder(subroot->right()); } // Test the preorder traversal routines int main() { BinNodePtr<int>* root = new BinNodePtr<int>(10); root->setLeft(new BinNodePtr<int>(15)); root->setRight(new BinNodePtr<int>(20)); preorder(root); return 1; } #include <iostream> #include "binnode.h" using namespace std; int max(int i1, int i2) { return i1>i2?i1:i2; } template <class Elem> int returnHeight(BinNode<Elem>* node) { if (node == NULL) return 0; return 1 + max(returnHeight(node->left()) , returnHeight(node->right())); } template <class Elem> int numberOfNodes(BinNode<Elem>* node) { if (node == NULL) return 0; return 1 + numberOfNodes(node->left()) + numberOfNodes(node->right()); } template <class Elem> int numberOfLeaves(BinNode<Elem>* node) { if (node == NULL) return 0; if (node->left() == NULL && node->right() == NULL) return 1; return numberOfLeaves(node->left()) + numberOfLeaves(node->right()); } void main() { // 1 // lvl 0 root // 2 / \ 3 // lvl 1 o o // / \ // lvl 2 4 o o 5 // / // lvl 3 6 o // \ 7 // lvl 4 o /*1*/ BinNodePtr<int>* root = new BinNodePtr<int>(10); /*2*/ root->setLeft(new BinNodePtr<int>(15)); /*3*/ root->setRight(new BinNodePtr<int>(20)); /*4*/ root->right()->setLeft(new BinNodePtr<int>(15)); /*5*/ root->right()->setRight(new BinNodePtr<int>(20)); /*6*/ root->right()->right()->setLeft(new BinNodePtr<int>(15)); /*7*/ root->right()->right()->left()->setRight(new BinNodePtr<int>(20)); //int maxheight; //returnHeight(root,1,maxheight); cout<<"Height of Tree= "<<returnHeight(root); // 5 cout<<"\nNumber of Nodes= "<<numberOfNodes(root); // 7 cout<<"\nNumber of Leaves= "<<numberOfLeaves(root); // 3 cout<<endl; } // 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 classy 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); } }; #include <iostream.h> #include <stdlib.h> //#include "book.h" #include "binnode.h" // Stick these in to test the preorder routine template <class Elem> void visit(const Elem& X) {cout << X->val() << " ";}; template <class Elem> void inorder(BinNode<Elem>* subroot) { if (subroot == NULL) return; // Empty subtree, do nothing inorder(subroot->left()); visit(subroot); // Perform whatever action is desired inorder(subroot->right()); } // Test the preorder traversal routines int main() { // // lvl 0 101 // / \ // lvl 1 201 202 // / \ // lvl 2 301 302 // / / \ // lvl 3 401 402 403 // // => inorder: 201 > 101 > 401 > 301 > 202 > 402 > 302 > 403 BinNodePtr<int>* root = new BinNodePtr<int>(101); root->setLeft(new BinNodePtr<int>(201)); root->setRight(new BinNodePtr<int>(202)); root->right()->setLeft(new BinNodePtr<int>(301)); root->right()->setRight(new BinNodePtr<int>(302)); root->right()->left()->setLeft(new BinNodePtr<int>(401)); root->right()->right()->setLeft(new BinNodePtr<int>(402)); root->right()->right()->setRight(new BinNodePtr<int>(403)); inorder(root); cout<<endl; return 1; } // 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) { // 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; } }; // 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); } }; using namespace std; // Singly-linked list node class Link { public: BinNode<int>* element; // Value for this node Link *next; // Pointer to next node in list Link(BinNode<int>* elemval, Link* nextval =NULL) { element = elemval; /*element->setVal(elemval->val()); element->setLeft(elemval->left()); element->setRight(elemval->right()); */next = nextval; } Link(Link* nextval =NULL) { next = nextval; } }; // Abstract queue class template <class Elem> class Queue { public: // Reinitialize the queue. The user is responsible for // reclaiming the storage used by the stack elements. virtual void clear() = 0; // Place an element at the rear of the queue. Return // true if successful, false if not (if queue is full). virtual bool enqueue(BinNode<int>&) = 0; // Remove the element at the front of the queue. Return // true if succesful, false if queue is empty. // The element removed is returned in the first parameter. virtual bool dequeue(BinNode<int>&) = 0; // Remove Elem from front // Return in first parameter a copy of the front element. // Return true if succesful, false if queue is empty. virtual bool frontValue(BinNode<int>&) const = 0; // Return the number of elements in the queue. virtual int length() const = 0; }; // This is the file to include in your code if you want access to the // complete LQueue template class // Include the link class #include "bnlink.h" // First, get the declaration for the base stack class #include "bnlqueue.h" // Linked queue implementation template <class Elem> class LQueue: public Queue<Elem> { private: Link* front; // Pointer to front queue node Link* rear; // Pointer to rear queue node int size; // Number of elements in queue public: LQueue(int sz) // Constructor { front = NULL; rear = NULL; size = 0; } ~LQueue() { clear(); } // Destructor void clear() { // Clear queue while(front != NULL) { // Delete each link node rear = front; front = front->next; delete rear; } rear = NULL; size = 0; } bool enqueue(BinNode<int>& it) { if (rear == NULL) // Empty queue front = rear = new Link(&it, NULL); else { // Append new node rear->next = new Link(&it, NULL); rear = rear->next; } size++; return true; } bool dequeue(BinNode<int>& it) { // Remove Elem from front if (size == 0) return false; // Empty //it = front->element; // Store dequeued value cout<<front->element->val()<<" "; BinNode<int>* bn = front->element->left(); if (bn != NULL) enqueue(*bn); bn = front->element->right(); if (bn != NULL) enqueue(*bn); Link* ltemp = front; // Hold dequeued link front = front->next; // Advance front delete ltemp; // Delete link if (front == NULL) rear = NULL; // Dequeued last element size --; dequeue(*bn); return true; // Return element value } bool frontValue(BinNode<int>& it) const { if (size == 0) return false; //it = front->element; return true; } virtual int length() const { return size; } }; // Abstract queue class template <class Elem> class Queue { public: // Reinitialize the queue. The user is responsible for // reclaiming the storage used by the stack elements. virtual void clear() = 0; // Place an element at the rear of the queue. Return // true if successful, false if not (if queue is full). virtual bool enqueue(const Elem&) = 0; // Remove the element at the front of the queue. Return // true if succesful, false if queue is empty. // The element removed is returned in the first parameter. virtual bool dequeue(Elem&) = 0; // Remove Elem from front // Return in first parameter a copy of the front element. // Return true if succesful, false if queue is empty. virtual bool frontValue(Elem&) const = 0; // Return the number of elements in the queue. virtual int length() const = 0; }; #include <iostream> #include "binnode.h" //#include "BinaryNodeLinkedQueue.H" #include "aqueue.h" using namespace std; template <class Elem> void visit(const Elem& X) {cout << X->val() << " ";}; template <class Elem> void printByLevel(BinNode<Elem>* subroot) { AQueue<BinNode<Elem>*> q(999); q.enqueue(subroot); while (q.length()!=0) { BinNode<Elem>* extracted; q.dequeue(extracted); visit(extracted); if(extracted->left() != NULL) q.enqueue(extracted->left()); if(extracted->right()!= NULL) q.enqueue(extracted->right()); } } void main() { // // lvl 0 101 // / \ // lvl 1 201 202 // / \ // lvl 2 301 302 // / / \ // lvl 3 401 402 403 // // => print by level: 101 > 201 > 202 > 301 > 302 > 401 > 402 > 403 BinNodePtr<int>* root = new BinNodePtr<int>(101); root->setLeft(new BinNodePtr<int>(201)); root->setRight(new BinNodePtr<int>(202)); root->right()->setLeft(new BinNodePtr<int>(301)); root->right()->setRight(new BinNodePtr<int>(302)); root->right()->left()->setLeft(new BinNodePtr<int>(401)); root->right()->right()->setLeft(new BinNodePtr<int>(402)); root->right()->right()->setRight(new BinNodePtr<int>(403)); printByLevel(root); cout<<endl; } // 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) { // 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; } }; // 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); } }; // Abstract queue class template <class Elem> class Queue { public: // Reinitialize the queue. The user is responsible for // reclaiming the storage used by the stack elements. virtual void clear() = 0; // Place an element at the rear of the queue. Return // true if successful, false if not (if queue is full). virtual bool enqueue(const Elem&) = 0; // Remove the element at the front of the queue. Return // true if succesful, false if queue is empty. // The element removed is returned in the first parameter. virtual bool dequeue(Elem&) = 0; // Remove Elem from front // Return in first parameter a copy of the front element. // Return true if succesful, false if queue is empty. virtual bool frontValue(Elem&) const = 0; // Return the number of elements in the queue. virtual int length() const = 0; }; #include <iostream.h> #include <stdlib.h> //#include "book.h" #include "binnode.h" #include "AQUEUE.h" // Stick these in to test the preorder routine template <class Elem> void visit(const Elem& X) {cout << X->val() << endl;} template <class Elem> void inorder(BinNode<Elem>* subroot) { if (subroot == NULL) return; // Empty subtree, do nothing inorder(subroot->left()); visit(subroot); // Perform whatever action is desired inorder(subroot->right()); } int max(int x,int y) { if(x>y) return x; else return y; } template <class Elem> int height(BinNode<Elem>* subroot) { if(subroot == NULL) return 0; return 1+max(height(subroot->left()),height(subroot->right())); } template <class Elem> int count(BinNode<Elem>* subroot) { if(subroot == NULL) return 0; return 1+ count(subroot->left()) + count(subroot->right()); } template <class Elem> int numLeaf(BinNode<Elem>* subroot) { if(subroot == NULL) return 0; if(subroot->isLeaf() == true ) return 1; else return numLeaf(subroot->left()) + numLeaf(subroot->right()); } template <class Elem> void level(BinNode<Elem>* subroot) { AQueue<BinNode<Elem>*> q(999); q.enqueue(subroot); while(q.length()!=0) { BinNode<Elem>* temp; q.dequeue(temp); visit(temp); if(temp->left() != NULL) q.enqueue(temp->left()); if(temp->right()!= NULL) q.enqueue(temp->right()); } } // Test the preorder traversal routines int main() { BinNodePtr<int>* root = new BinNodePtr<int>(10); root->setLeft(new BinNodePtr<int>(15)); root->setRight(new BinNodePtr<int>(20)); cout<<"Height is :"<<height(root)<<endl; cout<<"Count is :"<<count(root)<<endl; cout<<"Number of leafs :"<<numLeaf(root)<<endl; cout<<"Inorder traversal:"<<endl; inorder(root); cout<<endl; cout<<"Level printing:"<<endl; level(root); cout<<endl; return 1; }