- #include "stdafx.h"
- #include "malloc.h"
- #define M 100
- typedef struct tree
- {
- char data;
- struct tree *lchild;
- struct tree *rchild;
- }bitree,*linktree;
- linktree createtree()
- {
- char ch;
- linktree bt;
- scanf("%c",&ch);
- if(ch=='.') //为‘.’时结束
- return NULL;
- else
- {
- bt=(linktree)malloc(sizeof(bitree));
- bt->data=ch;
- bt->lchild=createtree();
- bt->rchild=createtree();
- }
- return bt;
- }
- void preorder(linktree bt)
- {
- linktree stack[M]; //定义一维数字stack[M]作为栈
- int top=0;
- while(bt)
- {
- while(bt) //搜索到最左树
- {
- printf("%c",bt->data); //输出结点
- stack[top++]=bt;
- bt=bt->lchild; //搜索左树
- }
- while(top>0)
- {
- bt=stack[--top];
- bt=bt->rchild; //搜索右树
- if(bt) //若存在右树,跳出该循环
- break;
- }
- }
- }
- void inorder(linktree bt)
- {
- linktree stack[M]; //定义一维数字stack[M]作为栈
- int top=0;
- while(bt)
- {
- while(bt)
- {
- stack[top++]=bt;
- bt=bt->lchild;
- }
- while(top>0)
- {
- bt=stack[--top];
- printf("%c",bt->data);
- bt=bt->rchild;
- if(bt)
- break;
- }
- }
- }
- /*后序遍历时,当指针第一次指向某一结点的时候,不能立即访问,要将该结点入栈,然后遍历该节点的左树,当左树遍历完毕再次搜索到该节点的时候,还不能立即访问,要将节点入栈,接着遍历右树,左右树都遍历完毕,第三次遇到该节点的时候,才将该节点出栈并访问。所以附加了一个栈s用来记录节点的访问次数,设定标志值为0时该节点首次入栈,为1时第二次入栈*/
- void postorder(linktree bt)
- {
- linktree stack[M];
- int top=0,flag,s[M]; //s[]为标志结点入栈次数
- do{
- while(bt!=NULL)
- {
- stack[top]=bt;
- s[top++]=0;
- bt=bt->lchild;
- }
- if(top>0)
- {
- flag=s[--top];
- bt=stack[top];
- if(flag==0)
- {
- stack[top]=bt;
- s[top++]=1; //第二次入栈
- bt=bt->rchild; //遍历右树
- }
- else
- {
- printf("%c",bt->data); //第3次遇到该节点,输出该节点
- bt=NULL;
- }
- }
- }while(top>0);
- }
- void main()
- {
- linktree bt;
- bt=createtree(); //递归创建二叉树
- printf("先序遍历:");
- preorder(bt);
- printf("\\n中序遍历:");
- inorder(bt);
- printf("\\n后序遍历:");
- postorder(bt);
- }
- //该片段来自于http://www.codesnippet.cn/detail/130120148496.html
来源: http://www.codesnippet.cn/detail/130120148496.html