C语言二叉树非递归遍历

显示全部楼层 · 2010-4-9 21:43:05

我们今天讲了一点我写了下函数部分。。其实我也不太懂！void PreOrderTraverse(struct tree *p)/*进行先序遍历*/{ top=0;
bool; do{
while(p)
{
s[top]=p;
top++;
p=p->lch;
top--;
if(top==0)
bool=0;
else{
top--;
p=s[top];
printf(p->data);
p=p->rch;
}}while(bool)}void InOrderTraverse(struct tree *p)/*进行中序遍历*/{ top=0; bool; do{
while(p)
{
s[top]=p;
top++;
p=p->lch;
if(top==0)
bool=0;
else{
top--;
p=s[top];
printf(p->data);
p=p->rch;
}}while(bool)}后序遍历我也不怎么会写！不过我可以给你说一下原理：先是一个p->data入栈，入栈的时候给它标记下，用i=1记一下，然后是他的左子树，p=p->lch;p->data要出栈，这时候做一次判断。看P的标记i是多少，是1的话就不让他出来，返回去并且i+1，变成2；然后继续前面的动作!等到第二次出栈时做同样的判断，i=2，就出栈！并输出！！希望对你有所帮助！

千问 · 2010-4-9 21:43:05

汗，兄弟，非递归算法你在网上一搜遍地都是，数据结构课程必讲的~

千问 · 2010-4-9 21:43:05

难为我了