二叉树的遍历（先序中序后序）

二叉树的遍历可以通过递归或不递归

二叉树的创建：

定义节点结构体：

struct TreeNode
{
    int val;
    struct TreeNode * left;
    struct TreeNode * right;
    TreeNode(int x) :                       //这两行是用来初始化的
        val(x), left(NULL), right(NULL) {

    }
};

创建二叉树：

struct TreeNode * CreateBTree()         //动态地建了一个二叉树，有返回值，返回根节点的地址
{
    TreeNode* Head = new TreeNode(1);
    Head->left = new TreeNode(2);
    Head->right = new TreeNode(3);
    Head->left->left= new TreeNode(4);
    Head->left->right = new TreeNode(5);
    Head->right->left = new TreeNode(6);
    Head->right->right = new TreeNode(7);

    return Head;

}

一、递归遍历

可以总结成一个递归序，每一个节点都会经过三次（它1->它左->回到它2->它右->回到它3），先序中序后序就是在不同时候经过它的时候进行打印------------------先序是第一次经过就打印；中序是第二次经过再打印，后序是最后一次经过再打印
（以遍历到NULL作为递归的结束）
###1、先序
先访问根节点
再先序访问左子树
再先序访问右子树

   void PreTraverseBTree(struct TreeNode * pT)
    {
        if (pT != NULL)
        {
           cout<< pT->val<<" ";
           if (NULL != pT->left)          //如果左子树是空的话就不需要再访问了，可以提高效率
           {
               PreTraverseBTree(pT->left);
           }
           if (NULL != pT->left)
           {
               PreTraverseBTree(pT->right);
           }
        }
    }

2、中序

先中序访问左子树
再访问根节点
再中序访问右子树

    void InTraverseBTree(struct TreeNode* pT)
    {
        if (pT != NULL)
        {
            if (NULL != pT->left)
            {
                InTraverseBTree(pT->left);
            }
            cout << pT->val << " ";
            if (NULL != pT->left)
            {
                InTraverseBTree(pT->right);
            }
        }
    }

3、后序

先后序访问左子树
再后序访问右子树
再访问根节点

  void PostTraverseBTree(struct TreeNode* pT)
    {
        if (pT != NULL)
        {
            if (NULL != pT->left)
            {
                PostTraverseBTree(pT->left);
            }
            if (NULL != pT->right)
            {
                PostTraverseBTree(pT->right);
            }
            cout << pT->val <<" ";
        }
    }

非递归遍历（可以利用压栈弹出的思想）

其实递归里面也是利用栈，只是它在内部自己实现，我们不知道而已；非递归就是我们自己做一个栈进行迭代
###1、先序
思想：
1、申请一个栈，把头压进去
2.只要栈不为空就进行如下操作：弹出并打印；将弹出的右节点压进栈，再把左节点压进栈
记忆方法：弹出打印->先右后左
图片说明

 void PreUnRecur(struct TreeNode* pHead)
    {
        stack<TreeNode*> stack1;
        stack1.push(pHead);         //头先入栈
        while (!stack1.empty())     //栈不为空时
        {
            pHead = stack1.top();
            stack1.pop();                //弹出
            cout << pHead->val << " ";    //打印
            if (pHead->right != NULL)     //把右边压进栈
            {
                stack1.push(pHead->right);
            }
            if (pHead->left!= NULL)       //把左边压进栈
            {
                stack1.push(pHead->left);
            }
        }
    }

2、后序

思想：
与先序类似，不同地方在于：弹出不打印，而是用另一个栈保存起来；压栈顺序是先左再右
1.申请两个栈，栈1和先序一样用来遍历数，栈2用来收集栈1弹出的节点
2.头结点压进栈1
3.只要栈1不为空，就进行如下操作：弹出，并用栈2进行收集，将弹出的左节点压如栈，再把右节点压如栈
记忆方法：弹出收集，先左后右
图片说明

  void PostUnRecur(struct TreeNode* pHead)
    {
        stack<TreeNode*> stack1;           //用来做遍历栈
        stack<TreeNode*> stack2;           //用来收集stack1弹出来的东西
        stack1.push(pHead);                //头先入栈
        while (!stack1.empty())            //栈1不为空时
        {
            pHead = stack1.top();
            stack1.pop();
            stack2.push(pHead);
            if (pHead->left != NULL)
            {
                stack1.push(pHead->left);
            }
            if (pHead->right != NULL)
            {
                stack1.push(pHead->right);
            }
        }
        while (!stack2.empty())
        {
            pHead = stack2.top();
            stack2.pop();
            cout << pHead->val<<" ";
        }

    }

3、中序

中序与前面不太一样，不用先把头压进栈
思想：
只要栈不为空或者节点不为空就进行如下操作：
如果节点不为空：把它所有的左边界都压进栈
否则，对栈进行操作：弹出->打印->去右边节点
图片说明

    void InUnRecur(struct TreeNode* pHead)
    {
        stack<TreeNode*> stack1;
        while (pHead != NULL || !stack1.empty())         //停止条件：栈为空并且节点为空
        {
            if (pHead != NULL)                 //只要节点不为空我就把左边全部压进栈
            {
                stack1.push(pHead);
                pHead = pHead->left;
            }
            else                             //节点为空了，开始弹出-》打印-》去右边
            {
                pHead = stack1.top();
                stack1.pop();
                cout << pHead->val<<" ";
                pHead = pHead->right;
            }
        }

    }

我总结了一下记忆方法：
先序：弹出打印，先右后左
后序：弹出收集，先左后右
中序：左全压栈，弹出打印去右边