C语言非递归实现二叉树的先序、中序、后序、层序遍历

C语言非递归实现二叉树的先序、中序、后序、层序遍历代码如下：

#include <stdio.h>   
#include <stdlib.h> 
#include <stack>
#include <queue>
using namespace std;

//*****二叉树的二叉链表存储表示*****//   
typedef struct BiNode   
{   
    char data;   
    struct BiNode *lchild, *rchild;
    int visitCount;
}BiNode, *BiTree;   

//*****按先序次序输入二叉树中结点的值(一个字符)，空格字符表示空树构造二叉链表表示的二叉树T*****//   
void CreateBiTree(BiTree &T)           
{                                     
    char ch;   
    scanf("%c", &ch);   
    if(ch == ' ')   
    {   
        T = NULL;   
    }   
    else   
    {   
        if(!(T = (BiNode *)malloc(sizeof(BiNode))))   
        {   
            return;   
        }   
        T->data = ch;                            //生成根结点   
        T->lchild = NULL;
        T->rchild = NULL;
        CreateBiTree(T->lchild);                //构造左子树   
        CreateBiTree(T->rchild);                //构造右子树   
    }   

    return;   
}   

//*****先序遍历二叉树*****//   
void PreOrderTraverse(BiTree T)   
{   
    stack<BiTree> TreeStack;
    BiTree p = T;

    while (p || !TreeStack.empty())
    {
        if (p)
        {
            printf("%c ", p->data);
            TreeStack.push(p);
            p = p->lchild;
        }
        else
        {
            p = TreeStack.top();
            TreeStack.pop();
            p = p->rchild;
        }
    }
}   

//*****中序遍历二叉树*****//   
void InOrderTraverse(BiTree T)   
{   
    stack<BiTree> TreeStack;
    BiTree p = T;

    while (p || !TreeStack.empty())
    {
        if (p)
        {
            TreeStack.push(p);
            p = p->lchild;
        }
        else
        {
            p = TreeStack.top();
            printf("%c ", p->data);
            TreeStack.pop();
            p = p->rchild;
        }
    }
}   

//*****后序遍历二叉树*****//   
void PostOrderTraverse(BiTree T)   
{   
    stack<BiTree> TreeStack;
    BiTree p = T;

    while (p || !TreeStack.empty())
    {
        if (p)
        {
            p->visitCount = 1;
            TreeStack.push(p);
            p = p->lchild;
        }
        else
        {
            p = TreeStack.top();
            TreeStack.pop();
            if (p->visitCount == 2)
            {
                printf("%c ", p->data);
                p = NULL;
            }
            else
            {
                p->visitCount++;
                TreeStack.push(p);
                p = p->rchild;
            }
        }
    }
} 

//*****层序遍历二叉树*****//
void LevelOrderTraverse(BiTree T)
{
    if (!T)
    {
        return;
    }

    queue<BiTree> TreeQueue;
    TreeQueue.push(T);
    BiTree p = T;
    while (!TreeQueue.empty())
    {
        p = TreeQueue.front();
        TreeQueue.pop();
        printf("%c ", p->data);

        if (p->lchild)
        {
            TreeQueue.push(p->lchild);
        }
        if (p->rchild)
        {
            TreeQueue.push(p->rchild);
        }
    }
}

int main(void)   
{   
    BiTree T;       
    printf("请按先序次序输入二叉树中结点的值(字符)，空格字符表示空树:\n");   
    CreateBiTree(T);       

    printf("先序遍历结果为:");   
    PreOrderTraverse(T);   
    printf("\n\n");   

    printf("中序遍历结果为:");   
    InOrderTraverse(T);   
    printf("\n\n");   

    printf("后序遍历结果为:");   
    PostOrderTraverse(T);       
    printf("\n\n");     

    printf("层序遍历结果为:");   
    LevelOrderTraverse(T);       
    printf("\n\n");

    return 0;       
}

以如下二叉树为例，给出按先序次序输入二叉树中结点的值（字符），从而按照本文给出的算法构造二叉树。

输入字符的顺序是：-+a空格空格*b空格空格-c空格空格d空格空格/e空格空格f空格空格，即可验证本文提供的遍历算法。