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（"请按先序次序输入二叉树中结点的值（字符），空格字符表示空树: "）;
CreateBiTree（T）;    printf（"先序遍历结果为:"）;
PreOrderTraverse（T）;
printf（" "）; printf（"中序遍历结果为:"）;
InOrderTraverse（T）;
printf（" "）; printf（"后序遍历结果为:"）;
PostOrderTraverse（T）;
printf（" "）;    printf（"层序遍历结果为:"）;
LevelOrderTraverse（T）;
printf（" "）; 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本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-02/113460.htm