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

/////////////////////////////////////////////////////////////
//二叉树中序遍历器类
/////////////////////////////////////////////////////////////
template <class T>
class IInOrder:public BIterator<T>
{
public:
IInOrder(BST<T>& bt)
{
 r=bt.getroot();
 current=NULL;
}
T * GoFirst(BST<T>& bt);
T * Next(void);
private:
 std::stack<BSTNode<T>*> s;
};
template <class T>
T* IInOrder<T>::GoFirst(BST<T> &bt)
{
  current=bt.getroot();
  if(!current)
   return NULL;
        while(current->left!=NULL)
  {
   s.push(current);
   current=current->left;
  }
  return &current->element;
 
}
template <class T>
T* IInOrder<T>::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 &current->element;

}

 

/////////////////////////////////////////////////////////////
//二叉树前序遍历器类
/////////////////////////////////////////////////////////////
template <class T>
class IPreOrder: public BIterator<T>
{
public:
 IPreOrder(BST<T> &bt)
 {
       r=bt.getroot();
       current=NULL;
 }
T* GoFirst(BST<T> &bt);
T* Next(void);
private:
 BSTNode<T>* r,*current;
 std::stack<BSTNode<T>*> s;
};
template <class T>
T* IPreOrder<T>::GoFirst(BST<T> &bt)
{
 current=bt.getroot();
 if(current)
 {
 s.push(current);
 return &current->element;
 }
 else
 return NULL;
}
template <class T>
T* IPreOrder<T>::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 &current->element;

}

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

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

template <class T>
T* IPostOrder<T>::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 &current->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 &current->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 &current->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 &current->element;
}
s.push(current);
current=current->right;
}
}

}
}

int main()
{
 BST<int> tree=BST<int>();
 int* e=0;
 cin>>tree;
 cout<<tree;
 tree.postorder();
   IPostOrder<int> x=IPostOrder<int>(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");
}