二叉树遍历器

/////////////////////////////////////////////////////////////
//二叉树遍历器基类
/////////////////////////////////////////////////////////////
template
class BIterator
{
public:
   virtual T* GoFirst(BST& bt)=0;
      virtual T* Next(void)=0;
   // virtual void Traverse(void (*Visit)(T& x),const BST& bt)=0;
protected:
   BSTNode *r,*current;
};
/*template
void BIterator::Traverse(void (*Visit)(T& x),const BST& bt)
{
T* p=GoFirst(bt);
while(p)
  {
 Visit(*p);
 p=Next();
  }
};*/

/////////////////////////////////////////////////////////////
//二叉树中序遍历器类
/////////////////////////////////////////////////////////////
template
class IInOrder:public BIterator
{
public:
IInOrder(BST& bt)
{
 r=bt.getroot();
 current=NULL;
}
T * GoFirst(BST& bt);
T * Next(void);
private:
 std::stack*> s;
};
template
T* IInOrder::GoFirst(BST &bt)
{
  current=bt.getroot();
  if(!current)
   return NULL;
        while(current->left!=NULL)
  {
   s.push(current);
   current=current->left;
  }
  return ¤t->element;
 
}
template
T* IInOrder::Next(void)
{
      if(current->right!=NULL)
   {
   current=current->right;
   while(current->left)
   {
   s.push(current);
   current=current->left;
   }
   }
   else if(!s.empty())
   {
   current=s.top();
   s.pop();
   }
   else
   {
    current=NULL;
    return NULL;
   }
   return ¤t->element;

}

 

/////////////////////////////////////////////////////////////
//二叉树前序遍历器类
/////////////////////////////////////////////////////////////
template
class IPreOrder: public BIterator
{
public:
 IPreOrder(BST &bt)
 {
       r=bt.getroot();
       current=NULL;
 }
T* GoFirst(BST &bt);
T* Next(void);
private:
 BSTNode* r,*current;
 std::stack*> s;
};
template
T* IPreOrder::GoFirst(BST &bt)
{
 current=bt.getroot();
 if(current)
 {
 s.push(current);
 return ¤t->element;
 }
 else
 return NULL;
}
template
T* IPreOrder::Next(void)
{
if(current->left)
{
s.push(current->left);
current=current->left;
}
else if(!s.IsEmpty())
{
current=s.Top();
s.pop();
while(!current->right)
{
current=s.Top();
s.pop();
}
current=current->right;
s.push(current);
}
else
{
 current=NULL;
 return current;
}
return ¤t->element;

}

/////////////////////////////////////////////////////////////
//二叉树后序遍历器基类
/////////////////////////////////////////////////////////////
template
class IPostOrder:public BIterator
{
public:
 IPostOrder(BST &bt)
 {
       r=bt.get_root();
    current=NULL;
 }
T* GoFirst(BST& bt);
T* Next(void);
private:
 BSTNode* r,*current,* pre;
    stack*> s;
};

template
T* IPostOrder::GoFirst(BST& bt)
{
pre=NULL;
current=bt.get_root();
for(;current->left!=NULL;current=current->left)
{
s.push(current);
}
return ¤t->element;
}

template
T* IPostOrder::Next(void)
{
if(pre==NULL)
{
pre=current;

current=s.top();

s.pop();

if(current==NULL)
return NULL;
else if(current->right==NULL||current->right==pre)
return ¤t->element;
else
{
s.push(current);
current=current->right;
while(true)
{
for(;current->left!=NULL;current=current->left)
{
 s.push(current);
}
if(current->right==NULL)
{
 return ¤t->element;
}
s.push(current);
current=current->right;
}
}
}
else
{
pre=current;
current=s.top();
s.pop();
if(current==NULL)
return NULL;
else if((current->right==NULL)||(current->right==pre))
return ¤t->element;
else
{
s.push(current);
current=current->right;
while(true)
{
for(;current->left!=NULL;current=current->left)
{
 s.push(current);
}
if(current->right==NULL)
{
 return ¤t->element;
}
s.push(current);
current=current->right;
}
}

}
}

int main()
{
 BST tree=BST();
 int* e=0;
 cin>>tree;
 cout< tree.postorder();
   IPostOrder x=IPostOrder(tree);
   e=x.GoFirst(tree);
   cout<<*e;
   e=x.Next();
   cout<<*e;
      e=x.Next();
   cout<<*e;
      e=x.Next();
   cout<<*e;
      e=x.Next();
   cout<<*e;
   system("pause");
}