二叉树的前序、中序、后序及层次遍历的递归与非递归源码实现

二叉树是基本却非常重要的数据结构，经常在面试中出现，现在我主要是针对面试中出现比率非常高的前序、中序、后序及层次遍历，给出自己的递归与非递归实现，源码仅供参考。
另外，如果觉得我写的好，可以关注我的github帐号(https://github.com/chenqiangzhishen). 本文代码部分我也贴在了如下的目录中。
(https://github.com/chenqiangzhishen/Algorithms/blob/master/binaryTree/binaryTree.c)
有了github，我会经常更新些新的，高效的，经典的算法和其他新的知识与大家分享，开源快乐～

注：我的代码不出意外，都可以直接运行，采用gcc/g++/gdb进行的开发与调试工具及vim开发工具。
因为比较喜欢在Linux下编程，不大喜欢用中文切来切去的进行描述，所以直接采用英文进行注释。

#include <stdio.h>
#include <stdlib.h>
#define MAX 100
typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
BiTNode* stack[MAX];

BiTree createBiTree(void)
{
    int data;
    BiTNode *root = NULL;
    scanf("%d", &data);

    if(data == -1)
    {
        root = NULL;
    }
    else
    {
        root = (BiTNode *)malloc(sizeof(BiTNode));
        root->data = data;
        root->lchild = createBiTree();
        root->rchild = createBiTree();
    }
    return root;
}

void preOrderTraverse(BiTree root)
{
    if(root == NULL)
        return;
    printf("%d ", root->data);
    preOrderTraverse(root->lchild);
    preOrderTraverse(root->rchild);
}


void inOrderTraverse(BiTree root)
{
    if(root == NULL)
        return;
    inOrderTraverse(root->lchild);
    printf("%d ", root->data);
    inOrderTraverse(root->rchild);
}

void postOrderTraverse(BiTree root)
{
    if(root == NULL)
        return;
    postOrderTraverse(root->lchild);
    postOrderTraverse(root->rchild);
    printf("%d ", root->data);
}

void preOrderTraverse_none_recursive(BiTree root)
{
    if(root == NULL)
        return;
    int top = 0;
    while(root || top>0)
    {
        while(root)
        {
            printf("%d ", root->data);
            stack[top++] = root;
            root = root->lchild;
        }
        root = stack[--top];
        root = root->rchild;
    }
    printf("
");
}

void inOrderTraverse_none_recursive(BiTree root)
{
    if(root == NULL)
        return;
    int top = 0;
    while(root || top>0)
    {
        while(root)
        {
            stack[top++] = root;
            root = root->lchild;
        }
        root = stack[--top];
        printf("%d ", root->data);
        root = root->rchild;
    }
    printf("
");
}

void postOrderTraverse_none_recursive(BiTree root)
{
    if(root == NULL)
        return;
    BiTNode *visited = NULL;
    int top = 0;
    while(root || top>0)
    {
        while(root)
        {
            stack[top++] = root;
            root = root->lchild;
        }
        root = stack[top -1];
        //if do not have right child or the right child is visited, then visit the parent(root) node.
        if(root->rchild==NULL || visited==root->rchild)
        {
            printf("%d ", root->data);
            visited = root;
            --top;
            root = NULL;//note that: let the node become NULL
        }
        else
        {
            root = root->rchild;
        }
    }
    printf("
");
}

void levelTraverse(BiTree root)
{
    if(root == NULL)
        return;
    BiTNode* p = NULL;
    int top = 0;
    int beg = 0;
    stack[top++] = root;
    int end = top;
    while(beg < end)
    {
        while(beg < end)
        {
            p = stack[beg++];
            printf("%d ", p->data);
            if(p->lchild)
                stack[top++] = p->lchild;
            if(p->rchild)
                stack[top++] = p->rchild;
        }
        end = top;
    }
}

int main(void)
{

    printf("please input the data to create binary tree, input -1 to exit
");
    BiTree root = createBiTree();
    printf("The binary tree is:
");

    printf("The preOrderTraverse is:
");
    preOrderTraverse(root);
    printf("
");
    printf("The inOrderTraverse is:
");
    inOrderTraverse(root);
    printf("
");
    printf("The postOrderTraverse is:
");
    postOrderTraverse(root);
    printf("
");
    printf("The preOrderTraverse with none recursive is:
");
    preOrderTraverse_none_recursive(root);
    printf("The inOrderTraverse with none recursive is:
");
    inOrderTraverse_none_recursive(root);
    printf("The postOrderTraverse with none recursive is:
");
    postOrderTraverse_none_recursive(root);
    printf("The level traverse for binary tree is:
");
    levelTraverse(root);
    printf("
");
    return 0;
}