#ifndef _BINARYTREE_H_
#define _BINARYTREE_H_
#include <iostream>
#include <queue>
#include <stack>
#define max(x, y) ((x) > (y) ? (x) :(y))
int countnode=0; /* the number of nodes */
using namespace std;
template <class T>
class BinaryTree;
template <class T>
class BSTree;
template <class T>
class AVLTree;
template <class T>
class BinaryTreeNode
{
public:
BinaryTreeNode():left(0), right(0) {}
BinaryTreeNode(const T &e):key(e), left(0), right(0){ }
BinaryTreeNode(const T &e, BinaryTreeNode *l, BinaryTreeNode *r):key(e),/
left(l), right(r) {}
T keyValue()
{
return key;
}
friend class BinaryTree<T>;
friend class BSTree<T>;
friend class AVLTree<T>;
protected:
T key;
BinaryTreeNode *left;
BinaryTreeNode *right;
};
template <class T>
class BinaryTree
{
public:
BinaryTree():root(0) {}
BinaryTree(BinaryTreeNode<T> *r):root(r) {}
BinaryTree(const T &t):root(new BinaryTreeNode<T>(t)) {}
virtual ~BinaryTree()
{
destroyTree(root);
root = 0;
}
void makeTree(const T &t, BinaryTree &left, BinaryTree &right);
void preOrder(void (*visit)(BinaryTreeNode<T> *node))
{
preOrder(visit, root);
}
void inOrder(void (*visit)(BinaryTreeNode<T> *node))
{
inOrder(visit, root);
}
void postOrder(void (*visit)(BinaryTreeNode<T> *node))
{
postOrder(visit, root);
}
void levelOrder(void (*visit)(BinaryTreeNode<T> *node))
{
levelOrder(visit, root);
}
void nonRecurPre(void (*visit)(BinaryTreeNode<T> *node))
{
nonRecurPre(visit,root);
}
void nonRecurIn(void (*visit)(BinaryTreeNode<T> *node))
{
nonRecurIn(visit,root);
};
void nonRecurPost(void (*visit)(BinaryTreeNode<T> *node))
{
nonRecurPost(visit,root);
}
int height()
{
return height(root);
}
BinaryTreeNode<T> *copyTree()
{
return copyTree(root);
}
int countLeaf()
{
return countLeaf(root);
}
int countNode()
{
return countNode(root);
};
void destroyTree();
protected:
BinaryTreeNode<T> *root;
void preOrder(void (*visit)(BinaryTreeNode<T> *node), BinaryTreeNode<T> *t);
void inOrder(void (*visit)(BinaryTreeNode<T> *node), BinaryTreeNode<T> *t);
void postOrder(void (*visit)(BinaryTreeNode<T> *node), BinaryTreeNode<T> *t);
void levelOrder(void (*visit)(BinaryTreeNode<T> *node), BinaryTreeNode<T> *t);
void nonRecurPre(void (*visit)(BinaryTreeNode<T> *node), BinaryTreeNode<T> *t);
void nonRecurIn(void (*visit)(BinaryTreeNode<T> *node), BinaryTreeNode<T> *t);
void nonRecurPost(void (*visit)(BinaryTreeNode<T> *node), BinaryTreeNode<T> *t);
int height(BinaryTreeNode<T> *t);
BinaryTreeNode<T> *copyTree(BinaryTreeNode<T> *node) ;
int countLeaf(BinaryTreeNode<T> *t);
void destroyTree(BinaryTreeNode<T> *t);
int countNode(BinaryTreeNode<T> *t);
};
template <class T>
void BinaryTree<T>::makeTree(const T &t, BinaryTree &left, BinaryTree &right)
{
root = new BinaryTreeNode<T>(t, left.root, right.root);
if (root == NULL)
{
cout<<"malloc fails!"<<endl;
return;
}
left.root = right.root = 0;
}
template <class T>
void BinaryTree<T>::preOrder(void (*visit)(BinaryTreeNode<T> *node), /
BinaryTreeNode<T> *t)
{
if(t)
{
visit(t);
preOrder(visit, t->left);
preOrder(visit, t->right);
}
}
template <class T>
void BinaryTree<T>::inOrder(void (*visit)(BinaryTreeNode<T> *node),
BinaryTreeNode<T> *t) {
if(t){
inOrder(visit, t->left);
visit(t);
inOrder(visit, t->right);
}
}
template <class T>
void BinaryTree<T>::postOrder(void (*visit)(BinaryTreeNode<T> *node),
BinaryTreeNode<T> *t)
{
if(t)
{
postOrder(visit, t->left);
postOrder(visit, t->right);
visit(t);
}
}
template <class T>
void BinaryTree<T>::levelOrder(void (*visit)(BinaryTreeNode<T> *node),
BinaryTreeNode<T> *t)
{
queue<BinaryTreeNode<T>*> q;
BinaryTreeNode<T> *temp;
q.push(t);
while(!q.empty())
{
temp=q.front();
visit(temp);
q.pop();
if(temp->left)
q.push(temp->left);
if(temp->right)
q.push(temp->right);
}
}
template <class T>
void BinaryTree<T>::nonRecurPre(void (*visit)(BinaryTreeNode<T> *node),
BinaryTreeNode<T> *t)
{
stack<BinaryTreeNode<T>*> s;
BinaryTreeNode<T> *current = t;
s.push(current);
while (!s.empty() || current != NULL)
{
if(current == NULL)
{
current = s.top();
s.pop();
if (current->right)
{
current = current->right;
s.push(current);
}
else
{
current = NULL;
}
}
else
{
visit(current);
if (current->left)
{
current = current->left;
s.push(current);
}
else
current = NULL;
}
}
}
template <class T>
void BinaryTree<T>::nonRecurIn(void (*visit)(BinaryTreeNode<T> *node),
BinaryTreeNode<T> *t)
{
stack<BinaryTreeNode<T>*> s;
BinaryTreeNode<T> *current = t;
s.push(current);
while (!s.empty() || current != NULL)
{
if(current == NULL)
{
current = s.top();
visit(current);
s.pop();
if (current->right)
{
current = current->right;
s.push(current);
}
else
{
current = NULL;
}
}
else
{
if (current->left)
{
current = current->left;
s.push(current);
}
else
current = NULL;
}
}
}
//后序非递归遍历二叉树
template <class T>
void BinaryTree<T>::nonRecurPost(void (*visit)(BinaryTreeNode<T> *node),
BinaryTreeNode<T> *t)
{
stack<BinaryTreeNode<T>*> s;
stack<int> sf;
int flag = 0;
BinaryTreeNode<T> *current = t;
while (!s.empty() || current != NULL)
{
if(current)
{
flag = 0;
s.push(current);
sf.push(flag);
current = current->left;
}
else
{
current = s.top();
s.pop();
flag = sf.top();
sf.pop();
if (flag == 0)
{
flag = 1;
s.push(current);
sf.push(flag);
current = current->right;
}
else
{
visit(current);
current = NULL;
}
}
}
}
template <class T>
int BinaryTree<T>::height(BinaryTreeNode<T> *t)
{
if(!t)
return 0;
else
return 1 + max(height(t->left), height(t->right));
}
template <class T>
BinaryTreeNode<T> *BinaryTree<T>::copyTree(BinaryTreeNode<T> *node)
{
BinaryTreeNode<T> *l, *r, *p;
if(!node)
return NULL;
if(node->left)
l = copyTree(node->left);
else
l = NULL;
if (node->right)
r = copyTree(node->right);
else
r = NULL;
p = new BinaryTreeNode<T>(node->key, l, r);
return p;
}
template <class T>
int BinaryTree<T>::countLeaf(BinaryTreeNode<T> *t)
{
static count = 0;
if(!t)
return 0;
else
{
if(t->left)
countLeaf(t->left);
if(t->right)
countLeaf(t->right);
if((t->left == NULL) && (t->right == NULL))
count++;
}
return count;
}
template <class T>
void add1(BinaryTreeNode<T> *t)
{
countnode++;
}
template <class T>
int BinaryTree<T>::countNode(BinaryTreeNode<T> *t)
{
countnode = 0;
inOrder(add1, t);
return countnode;
}
//delete tree functions
template <class T>
static void Free(BinaryTreeNode<T> *t){
delete t;
t = NULL;
}
template <class T>
void BinaryTree<T>::destroyTree() {
postOrder(Free);
root = 0;
}
template <class T>
void BinaryTree<T>::destroyTree(BinaryTreeNode<T> *t)
{
if (t)
{
if(t->left)
destroyTree(t->left);
if(t->right)
destroyTree(t->right);
Free(t);
}
}
#endif