#ifndef BITREE_H
#define BITREE_H
#include <iostream>
#include <iomanip>
#include "BiTNode.h"
#include <queue>
#include <stack>
using namespace std;
typedef int Status;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
template<typename NODETYPE>
class BiTree
{
public:
BiTree();
void CreateBiTree();
void DestroyBiTree();
Status BiTreeEmpty();
NODETYPE Root();
int BiTreeDepth();
int BiTreeDepthNonRecursion();
void PreOrderTraverse();
void PreOrderNonRecursion();
void InOrderTraverse();
void InOrderNonRecursion();
void PostOrderTraverse();
void PostOrderNonRecursion();
void LevelOrderTraverse();
void PrintLast();
void PrintByDepth();
private:
BiTNode<NODETYPE> *rootPtr;
void visit(BiTNode<NODETYPE> *p);
void CreateBiTreeHelper(BiTNode<NODETYPE> **T);
void DestroyBiTreeHelper(BiTNode<NODETYPE> **T);
int BiTreeDepthHelper(BiTNode<NODETYPE> *T);
void PreOrderTraverseHelper(BiTNode<NODETYPE> *T);
void InOrderTraverseHelper(BiTNode<NODETYPE> *T);
void PostOrderTraverseHelper(BiTNode<NODETYPE> *T);
};
template<typename NODETYPE>
BiTree<NODETYPE>::BiTree()
{
rootPtr = 0;
}
template<typename NODETYPE>
Status BiTree<NODETYPE>::BiTreeEmpty()
{
if (rootPtr)
return FALSE;
else
return TRUE;
}
template<typename NODETYPE>
void BiTree<NODETYPE>::CreateBiTree()
{
CreateBiTreeHelper(&rootPtr);
}
template<typename NODETYPE>
void BiTree<NODETYPE>::CreateBiTreeHelper(BiTNode<NODETYPE> **T)
{
NODETYPE val;
cin >> val;
if (val == '#')
*T = NULL;
else
{
*T = new BiTNode<NODETYPE>(val);
CreateBiTreeHelper(&(*T)->lchild);
CreateBiTreeHelper(&(*T)->rchild);
}
}
template<typename NODETYPE>
void BiTree<NODETYPE>::DestroyBiTree()
{
DestroyBiTreeHelper(&rootPtr);
}
template<typename NODETYPE>
void BiTree<NODETYPE>::DestroyBiTreeHelper(BiTNode<NODETYPE> **T)
{
if (*T)
{
if ((*T)->lchild)
DestroyBiTreeHelper(&(*T)->lchild);
if ((*T)->rchild)
DestroyBiTreeHelper(&(*T)->rchild);
free(*T);
*T = NULL;
}
}
template<typename NODETYPE>
int BiTree<NODETYPE>::BiTreeDepth()
{
return BiTreeDepthHelper(rootPtr);
}
template<typename NODETYPE>
int BiTree<NODETYPE>::BiTreeDepthHelper(BiTNode<NODETYPE> *T)
{
int i, j;
if (!T)
return 0;
if (T->lchild)
i = BiTreeDepthHelper(T->lchild);
else
i = 0;
if (T->rchild)
j = BiTreeDepthHelper(T->rchild);
else
j = 0;
return i > j ? i+1 : j+1;
}
template<typename NODETYPE>
NODETYPE BiTree<NODETYPE>::Root()
{
if (!rootPtr)
return ' ';
else
return rootPtr->data;
}
template<typename NODETYPE>
int BiTree<NODETYPE>::BiTreeDepthNonRecursion()
{
if (!rootPtr)
return 0;
BiTNode<NODETYPE> *p;
BiTNode<NODETYPE> *back;
int level = 0;
queue<BiTNode<NODETYPE> *> Q;
Q.push(rootPtr);
back = Q.back();
while (!Q.empty())
{
p = Q.front();
Q.pop();
if (p->lchild)
Q.push(p->lchild);
if (p->rchild)
Q.push(p->rchild);
if (p == back)
{
level++;
if (!Q.empty())
back = Q.back();
}
}
return level;
}
template<typename NODETYPE>
void BiTree<NODETYPE>::PreOrderTraverse()
{
PreOrderTraverseHelper(rootPtr);
}
template<typename NODETYPE>
void BiTree<NODETYPE>::PreOrderTraverseHelper(BiTNode<NODETYPE> *T)
{
if (!T)
return;
visit(T);
PreOrderTraverseHelper(T->lchild);
PreOrderTraverseHelper(T->rchild);
}
template<typename NODETYPE>
void BiTree<NODETYPE>::PreOrderNonRecursion()
{
if (!rootPtr)
return;
BiTNode<NODETYPE> *p;
stack<BiTNode<NODETYPE> *> S;
p = rootPtr;
while (p || !S.empty())
{
while (p)
{
visit(p);
S.push(p);
p = p->lchild;
}
if (!S.empty())
{
p = S.top();
S.pop();
p = p->rchild;
}
}
}
template<typename NODETYPE>
void BiTree<NODETYPE>::InOrderTraverse()
{
InOrderTraverseHelper(rootPtr);
}
template<typename NODETYPE>
void BiTree<NODETYPE>::InOrderTraverseHelper(BiTNode<NODETYPE> *T)
{
if (!T)
return;
InOrderTraverseHelper(T->lchild);
visit(T);
InOrderTraverseHelper(T->rchild);
}
template<typename NODETYPE>
void BiTree<NODETYPE>::InOrderNonRecursion()
{
if (!rootPtr)
return;
BiTNode<NODETYPE> *p;
stack<BiTNode<NODETYPE> *> S;
p = rootPtr;
while (p || !S.empty())
{
while (p)
{
S.push(p);
p = p->lchild;
}
if (!S.empty())
{
p = S.top();
S.pop();
visit(p);
p = p->rchild;
}
}
}
template<typename NODETYPE>
void BiTree<NODETYPE>::PostOrderTraverse()
{
PostOrderTraverseHelper(rootPtr);
}
template<typename NODETYPE>
void BiTree<NODETYPE>::PostOrderTraverseHelper(BiTNode<NODETYPE> *T)
{
if (!T)
return;
PostOrderTraverseHelper(T->lchild);
PostOrderTraverseHelper(T->rchild);
visit(T);
}
template<typename NODETYPE>
void BiTree<NODETYPE>::PostOrderNonRecursion()
{
if (!rootPtr)
return;
BiTNode<NODETYPE> *p;
BiTNode<NODETYPE> *r;
stack<BiTNode<NODETYPE> *> S;
p = rootPtr;
r = NULL;
while (p || !S.empty())
{
while (p)
{
S.push(p);
p = p->lchild;
}
if (!S.empty())
{
p = S.top();
if (p->rchild && p->rchild != r)
{
p = p->rchild;
S.push(p);
p = p->lchild;
}
else
{
S.pop();
visit(p);
r = p;
p = NULL;
}
}
}
}
template<typename NODETYPE>
void BiTree<NODETYPE>::LevelOrderTraverse()
{
if (!rootPtr)
return;
BiTNode<NODETYPE> *p;
BiTNode<NODETYPE> *back;
queue<BiTNode<NODETYPE> *> Q;
Q.push(rootPtr);
back = Q.back();
while (!Q.empty())
{
p = Q.front();
Q.pop();
visit(p);
if (p->lchild)
Q.push(p->lchild);
if (p->rchild)
Q.push(p->rchild);
}
}
template<typename NODETYPE>
void BiTree<NODETYPE>::PrintLast()
{
if (!rootPtr)
return;
BiTNode<NODETYPE> *p;
BiTNode<NODETYPE> *back;
queue<BiTNode<NODETYPE> *> Q;
Q.push(rootPtr);
back = Q.back();
while (!Q.empty())
{
p = Q.front();
Q.pop();
if (p->lchild)
Q.push(p->lchild);
if (p->rchild)
Q.push(p->rchild);
if (p == back)
{
visit(p);
if (!Q.empty())
back = Q.back();
}
}
}
template<typename NODETYPE>
void BiTree<NODETYPE>::PrintByDepth()
{
if (!rootPtr)
return;
BiTNode<NODETYPE> *p;
BiTNode<NODETYPE> *back;
queue<BiTNode<NODETYPE> *> Q;
Q.push(rootPtr);
back = Q.back();
while (!Q.empty())
{
p = Q.front();
Q.pop();
visit(p);
if (p->lchild)
Q.push(p->lchild);
if (p->rchild)
Q.push(p->rchild);
if (p == back)
{
cout << endl;
if (!Q.empty())
back = Q.back();
}
}
}
template<typename NODETYPE>
void BiTree<NODETYPE>::visit(BiTNode<NODETYPE> *p)
{
cout << left << setw(5) << p->data;
}
#endif