《C语言实现二叉树的前序、中序、后续遍历(非递归法).doc》由会员分享,可在线阅读,更多相关《C语言实现二叉树的前序、中序、后续遍历(非递归法).doc(5页珍藏版)》请在三一文库上搜索。
1、二叉树的前序遍历、中序遍历、后续遍历(非递归法)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(
2、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/定
3、义结构体 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=
4、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=N
5、ULL;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);system(pause);return 0;供测试使用的数据前序创建二叉树中序后序/*AB D C */BDACDBCA/*ABC D EF G */CBDAFEGCDBFGEA