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