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空格空格，即可驗證本文提供的遍歷算法。

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm