//file:BTtree.h
#ifndef _BTTREE_H_HUMING_INCLUDE_
#define _BTTREE_H_HUMING_INCLUDE_
#include
#include
#include
#define maxlen 100
using namespace std;
template
class treenode
{
public:
treenode():lchild(NULL),rchild(NULL) {};
treenode(const T &v,treenode *left,treenode *right):data(v),lchild(left),rchild(right) {};
~treenode()
{
delete lchild;
delete rchild;
}
treenode *lchild,*rchild;
T data;
};
template
class BTtree
{
public:
BTtree():root(NULL) {};
~BTtree();
void pre_create();
bool Isempty();
treenode* Lchild(treenode* t);
treenode* Rchild(treenode* t);
T element(treenode* t);
treenode* return_root();
void pre_order(treenode* t);
void in_order(treenode* t);
void post_order(treenode* t);
void nrec_pre_order(treenode* t);
void nrec_in_order(treenode* t);
void nrec_post_order(treenode* t);
void level_order(treenode* t);
private:
treenode *root;
void clear(treenode* t);
treenode*insert();
};
template
BTtree::~BTtree()
{
clear(root);
delete root;
}
template
void BTtree::clear(treenode* t)
{
if(t==NULL) return;
else
{
clear(t->lchild);
clear(t->rchild);
t=NULL;
}
}
template
void BTtree::pre_create()
{
root=insert();
}
template
treenode* BTtree::insert()
{
T ch;
treenode *t;
cin >> ch;
if(ch=='#') t=NULL;
else
{
t=new treenode;
t->data=ch;
t->lchild=insert();
t->rchild=insert();
}
return t;
}
template
bool BTtree::Isempty()
{
return root false:true;
}
template
treenode* BTtree::Lchild(treenode* t)
{
return t->lchild t->lchild:NULL;
}
template
treenode* BTtree::Rchild(treenode* t)
{
return t->rchild t->rchild:NULL;
}
template
T BTtree::element(treenode* t)
{
return t->data;;
}
template
void BTtree::pre_order(treenode* t)
{
if(t!=NULL)
{
cout << t->data;
pre_order(t->lchild);
pre_order(t->rchild);
}
}
template
treenode* BTtree::return_root()
{
return root;
}
template
void BTtree::in_order(treenode* t)
{
if(t!=NULL)
{
in_order(t->lchild);
cout << t->data;
in_order(t->rchild);
}
}
template
void BTtree::post_order(treenode* t)
{
if(t!=NULL)
{
post_order(t->lchild);
post_order(t->rchild);
cout << t->data;
}
}
template
void BTtree::nrec_pre_order(treenode* t)
{
stack*> s;
while(t!=NULL||!s.empty())
{
while(t!=NULL)
{
cout << t->data;
s.push(t);
t=t->lchild;
}
if(!s.empty())
{
t=s.top();
s.pop();
t=t->rchild;
}
}
}
template
void BTtree::nrec_in_order(treenode* t)
{
stack*> s;
while(t!=NULL||!s.empty())
{
if(t!=NU