先用先序输入二叉树

1、先用先序输入二叉树,在对二叉树逬行先序遍历,进行中序遍历。includestdio.hincludestdlib.h#define OVERFLOW -2#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct BiTNode二叉树的二叉链表存储表示。char data;struct BiTNode *lchild,*rchild; 左右孩子指针。BiTNode,*BiTree;栈的顺序存储表示。栈底指针。栈

2、的顺序存储表示。栈底指针。栈顶指针。初始化。BiTree *base;BiTree *top;int stacksize;SqStack;int InitStack(SqStack &s)s.base=但iTree *)malloc(STACK_INIT_SIZE*sizeof(BiTree); if(!s.base) exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;return OK;int StackEmpty(SqStack s)if(s.base=s.top)return TRUE;elsereturn FALSE;int

3、 Push(SqStack &szBiTree T)入栈。if(s.top-s.base)=s.stacksize)s.base=(BiTree *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(BiTree);if(!s.base) exit(OVERFLOW);s.top=s.base+s.stacksize; s.stacksize+=STACKINCREMENT;*s.top+=T;return OK;int Pop(SqStack BiTree &T)出栈。if(s.top=s.base)return ERROR;T=*-s.t

4、op;/ printf(”出栈的数:”);/ printf(%c,T-data);return OK;int GetTop(SqStack s,BiTree &T)if(s.top=s.base)return ERROR;T=*(s.top-1);return OK;int CreateBiTree(BiTree &T)按先序次序输入二叉树中结点的值(一个字符),空字符串表示空树。char ch;scan f(“c：&ch);if(ch=)T=NULL；elseif(!仃=(B iTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=ch;Cre

5、ateBiTree(T-lchild);CreateBiTree(T-rchild);return OK;int Visit(char e)/ Visit 函数输出。printf(%c,e);return OK;int PreOrderTraverse(BiTree T,int(*Visit)(char e)先序遍历。if(T)if(Visit (T-data)if( PreOrderT raverse(T- Ichild, Visit)if(PreOrderT raverse(T- rchild,Visit) return OK;return ERROR;elsereturn OK;int InOrderTraverse(BiTree Tzint(*Visit)(char e)中序遍历。BiTree p;SqStack s;p=(B iTNode*)malloc(sizeof(BiTNode);InitStack(s);Push(szT);while(!StackEmpty(s)while(GetTop(s,p)&p)Push(s,p-lchild);Pop(s,p)；if(!StackEmpty )Pop p)；if(!Visit(p-data)return ERROR;Push(s,p-rchild);return OK;void main()BiTree T;prin