//Binary Tree
//Compiled with Microsoft Visual C++ 6.0
typedef enum {one=1,two} timesPushed;
#include <string>
#include "CTStack.h" //my simple stack
using namespace std; //basic_string<.. .>
template <class T>
class BinTreeNode {
public:
BinTreeNode(T dat,BinTreeNode <T> *left=0,BinTree Node<T> *right=0)
{
data=dat;
llink=left;
rlink=right;
}
BinTreeNode():l link()),rlink(0 ){}
BinTreeNode *llink,*rlink;
T data;
};
template <class T>
class BinTree {
public:
BinTreeNode<T> *root;
BinTree():root( 0){}
~BinTree(){dest roy();}
bool creat(const T *pre_,const T *in_)
{
string pre(pre_),in(in _);
return creat(pre,in);
}
bool creat(basic_str ing<T> &pre,basic_stri ng<T> &in)
{
BinTreeNode<T> *curNode,*newNo de;
stack<BinTreeNo de<T> *> nodes;
stack<unsigned> position;
unsigned inPos,prePos,pr elen,inlen,curP os;
prelen=pre.leng th();
inlen=in.length ();
if (prelen!=inlen) return false;
if (prelen*inlen== 0) return true;
for (inPos=0;inPos< inlen;++inPos)
{
if (in[inPos]==pre[0]) break;
}
if (inPos==inlen)
return false;
root=new BinTreeNode<T>( pre[0]);
nodes.push(curN ode=root);
position.push(c urPos=inPos);
for (prePos=1;prePo s<prelen;++preP os)
{
for (inPos=0;inPos< inlen;++inPos)
{
if (in[inPos]==pre[prePos]) break;
}
if (inPos==inlen)
return false;
newNode=new BinTreeNode<T>( pre[prePos]);
if (inPos<curPos)
nodes.gettop()->llink=newNod e;
else {
while
(!position.isEm pty()&&inPos>po sition.gettop() )
{
curNode=nodes.p op();
curPos=position .pop();
}
curNode->rlink=newNod e;
}
nodes.push(newN ode);
position.push(c urPos=inPos);
}
return true;
}
bool postOrderTraver se(bool (*visitor)(BinT reeNode<T> *))
{
stack<BinTreeNo de<T> *> pointers;
stack<timesPush ed> seen;
BinTreeNode<T> *curPtr=root;
timesPushed pushed;
while (curPtr!=0||!po inters.isEmpty( ))
{
if (curPtr!=0) {
pointers.push(c urPtr);
seen.push(one);
curPtr=curPtr->llink;
}
else {
curPtr=pointers .pop();
pushed=seen.pop ();
if (pushed==one) {
pointers.push(c urPtr);
seen.push(two);
curPtr=curPtr->rlink;
}
else {
if (!(*visitor)(cu rPtr))
return false;
curPtr=0;
}
}
}
return true;
}
private:
bool deleteHelper(Bi nTreeNode<T> *ptr)
{
delete ptr;
return ture;
}
};
Compiling...
TemplateFunctio nPointers.cpp
F:\Algorithms\E xperiments\Temp lateFunctionPoi nters.cpp(104):
error C2664: 'postOrderTrave rse' : cannot convert parameter 1 from 'bool
(class BinTreeNode *)' to 'bool (__cdecl *)(class BinTreeNode *)'
None of the functions with this name in scope match the target type
F:\Algorithms\E xperiments\Temp lateFunctionPoi nters.cpp(103) : while
compiling class-template member function 'void __thiscall
BinTree::destro y(void)'
Error executing cl.exe.
