遍历类型

众所周知，二叉树的遍历有三种：前序遍历、中序遍历和后序遍历。三者不同之处是访问节点的先后次序（注意该先后次序是指节点、节点左子树、节点右子树，这三部分的顺序而非每一个节点的顺序，这三部分内部的遍历顺序与外部保持一致）。三种遍历的实现依靠递归或者非递归两种。

遍历类型	遍历方式
前序遍历	中左右
中序遍历	左中右
后序遍历	左右中

所以，前中后三种遍历是指节点相对于其左孩子和右孩子的位置。

一个二叉树

如下图一个满的完全二叉树

递归实现

遍历时，遇空则返回上一级，使用下图更直接些。

null

因为4/5/6/7四个节点的左右孩子为空，所以到达空节点后会返回节点，拿节点4为例：

先遍历其左孩子发现为null,返回到4的位置

然后遍历其右孩子发现还为null返回4

4的树遍历完后返回到2的位置，开始进行2的右孩子的遍历。其他节点同理。
遍历的实际过程为：124442555213666377731
神奇的事情发生了！

先序遍历实际就是打印数值第一次出现时间，即1245367
中序遍历实际为打印数值第二次出现时间，即4251637
后序遍历实际为打印数值第三次出现时间，即4526731

观察代码你会发现，三种遍历方法的不同之处就是打印操作出现的时间！

先序遍历（中左右）：打印放前 → \rightarrow →递归左子树 → \rightarrow →递归右子树
中序遍历（左中右）：递归左子树 → \rightarrow →打印放中 → \rightarrow →递归右子树
后序遍历（左右中）：递归左子树 → \rightarrow →递归右子树 → \rightarrow →打印放后
所以，递归对于二叉树是好用的，他可以实访问一个节点三次。

非递归实现

用非递归实现二叉树时，要借用堆（stack）这个数据结构。因为递归的实质就是系统压栈出栈的过程，不使用递归则要申请一个额外的空间使用栈来实现二叉树的遍历（用队列好像也可以）。强烈建议自己动手画一遍过程！！！

先序遍历

使用一个栈stack。
先将头结点压入，再在栈不为空的前提下循环：
1.弹出栈顶元素
2.判断该节点右孩子不为空，压入该右孩子
3.判断该节点左孩子不为空，压入该左孩子（此时该值为栈顶元素），循环1的操作
故，第一步把头结点弹出，然后先压右再压左，弹出的顺序便是先弹左再弹右，符合中左右的顺序。

中序遍历

使用一个栈。
在该节点不为空或栈不为空的前提下循环：
1.节点不为空，将该节点与其左边界（左孩子的左孩子的左…）全部顺次压入栈中，直至为空。
2.节点为空，则将栈顶元素（左边界值）弹出（此时栈顶是其父节点），移至右孩子，判空后执行响应操作。

后序遍历

使用两个栈。（也可以使用一个栈）
一个栈temp用来临时存放，另一个栈用来弹出遍历结果。
先将头结点压入temp中：
1.栈temp不空，则把栈顶元素弹出当做当前节点，并压入另一个栈中，若该节点左右节点为空，则一直进行栈顶元素的弹出和压入,否则先压其左孩子再压其右孩子，直至栈空为止。
2.当要弹出遍历结果的栈不空时，一次弹出栈顶元素即为遍历结果。
一开始就把头结点压入了栈中，在temp中先压左再压右的目的就是弹出给stackpull中是以先右后左的顺序。这样就做到了弹出时按照左右中的顺序。

完整代码

#include<iostream>
#include<stack>
using namespace std;
struct Node
{
    int data;
    Node *left;
    Node *right;
    Node(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
class BinTree
{
public:
    Node *root;
    Node *CreateTree();
    void Preorder(Node *root);
    void Inorder(Node *root);
    void Postorder(Node *root);
    void Preorder2(Node *root);
    void Inorder2(Node *root);
    void Postorder2(Node *root);
};
Node* BinTree::CreateTree()
{
    Node *p1 = new Node(1);
    Node *p2 = new Node(2);
    Node *p3 = new Node(3);
    Node *p4 = new Node(4);
    Node *p5 = new Node(5);
    Node *p6 = new Node(6);
    Node *p7 = new Node(7);
    p1->left = p2; p1->right = p3;
    p2->left = p4; p2->right = p5;
    p3->left = p6; p3->right = p7;
    root = p1;
    return root;
}
/*二叉树递归遍历*/
void BinTree::Preorder(Node *root)
{
    if (root == NULL) return;
    else 
    {
        cout << root->data << "";
        Preorder(root->left);
        Preorder(root->right);
    }
}
void BinTree::Inorder(Node *root)
{
    if (root == NULL) return;
    else
    {
        Inorder(root->left);
        cout << root->data << "";
        Inorder(root->right);
    }
}
void BinTree::Postorder(Node *root)
{
    if (root == NULL) return;
    else
    {
        Postorder(root->left);
        Postorder(root->right);
        cout << root->data << "";
    }
}
/*二叉树非递归遍历*/
void BinTree::Preorder2(Node *root)
{
    if (root == NULL) return;
    else
    {
        stack<Node*> stack;
        stack.push(root);
        while (!stack.empty())
        {
            root = stack.top();
            cout << root->data << "";
            stack.pop();//stack.top()可以给root而stack.pop()却不能？？
            if (root->right != NULL)
                stack.push(root->right);
            if (root->left != NULL)
                stack.push(root->left);
        }
    }
    cout << endl;
}
void BinTree::Inorder2(Node *root)
{
    if (root == NULL) return;
    else
    {
        stack<Node*> stack;        
        while (!stack.empty() || root != NULL)
        {
            if (root != NULL)
            {
                stack.push(root);
                root = root->left;
            }
            else
            {
                root = stack.top();
                cout << root->data << "";
                stack.pop();
                root = root->right;
            }
        }
    }
    cout << endl;
}
void BinTree::Postorder2(Node *root)
{
    if (root == NULL) return;
    else
    {
        stack<Node*> stacktemp;
        stack<Node*> stackpull;
        stacktemp.push(root);
        while (!stacktemp.empty())
        {
            root = stacktemp.top();
            stacktemp.pop();
            stackpull.push(root);
            if (root->left != NULL)
                stacktemp.push(root->left);
            if (root->right != NULL)
                stacktemp.push(root->right);
        }
        while (!stackpull.empty())
        {
            root = stackpull.top();
            cout << root->data << "";
            stackpull.pop();
        }
    }
    cout << endl;
}
int main()
{
    BinTree tree;
    tree.CreateTree();
    cout << "********二叉树递归遍历********";
    cout << endl;
    cout << "先序递归结果：";
    tree.Preorder(tree.root);    
    cout << endl;
    cout << "中序递归结果：";
    tree.Inorder(tree.root);    
    cout << endl;
    cout << "后序递归结果：";    
    tree.Postorder(tree.root); 
    cout << endl;
    cout << "********二叉树非递归遍历********";
    cout << endl;
    cout << "先序非递归结果：";
    tree.Preorder2(tree.root);
    cout << "中序非递归结果：";
    tree.Inorder2(tree.root);
    cout << "后序非递归结果：";
    tree.Postorder2(tree.root);
    return 0;
}