#include "stdio.h"#include "stdlib.h"#define STACK_INIT_SIZE 100 //栈存储空间初始分配量#define STACKINCREMENT 10 //存储空间分配增量//------二叉树的存储结构表示------//typedef struct BiTNode{int data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;//-----顺序栈的存储结构表示------//typedef struct{BiTree *top;BiTree *base;int stacksize;}SqStack;//***************************************************//构造一个空栈sSqStack *InitStack();//创建一颗二叉树BiTree CreatBiTree();//判断栈空int StackEmpty(SqStack *S);//插入元素e为新的栈顶元素void Push(SqStack *S,BiTree p);//若栈不为空，则删除s栈顶的元素e，将e插入到链表L中void Pop(SqStack *S,BiTree *q);//非递归先序遍历二叉树void PreOrderTraverse(BiTree L);//非递归中序遍历二叉树void InOrderTraverse(BiTree L);//非递归后序遍历二叉树void PostOrderTraverse(BiTree L);//递归后序遍历二叉树void PostOrder(BiTree bt);//递归中序遍历二叉树void InOrder(BiTree bt);//递归先序遍历二叉树void PreOrder(BiTree bt);//***************************************************int main(){BiTree bt;int n,k;printf("Creat Tree and the end with '.' \n");bt=CreatBiTree(); //创建二叉树do{printf("1.PreOrderTraverse 2.InOrderTraverse 3.PostOrderTraverse 4.PostOrder 5.InOrder 6.PreOrde\n");printf("please input a num to n:");scanf("%d",&n);switch(n){case 1: PreOrderTraverse(bt);printf("\n");break; //先序遍历非递归算法case 2: InOrderTraverse(bt);printf("\n");break; //中序非递归遍历算法case 3: PostOrderTraverse(bt);printf("\n"); break; //后序非递归遍历算法case 4: PostOrder(bt);printf("\n");break; //后序递归遍历算法case 5: InOrder(bt);printf("\n");break; //中序递归遍历算法case 6: PreOrder(bt);printf("\n");break; //先序递归遍历算法}printf("if you want to continue,please input a num>0 to k:");scanf("%d",&k);}while(k>0);return 0;}SqStack *InitStack(){ //构造一个空栈SSqStack *S;S=(SqStack *)malloc(sizeof(SqStack));S->base=(BiTree *)malloc(STACK_INIT_SIZE*sizeof (BiTree));S->top=S->base;S->stacksize =STACK_INIT_SIZE;return S;}BiTree CreatBiTree(){ //先序方式递归方式建立一个二叉树char k;BiTree T;k=getchar();if(k=='.')T=NULL;else{T=(BiTNode *)malloc(sizeof(BiTNode));T->data=k;T->lchild=CreatBiTree();T->rchild=CreatBiTree();}return T;}void Push(SqStack *S,BiTree p){ //插入二叉树p的结点地址为栈顶的新元素if(S->top-S->base>=S->stacksize){S->base=(BiTree*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(BiTree));S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;}*S->top=p;S->top++;}void Pop(SqStack *S,BiTree *q){ //二叉树q的结点地址出栈返回，做为新二叉树的当前地址if(S->base==S->top)exit(0);S->top--;*q=*S->top;}int StackEmpty(SqStack *S){// 若栈S为空栈，则返回1，否则返回0if(S->top == S->base)return 1;elsereturn 0;}void PreOrderTraverse(BiTree L){ //非先序遍历二叉树BiTree T;SqStack *S;S=InitStack();T=L;while(!StackEmpty(S)||T!=NULL){if(T!=NULL){printf("%c",T->data);Push(S,T);T=T->lchild;} //根指针进栈，遍历左子树else{ //根指针退栈，访问根结点，遍历右子树Pop(S,&T);T=T->rchild;}}}void InOrderTraverse(BiTree L){ //非先序遍历二叉树BiTree T;SqStack *S;S=InitStack();T=L;while(!StackEmpty(S)||T!=NULL){if(T!=NULL){Push(S,T);T=T->lchild;} //根指针进栈，遍历左子树else{ //根指针退栈，访问根结点，遍历右子树Pop(S,&T);printf("%c",T->data);T=T->rchild;}}}void PostOrderTraverse(BiTree L){//非后序遍历二叉树BiTree T;SqStack *S;S=InitStack();T=L;while(!StackEmpty(S)||T!=NULL){if(T!=NULL){Push(S,T);T=T->lchild;} //根指针进栈，遍历左子树else{ //根指针退栈，访问根结点，遍历右子树Pop(S,&T);printf("%c",T->data);T=T->rchild;}}}void PostOrder(BiTree bt){if(bt==NULL)return;PostOrder(bt->lchild);PostOrder(bt->rchild);printf("%c",bt->data);}void InOrder(BiTree bt){if(bt==NULL)return;InOrder(bt->lchild);printf("%c",bt->data);InOrder(bt->rchild);}void PreOrder(BiTree bt){if(bt==NULL)return;printf("%c",bt->data);PreOrder(bt->lchild);PreOrder(bt->rchild); }。