二叉树遍历的非递归实现

二叉树的非递归实现需要使用到下推栈，下面给出前序遍历的完整代码：#include <stdio.h>
#include <stdlib.h>
#define MAX 10
//二叉树存储结构定义
typedef char Item;
typedef struct node *link;
struct node {Item item; link l, r;};int Create（link *tp）;
void show（link h）;
void tranverse（link h, void （*visit）（link））;//下推栈存储结构定义
typedef link SItem;
static SItem *s;
static int N;void STACKinit（int maxN）;
int STACKempty（）;
void STACKpush（SItem item）;
SItem STACKpop（）;
int main（）
{
link tree; Create（&tree）;
tranverse（tree, show）; return 0;
}void STACKinit（int maxN）
{
s = （SItem *）malloc（maxN * sizeof（SItem））;
if （！s） return;
N = 0;
}int STACKempty（）
{
return N==0;
}void STACKpush（SItem item）
{
s[N++] = item;
}SItem STACKpop（）
{
return s[--N];
}int Create（link *tp）
{
//构造方法，或者说构造顺序：中序遍历构造
char x;
scanf（"%c",&x）;
if（x=="#"）
{
*tp=NULL;//指针为空，树节点中的某个指针为空
return 0;
}
*tp=（link）malloc（sizeof（**tp））;//将树节点中指针指向该地址空间
if（*tp==NULL）
return 0;
（*tp）->item=x;
Create（&（（*tp）->l））;
Create（&（（*tp）->r））;
return 1;
}void show（link h）
{
printf（" %c ", h->item）;
}//前序遍历
void tranverse（link h, void （*visit）（link））
{
STACKinit（MAX）;
STACKpush（h）;
while （！STACKempty（））{
（*visit）（h = STACKpop（））;
if （h->r ！= NULL） STACKpush（h->r）;
if （h->l ！= NULL） STACKpush（h->l）;
}
}二叉树的常见问题及其解决程序 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-03/114488.htm