C语言实现二叉树的前序、中序、后续遍历(非递归法).doc

二叉树的前序遍历、中序遍历、后续遍历（非递归法）1、前序遍历（非递归）：#include#includestruct BiTNode *stack100;struct BiTNode/定义结构体 char data; struct BiTNode *lchild,*rchild;void later(struct BiTNode *&p) /前序创建树char ch;scanf(%c,&ch);if(ch= )p=NULL;elsep=(struct BiTNode *)malloc(sizeof(struct BiTNode);p-data=ch;later(p-lchild);later(p-rchild);void print(struct BiTNode *p) /前序遍历（输出二叉树）int i=-1;while(1)while(p!=NULL)stack+i=p-rchild;/*printf(ok？n);*/printf(%c,p-data);p=p-lchild;if(i!=-1)p=stacki;i-;elsereturn;void main()/主函数struct BiTNode *p,*t;later(p);print(p);2、中序遍历（非递归）#include#includestruct BiTNode *stack100;struct BiTNode/定义结构体 char data; struct BiTNode *lchild,*rchild;void later(struct BiTNode *&p) /前序创建树char ch;scanf(%c,&ch);if(ch= )p=NULL;elsep=(struct BiTNode *)malloc(sizeof(struct BiTNode);p-data=ch;later(p-lchild);later(p-rchild);void print(struct BiTNode *p) /中序遍历（输出二叉树）int i=-1;while(1)while(p!=NULL)i+;stacki=p;p=p-lchild;if(i!=-1)p=stacki;i-;printf(%c,p-data);p=p-rchild;void main()/主函数struct BiTNode *p;later(p);print(p);3、后续遍历（非递归）：#include#includestruct BiTNode *stack100;struct BiTNode/定义结构体 char data; struct BiTNode *lchild,*rchild;void later(struct BiTNode *&p) /前序创建树char ch;scanf(%c,&ch);if(ch= )p=NULL;elsep=(struct BiTNode *)malloc(sizeof(struct BiTNode);p-data=ch;later(p-lchild);later(p-rchild);void print(struct BiTNode *p) /后序遍历（输出二叉树）int i=-1;while(1)while(p!=NULL)stack+i=p;/*printf.0(ok？n);*/p=p-lchild;if(i!=-1) while(p=stacki-rchild|(p=stacki-lchild&stacki-rchild=NULL) p=stacki-; printf(%c,p-data); if(i=-1) return; p=stacki-rchild;elsereturn;int main()/主函数struct BiTNode *p,*t;later(p);print(p);printf(n);syste