二叉树的各种遍历

#include <iostream>
#include<stack>
#include<queue>

using namespace std;

struct TreeNode
{
    int val;
    struct TreeNode * left;
    struct TreeNode *right;
    TreeNode(int x)
    {
        this->val=x;
        this->left=nullptr;
        this->right=nullptr;
    }
};

void postOrder(TreeNode *root)
{
    if(root)
    {
        postOrder(root->right);
        postOrder(root->right);
        cout<<root->val;
    }
}

void postOrder2(TreeNode *root)
{
    stack<TreeNode *> s;

    TreeNode *node=root;//遍历指针
    TreeNode *p=nullptr;//辅助指针

    while(node||!s.empty())
    {
        if(node)
        {
            s.push(node);
            node=node->left;
        }
        else
        {
            node=s.top();
            if(node->right&&node->right!=p)//存在右子树并且没有访问过
            {
               node=node->right;
               s.push(node);
               node=node->left;
            }
            else//不存在右子树或者已经访问完成了
             {
              node=s.top();
              s.pop();
              cout<<s.top();
              p=node;
              node=nullptr;              
            }
        }
    }   

}
void PreOrder(TreeNode*root)

{
   if(root)
   {
       cout<<root->val;
       PreOrder(root->left);
       PreOrder(root->right);
   }
  } 

void PreOrder2(TreeNode* root)
{
    if(root==nullptr)  return;
    stack<TreeNode*> s;
    TreeNode *node=root;//声明遍历指针
    while(node||!s.empty())
    {
       if(node!=nullptr)
       {
           cout<<node->val;
           s.push(node);
           node=node->left;
       }
       else //遇到空指针，访问栈顶的右子树节点
       {
           node=s.top()->right;
           s.pop();
       }
    }  
}

void InOrder(TreeNode *root)
{
   if(root)
   {
       InOrder(root->left);
       cout<<root->val;
       InOrder(root->right);
   }
}



void InOrder2(TreeNode *root)
{
    if(root==nullptr) return;
    stack<TreeNode *> s;
    TreeNode *node=root;

    while(node||!s.empty())
    {
        if(node)
        {
            s.push(node);
            node=node->left;

        }
        else
        {
            node=s.top();
            s.pop();
            cout<<node->val;            
            node=node->right;
        }
    }

}



void LevelOrder(TreeNode *root)
{
    if(root==nullptr) return;
    queue<TreeNode *> q;
    q.push(root);
    while(!q.empty())
    {
        cout<<q.front();
        if(q.front()->left) 
            q.push(q.front()->left);
        if(q.front()->right) 
            q.push(q.front()->right); 
        q.pop();
    }
}

//深度优先遍历

void DepthOrder(TreeNode *root)
{
    if(root==nullptr) return;
    stack<TreeNode *> s;
    s.push(root);
    while(!s.empty())
    {
        TreeNode *node=s.top();
        s.pop();
        if(node->left) 
            s.push(node->left);
        if(node->right)
            s.push(node->right);

    }
}