[数据结构]用栈前序遍历树
对这篇文章的来源性说明：理论和代码来源，《系统设计师教程》（王春森主编），文章内容来自我对书中代码的分析和手工注释。（ 本文献给小师妹：littlehead（我是大好人））
[bo]名词：栈，遍历，前序遍历，树。[/bo]
（1）准备：树的定义省略。但是由于数的定义属于递归型定义，即树的每个子节点又是一棵树，所以这个递归型的定义使对树的很多操作通常都可以用递归算法来实现。对数节点的定义，一个节点含有一个数据，这里以一个字符数据作为示范，假设一个节点最多含有M个子节点（M成为树的次数），则节点定义为：
typedef struct tnode
{
char data;
struct tnode *child[M];
} TNODE;
我们对用根节点指针来持有和处理一棵树：即：
TNODE *root;
前序遍历和后序遍历：遍历值得是依次输出所有节点数据。前序后序中的序指的是本节点和其子节点之间的输出顺序关系。对于普通树来说存在前序，后序两种遍历。对二叉树来说又有中序遍历。
（2）我们先给出前序遍历的伪码为：
void pre_order(TNODE *t, int m) //m为数次数
{
if(t!=NULL) 打印t； //先输出本节点
for(i=0;i<m;i++)
pre_order(t->child[i],m); //前序输出所有子节点
}
/*--------------------------------
root-> 1
/ | \
2 3 4
/ \ |
5 6 7
/ \
8 9
----------------------------------*/
对于图1所示的树，则其前序遍历和后序遍历如下：
前序：1，2，5，6，3，4，7，8，9；
后序：5，6，2，3，8，9，7，4，1；
（3）采用栈来代替递归函数的方法如下：
方法：每出栈一个节点，打印该节点，然后则将其所有子节点逆序（从右到左）入栈。
初始栈状态：根节点入栈。栈中仅有根节点。栈顶指针top=1；
结束条件：栈为空。即栈顶指针top=0；
其相关代码如下
程序代码：
/*使用栈前序遍历树*/
#define M 10 /*树的次/度：最大子节点数*/
#define SN 100 /*栈最大深度*/
typedef struct tnode
{
char data;
struct tnode *child[M];
}TNODE;
/*t-root; m-度*/
void pre_order(TNODE *t,int m)
{
TNODE *s[SN];/*定义栈*/
int top=0,i;/*top-栈顶指针；*/
if(t==NULL)
return;
s[top++]=t;/*根节点入栈*/
while(top>0) /*当栈不为空时：*/
{
t=s[--top];/*取出栈顶节点并打印输出该节点*/
printf("%c ",t->data);
/*将当前节点的子节点按逆序入栈*/
for(i=m-1;i>=0;i--)
{
if(t->child[i])
s[top++]=t->child[i];
}
}
}，遍历时的栈中节点状态如图2所示（蓝色箭头表示栈顶，每一行表示栈在当前的一个状态。）。
[[it] 本帖最后由 hoodlum1980 于 2008-3-20 23:11 编辑 [/it]]
