Question

二叉树中序遍历非递归算法(c语言实现）

要求用到栈的相关知识，包括栈的建立，什么什么的。
写出全部的过程源代码。
明早要交的作业，哪个给我写好了再加20分

Answer 1

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define null 0

struct node
{
char data;
struct node *lchild;
struct node *rchild;
};

//先序，中序 建树
struct node *create(char *pre,char *ord,int n)
{
struct node * head;
int ordsit;

head=null;
if(n<=0)
{
return null;
}
else
{
head=(struct node *)malloc(sizeof(struct node));
head->data=*pre;
head->lchild=head->rchild=null;
ordsit=0;
while(ord[ordsit]!=*pre)
{
ordsit++;
}
head->lchild=create(pre+1,ord,ordsit);
head->rchild=create (pre+ordsit+1,ord+ordsit+1,n-ordsit-1);
return head;
}
}

//中序递归遍历
void inorder(struct node *head)
{
if(!head)
return;
else
{
inorder(head->lchild );
printf("%c",head->data );
inorder(head->rchild );
}
}

//中序非递归遍历

void inorder1(struct node *head)
{
struct node *p;
struct node *stack[20];
int top=0;

p=head;
while(p||top!=0)
{
while (p)
{
stack[top++]=p;
p=p->lchild ;
}
p=stack[--top];
printf("%c ",p->data );
p=p->rchild ;
}
}

//主函数
int main()
{
struct node * head;
char pre[30],ord[30];
int n;

gets(pre);
gets(ord);
n=strlen(pre);
head=create(pre,ord,n);
inorder(head);
printf("\n");
inorder1(head);
printf("\n");
}

//测试事例；
/*
-+a*b%cd/ef
a+b*c%d-e/f
*/

几个月前自己编写，原版
vc++ 6.0实验通过

怎么样，老板，第一次上百度知道，好激动
给点面子
给分！给分啊