#ifndef linkedBinaryTree_
#define linkedBinaryTree_
using namespace std;
#include
#include "binaryTree.h"
#include "arrayQueue.h"
#include "binaryTreeNode.h"
#include "myExceptions.h"
#include "booster.h"
template
class linkedBinaryTree : public binaryTree >
{
public:
linkedBinaryTree() {root = NULL; treeSize = 0;}
~linkedBinaryTree(){erase();};
bool empty() const {return treeSize == 0;}
int size() const {return treeSize;}
E* rootElement() const;
void makeTree(const E& element,
linkedBinaryTree&, linkedBinaryTree&);
linkedBinaryTree& removeLeftSubtree();
linkedBinaryTree& removeRightSubtree();
void preOrder(void(*theVisit)(binaryTreeNode))
{visit = theVisit; preOrder(root);}
void inOrder(void(*theVisit)(binaryTreeNode))
{visit = theVisit; inOrder(root);}
void postOrder(void(*theVisit)(binaryTreeNode))
{visit = theVisit; postOrder(root);}
void levelOrder(void()(binaryTreeNode *));
void preOrderOutput() {preOrder(output); cout << endl;}
void inOrderOutput() {inOrder(output); cout << endl;}
void postOrderOutput() {postOrder(output); cout << endl;}
void levelOrderOutput() {levelOrder(output); cout << endl;}
void erase()
{
postOrder(dispose);
root = NULL;
treeSize = 0;
}
int height() const {return height(root);}
protected:
binaryTreeNoderoot;
static void stack(binaryTreeNode);
int treeSize; // number of nodes in tree
static void (*visit)(binaryTreeNode); // visit function
static int count; // used to count nodes in a subtree
static void preOrder(binaryTreeNodet);
static void inOrder(binaryTreeNode *t);
static void postOrder(binaryTreeNode *t);
static void countNodes(binaryTreeNode *t)
{
visit = addToCount;
count = 0;
preOrder(t);
}
static void dispose(binaryTreeNode *t) {delete t;}
static void output(binaryTreeNode *t)
{cout << t->element << ' ';}
static void addToCount(binaryTreeNode *t)
{count++;}
static int height(binaryTreeNode *t);
};
// the following should work but gives an internal compiler error
// template void (*linkedBinaryTree::visit)(binaryTreeNode);
// so the explicit declarations that follow are used for our purpose instead
void (*linkedBinaryTree::visit)(binaryTreeNode);
void (*linkedBinaryTree::visit)(binaryTreeNode);
void (*linkedBinaryTree >::visit)(binaryTreeNode >);
void (*linkedBinaryTree >::visit)(binaryTreeNode >);
void (*linkedBinaryTree >::visit)(binaryTreeNode >*);
template
E* linkedBinaryTree::rootElement() const
{// Return NULL if no root. Otherwise, return pointer to root element.
if (treeSize == 0)
return NULL; // no root
else
return &root->element;
}
template
void linkedBinaryTree::makeTree(const E& element,
linkedBinaryTree& left, linkedBinaryTree& right)
{
root = new binaryTreeNode (element, left.root, right.root);
treeSize = left.treeSize + right.treeSize + 1;
left.root = right.root = NULL;
left.treeSize = right.treeSize = 0;
}
template
linkedBinaryTree& linkedBinaryTree::removeLeftSubtree()
{
if (treeSize == 0)
throw emptyTree();
linkedBinaryTree leftSubtree;
leftSubtree.root = root->leftChild;
count = 0;
leftSubtree.treeSize = countNodes(leftSubtree.root);
root->leftChild = NULL;
treeSize -= leftSubtree.treeSize;
return leftSubTree;
}
template
linkedBinaryTree& linkedBinaryTree::removeRightSubtree()
{
if (treeSize == 0)
throw emptyTree();
linkedBinaryTree rightSubtree;
rightSubtree.root = root->rightChild;
count = 0;
rightSubtree.treeSize = countNodes(rightSubtree.root);
root->rightChild = NULL;
treeSize -= rightSubtree.treeSize;
return rightSubTree;
}
template
void linkedBinaryTree::preOrder(binaryTreeNoderoot)
{
if (root == NULL)
return;
binaryTreeNode *p = root;
stack<binaryTreeNode> s;
while (!s.empty() || p)
{
while (p)
{
cout << setw(4) << p->element;
s.push(p);
p = p->leftChild;
}
if (!s.empty())
{
p = s.top();
s.pop();
p = p->rightChild;
}
}
cout << endl;
}
template
void linkedBinaryTree::inOrder(binaryTreeNode *t)
{
if (t != NULL)
{
inOrder(t->leftChild);
linkedBinaryTree::visit(t);
inOrder(t->rightChild);
}
}
template
void linkedBinaryTree::postOrder(binaryTreeNode *t)
{
if (t != NULL)
{
postOrder(t->leftChild);
postOrder(t->rightChild);
linkedBinaryTree::visit(t);
}
}
template
void linkedBinaryTree::levelOrder(void(*theVisit)(binaryTreeNode))
{
arrayQueue> q;
binaryTreeNode *t = root;
while (t != NULL)
{
theVisit(t);
if (t->leftChild != NULL)
q.push(t->leftChild);
if (t->rightChild != NULL)
q.push(t->rightChild);
try {t = q.front();}
catch (queueEmpty) {return;}
q.pop();
}
}
template
int linkedBinaryTree::height(binaryTreeNode *t)
{
if (t == NULL)
return 0;
int hl = height(t->leftChild);
int hr = height(t->rightChild);
if (hl > hr)
return ++hl;
else
return ++hr;
}
#endif