二叉树的前序、中序、后续遍历方法

前段时间找工作，网投了很多互联网公司，中途碰了很多壁，后来每每面试一家回来就加班加点补习基础，其中滋味相信很多人都有经历。

对工作3年内的社招要求必不可少的是基本功的考验。这次有个工作年限比我稍长的同事去参加国内某互联网巨头公司面试。

笔试试卷总共就4道编程题，其中有一道就是分别实现二叉树的前序、中序和后序遍历（非递归实现）。

如果平时没有经常练习基本算法，在面试时间有限的条件很难完全准确无误地写出来。我觉得有必要自己实现一遍，因为如果拿给我，一时间也是手足无措。

网上很多关于二叉树遍历实现的代码，总结一下，前序和中序遍历都相对简单，网上的答案也大体相同。

但对于后序遍历，网上流行的一种是需要构造一个新的结构体，新结构体内包含了一个对该节点访问次数的成员。

我个人是比较排斥这种做法，这里给出了一种不需要借助新结构体来实现二叉树后序遍历的代码供参考，如下：

节点结构

typedef struct BinTree {
    int val;
    struct BinTree *left;
    struct BinTree *right;
} bintree_t;

前序遍历：

void preOrder(bintree_t *root)
{
    bintree_t *p;
    stack<bintree_t *> s;

    if (root == NULL) {
        return;
    }

    p = root;
    while (p != NULL || !s.empty()) {

        while (p != NULL) {
            printf("%d ", p->val);
            s.push(p);
            p = p->left;
        }

        if (!s.empty()) {
            p = s.top();
            s.pop();
            p = p->right;
        }
    }
}

中序遍历：

void inOrder(bintree_t *root)
{
    bintree_t *p;
    stack <bintree_t *> s;

    if (root == NULL) {
        return;
    }

    p = root;
    while (p != NULL || !s.empty()) {

        while (p != NULL) {
            s.push(p);
            p = p->left;
        }

        if (!s.empty()) {
            p = s.top();
            s.pop();
            printf("%d ", p->val);
            p = p->right;
        }
    }
}

后序遍历：

void push_leaf(stack<bintree_t *> &s, bintree_t *root)
{
    bintree_t *p, *tmp;

    p = root;
    while (p != NULL) {
        s.push(p);
        tmp = p;
        p = p->left;
        if (p == NULL) {
            p = tmp->right;
        }
    }
}

bintree_t *pop_leaf(stack <bintree_t *> &s)
{
    bintree_t *top, *top2;

    while (!s.empty()) {

        top = s.top();
        printf("%d ", top->val);
        s.pop();
        if (s.empty()) {

            return NULL;
        }

        top2 = s.top();
        if (top2->left == top
                && top2->right != NULL) {
            return top2->right;
        }
    }
}

void postOrder(bintree_t *root)
{
    stack<bintree_t *> s;
    bintree_t *p;

    if (root == NULL) {
        printf("invalid...\n");
        return;
    }

    p = root;
    while (p != NULL) {
        push_leaf(s, p);
        p = pop_leaf(s);
    }
}

已知前序和中序，构建二叉树

bintree_t *rebuildTree(int *pa, int *ia, int len)
{
    int i;
    bintree_t *proot = NULL;

    if (pa == NULL || ia == NULL || len <= 0) {
        return NULL;
    }

    proot = new bintree_t();
    proot->val = pa[0];
    proot->left = proot->right = NULL;

    printf("val = %d len = %d\n", pa[0], len);
    i = 0;
    while ((i < len) && (pa[0] != ia[i])) {
        i++;
    }

    if (i >= len) {
        printf("i = %d len = %d, invalid input!!\n", i, len);
        exit(0);
    }

    if (i > 0) {
        proot->left = rebuildTree(pa + 1, ia, i);
    }

    if (i < len - 1) {
        proot->right = rebuildTree(pa + i + 1, ia + i + 1, len - (i + 1));
    }

    return proot;
}

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <stack>
#include <exception>

using namespace std;

int main(int argc, char *argv[])
{
    bintree_t *root = NULL;

    //int pa[] = {1, 2, 4, 7, 3, 5, 6, 8};
    //int ia[] = {4, 7, 2, 1, 5, 3, 8, 6};

    //int pa[] = {1, 3, 6, 10, 13, 15, 7, 8, 12, 14, 16, 17, 20, 21, 22, 25, 26, 30, 36, 42, 40};
    //int ia[] = {13, 10, 15, 6, 3, 7, 12, 8, 14, 1, 20, 17, 21, 25, 22, 26, 16, 36, 42, 30, 40};
    int pa[] = {1, 2, 3};
    int ia[] = {2, 3, 1};

    root = rebuildTree(pa, ia, sizeof(pa) / sizeof(int));

    printf("\nPreOrder: ");
    preOrder(root);
    printf("\n");
    printf("\nInOrder: ");
    inOrder(root);
    printf("\n");

    printf("\nPostOrder: ");
    postOrder(root);
    printf("\n");

    return 0;
}