Write the following functions and add them to the BST class that was explained in the class:

a) A function to count the number of nodes in a binary tree

b) A function to count the number of leaves

c) A function to find the height of the tree

Then write a C++ program that goes with the genBST.h file that tests the three funtions above.

Test your functions and include your source code and screenshots of the testing results.

Here is the BST Code we went over in class....

//************************ genBST.h ************************** // generic binary search tree

#include #include #ifndef BINARY_SEARCH_TREE #define BINARY_SEARCH_TREE

using namespace std;

template class Stack : public stack { public:

T pop() { T tmp = top(); stack::pop(); return tmp; } };

template class Queue : public queue { public: T dequeue() { T tmp = front(); queue::pop(); return tmp; } void enqueue(const T& el) { push(el); } }; template class BST;

template class BSTNode { public: BSTNode() { left = right = 0; } BSTNode(const T& e, BSTNode *l = 0, BSTNode *r = 0) { el = e; left = l; right = r; } T el; BSTNode *left, *right; };

template class BST { public: BST() { root = 0; } ~BST() { clear(); } void clear() { clear(root); root = 0; } bool isEmpty() const { return root == 0; } void preorder() { preorder(root); } void inorder() { inorder(root); } void postorder() { postorder(root); } void insert(const T&); void recursiveInsert(const T& el) { recursiveInsert(root,el); } T* search(const T& el) const { return search(root,el); } T* recursiveSearch(const T& el) const { return recursiveSearch(root,el); }

void deleteByCopying(BSTNode*&); void findAndDeleteByCopying(const T&); void deleteByMerging(BSTNode*&); void findAndDeleteByMerging(const T&); void iterativePreorder(); void iterativeInorder(); void iterativePostorder(); void breadthFirst(); void MorrisPreorder(); void MorrisInorder(); void MorrisPostorder(); void balance(T*,int,int); protected: BSTNode* root; void clear(BSTNode*); void recursiveInsert(BSTNode*&, const T&); T* search(BSTNode*, const T&) const; T* recursiveSearch(BSTNode*, const T&) const; void preorder(BSTNode*); void inorder(BSTNode*); void postorder(BSTNode*); virtual void visit(BSTNode* p) { cout << p->el << ' '; } };

template void BST::clear(BSTNode *p) { if (p != 0) { clear(p->left); clear(p->right); delete p; } }

template void BST::insert(const T& el) { BSTNode *p = root, *prev = 0; while (p != 0) { // find a place for inserting new node; prev = p; if (el < p->el) p = p->left; else p = p->right; } if (root == 0) // tree is empty; root = new BSTNode(el); else if (el < prev->el) prev->left = new BSTNode(el); else prev->right = new BSTNode(el); }

template void BST::recursiveInsert(BSTNode*& p, const T& el) { if (p == 0) p = new BSTNode(el); else if (el < p->el) recursiveInsert(p->left, el); else recursiveInsert(p->right,el); }

template T* BST::search(BSTNode* p, const T& el) const { while (p != 0) if (el == p->el) return &p->el; else if (el < p->el) p = p->left; else p = p->right; return 0; }

template T* BST::recursiveSearch(BSTNode* p, const T& el) const { if (p != 0) if (el == p->el) return &p->el; else if (el < p->el) return recursiveSearch(p->left,el); else return recursiveSearch(p->right,el); else return 0; }

template void BST::inorder(BSTNode *p) { if (p != 0) { inorder(p->left); visit(p); inorder(p->right); } }

template void BST::preorder(BSTNode *p) { if (p != 0) { visit(p); preorder(p->left); preorder(p->right); } }

template void BST::postorder(BSTNode* p) { if (p != 0) { postorder(p->left); postorder(p->right); visit(p); } }

template void BST::deleteByCopying(BSTNode*& node) { BSTNode *previous, *tmp = node; if (node->right == 0) // node has no right child; node = node->left; else if (node->left == 0) // node has no left child; node = node->right; else { tmp = node->left; // node has both children; previous = node; // 1. while (tmp->right != 0) { // 2. previous = tmp; tmp = tmp->right; } node->el = tmp->el; // 3. if (previous == node) previous->left = tmp->left; else previous->right = tmp->left; // 4. } delete tmp; // 5. }

// findAndDeleteByCopying() searches the tree to locate the node containing // el. If the node is located, the function DeleteByCopying() is called.

template void BST::findAndDeleteByCopying(const T& el) { BSTNode *p = root, *prev = 0; while (p != 0 && !(p->el == el)) { prev = p; if (el < p->el) p = p->left; else p = p->right; } if (p != 0 && p->el == el) if (p == root) deleteByCopying(root); else if (prev->left == p) deleteByCopying(prev->left); else deleteByCopying(prev->right); else if (root != 0) cout << "el " << el << " is not in the tree "; else cout << "the tree is empty "; }

template void BST::deleteByMerging(BSTNode*& node) { BSTNode *tmp = node; if (node != 0) { if (!node->right) // node has no right child: its left node = node->left; // child (if any) is attached to its parent; else if (node->left == 0) // node has no left child: its right node = node->right; // child is attached to its parent; else { // be ready for merging subtrees; tmp = node->left; // 1. move left while (tmp->right != 0)// 2. and then right as far as possible; tmp = tmp->right; tmp->right = // 3. establish the link between the node->right; // the rightmost node of the left // subtree and the right subtree; tmp = node; // 4. node = node->left; // 5. } delete tmp; // 6. } }

template void BST::findAndDeleteByMerging(const T& el) { BSTNode *node = root, *prev = 0; while (node != 0) { if (node->el == el) break; prev = node; if (el < node->el) node = node->left; else node = node->right; } if (node != 0 && node->el == el) if (node == root) deleteByMerging(root); else if (prev->left == node) deleteByMerging(prev->left); else deleteByMerging(prev->right); else if (root != 0) cout << "el " << el << " is not in the tree "; else cout << "the tree is empty "; }

template void BST::iterativePreorder() { Stack*> travStack; BSTNode *p = root; if (p != 0) { travStack.push(p); while (!travStack.empty()) { p = travStack.pop(); visit(p); if (p->right != 0) travStack.push(p->right); if (p->left != 0) // left child pushed after right travStack.push(p->left); // to be on the top of the stack; } } }

template void BST::iterativeInorder() { Stack*> travStack; BSTNode *p = root; while (p != 0) { while (p != 0) { // stack the right child (if any) if (p->right) // and the node itself when going travStack.push(p->right); // to the left; travStack.push(p); p = p->left; } p = travStack.pop(); // pop a node with no left child while (!travStack.empty() && p->right == 0) { // visit it and all nodes visit(p); // with no right child; p = travStack.pop(); } visit(p); // visit also the first node with if (!travStack.empty()) // a right child (if any); p = travStack.pop(); else p = 0; } }

template void BST::iterativePostorder() { Stack*> travStack; BSTNode* p = root, *q = root; while (p != 0) { for ( ; p->left != 0; p = p->left) travStack.push(p); while (p->right == 0 || p->right == q) { visit(p); q = p; if (travStack.empty()) return; p = travStack.pop(); } travStack.push(p); p = p->right; } }

template void BST::breadthFirst() { Queue*> queue; BSTNode *p = root; if (p != 0) { queue.enqueue(p); while (!queue.empty()) { p = queue.dequeue(); visit(p); if (p->left != 0) queue.enqueue(p->left); if (p->right != 0) queue.enqueue(p->right); } } }

template void BST::MorrisInorder() { BSTNode *p = root, *tmp; while (p != 0) if (p->left == 0) { visit(p); p = p->right; } else { tmp = p->left; while (tmp->right != 0 &&// go to the rightmost node of tmp->right != p) // the left subtree or tmp = tmp->right; // to the temporary parent of p; if (tmp->right == 0) { // if 'true' rightmost node was tmp->right = p; // reached, make it a temporary p = p->left; // parent of the current root, } else { // else a temporary parent has been visit(p); // found; visit node p and then cut tmp->right = 0; // the right pointer of the current p = p->right; // parent, whereby it ceases to be } // a parent; } }

template void BST::MorrisPreorder() { BSTNode *p = root, *tmp; while (p != 0) { if (p->left == 0) { visit(p); p = p->right; } else { tmp = p->left; while (tmp->right != 0 &&// go to the rightmost node of tmp->right != p) // the left subtree or tmp = tmp->right; // to the temporary parent of p; if (tmp->right == 0) { // if 'true' rightmost node was visit(p); // reached, visit the root and tmp->right = p; // make the rightmost node a temporary p = p->left; // parent of the current root, } else { // else a temporary parent has been tmp->right = 0; // found; cut the right pointer of p = p->right; // the current parent, whereby it ceases } // to be a parent; } } }

template void BST::MorrisPostorder() { BSTNode *p = new BSTNode(), *tmp, *q, *r, *s; p->left = root; while (p != 0) if (p->left == 0) p = p->right; else { tmp = p->left; while (tmp->right != 0 &&// go to the rightmost node of tmp->right != p) // the left subtree or tmp = tmp->right; // to the temporary parent of p; if (tmp->right == 0) { // if 'true' rightmost node was tmp->right = p; // reached, make it a temporary p = p->left; // parent of the current root, } else { // else a temporary parent has been found; // process nodes between p->left (included) and p (excluded) // extended to the right in modified tree in reverse order; // the first loop descends this chain of nodes and reverses // right pointers; the second loop goes back, visits nodes, // and reverses right pointers again to restore the pointers // to their original setting; for (q = p->left, r = q->right, s = r->right; r != p; q = r, r = s, s = s->right) r->right = q; for (s = q->right; q != p->left; q->right = r, r = q, q = s, s = s->right) visit(q); visit(p->left); // visit node p->left and then cut tmp->right = 0; // the right pointer of the current p = p->right; // parent, whereby it ceases to be } // a parent; } }

template void BST::balance (T data[], int first, int last) { if (first <= last) { int middle = (first + last)/2; insert(data[middle]); balance(data,first,middle-1); balance(data,middle+1,last); } }

} #endif