二叉树的三种遍历方式的非递归和递归实现

//二叉树三种遍历方式的递归非递归实现

#include
#include

using namespace std;

typedef struct BiTreeNode
{

    intdata;
    BiTreeNode*left;
   BiTreeNode*right;

   BiTreeNode()
    {
      left = NULL;
      right =NULL;
    }
}BitTreeNode,*LinkBiTree;

//--------------------先序
void preTraverse( LinkBiTree root) //先序--非递归
{
if(root == NULL)
return ;

BiTreeNode *p = root;
stack stNode;

   while( p!=NULL ||!stNode.empty() )
   {
       while(p != NULL)
       {
          cout << p->data << " ";

         stNode.push(p);//将每一个遍历的节点入栈，用于遍历右孩子
          p=p->left;
       }

p=stNode.top();//取栈顶元素
stNode.pop();//出栈

p = p->right;
}
}

void preTraverse2(LinkBiTree root) //先序--递归
{
if(root == NULL)
return;

BiTreeNode *p = root;

   cout << p->data<< " ";

   preTraverse2(p->left);

preTraverse2(p->right);
}

//------中序
void MidTraverse( LinkBiTree root) //中序--非递归
{
   if(root == NULL)
   return;

   BiTreeNode *p=root;
   stack stNode;

   while( p!= NULL ||!stNode.empty() )
   {
      while(p!=NULL)
      {
          stNode.push(p);//从根节点到最左边叶子节点入栈
          p=p->left;
      }
      p =stNode.top();//取栈顶元素

      cout << p->data << " ";

      stNode.pop();//出栈
      p=p->right;
   }
}

void MidTraverse2(LinkBiTree root) //中序--递归
{
   if(root == NULL)
     return;

   BiTreeNode *p = root;

  MidTraverse2(p->left);

   cout << p->data<< " ";

MidTraverse2(p->right);
}

void postTraverse( LinkBiTree root)//后序非递归
{
    if(root ==NULL)
       return;

    stackstNode;
    BiTreeNode*p = root;
    BiTreeNode*pre = NULL;//记录上次出栈的节点，若是当前节点的右孩子，当前节点出栈，若不是，将当前节点的右孩子入栈

   while(p!=NULL || !stNode.empty())
    {
         while(p!=NULL)//从根节点开始到最左边叶子节点入栈
         {
            stNode.push(p);
            p=p->left;
          }
         p=stNode.top();

         if(p->right!= NULL && p->right !=pre)//存在右孩子，并且有孩子没有入栈（还没访问过）
         {
            p=p->right;
          }
         else
         {
             cout << p->data << " ";
             pre = stNode.top(); //记录本次出栈的元素
             stNode.pop();
              p=NULL;//防止再次入栈
         }
    }
}

void postTraverse2(LinkBiTree root)//后序-递归
{
   if(root == NULL)
    return;
   BiTreeNode *p = root;

   postTraverse2(p->left);

postTraverse2(p->right);

cout << p->data<< " ";
}

int main()
{
BiTreeNode*node = new BiTreeNode[5];
BiTreeNode*root = node;

   root->left = &node[1];
   root->right = &node[2];
   node[1].right = &node[3];
    node[3].left= &node[4];

for(inti=0;i!=5;++i)
node[i].data = i;

preTraverse(root);
preTraverse2(root);

cout<<endl;

    MidTraverse(root);
   MidTraverse2(root);

   cout<<endl;

   postTraverse(root);
   postTraverse2(root);
    return0;
}//二叉树三种遍历方式的递归非递归实现