2月4号作业

 编写程序实现二叉树的创建，三种遍历自己销毁

#include <myhead.h>#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
#define OK 1
#define ERROR 0#define INIT_SIZE 20
#define INCREMENT_SIZE 5typedef int Status;
typedef int TElemType;
//存储结构typedef struct BiNode{TElemType data;struct BiNode *lchild, *rchild;
}BiNode, *BiTree;typedef enum {Travel = 1,Visit = 0}TaskType;typedef struct{BiTree ptr;TaskType task;
}SElemType;typedef struct{SElemType *top;SElemType *base;int size;
}Stack;//栈的数据结构
//初始化栈
Status InitStack(Stack *S)
{S->base = (SElemType *)malloc(sizeof(SElemType)*INIT_SIZE);if(!S->base)exit(OVERFLOW);S->top = S->base;S->size = INIT_SIZE;return OK;
}//判断是否为空
Status IsEmpty(Stack S){if(S.base==S.top)return TRUE;return FALSE;}
//进入栈Status Push(Stack *S,SElemType e)//*S->top++=e{if((S->top - S->base) / sizeof(SElemType)>=S->size){S->base = (SElemType*)realloc(S->base,(S->size+INCREMENT_SIZE)*sizeof(SElemType));if(!S->base)exit(OVERFLOW);S->top = S->base + S->size;//从新申请了内存地址发生了变化S->size += INCREMENT_SIZE;}*S->top = e;//先取*s->top 在++//*++S->top先加再取值；S->top++;return OK;}//pop
Status Pop(Stack *S, SElemType *e)
{if(S->top == S->base)return ERROR;*e = *--S->top;return OK;}//创建二叉树(输入0结束）
Status CreateBiTree(BiTree *T)
{TElemType s;scanf("%d",&s);if(s==0)*T=NULL;else{*T = (BiTree)malloc(sizeof(BiNode));if(!T){return OVERFLOW;}(*T)->data = s;CreateBiTree(&(*T)->lchild);//修改指针的值使其指向创建的值CreateBiTree(&(*T)->rchild);}return OK;
}
//访问元素
void visit(TElemType e)
{printf("%d ",e);}
//先序遍历递归实现
Status PreOrderTraverse(BiTree T,void(*visit)(TElemType e))
{if(T){(*visit)(T->data);PreOrderTraverse(T->lchild,visit) ;PreOrderTraverse(T->rchild,visit);}}//中序遍历Status InOrderTraverse(BiTree T,void(*visit)(TElemType e))
{if(T){InOrderTraverse(T->lchild,visit);(*visit)(T->data);InOrderTraverse(T->rchild,visit);}}// houxuStatus PostOrderTraverse(BiTree T,void(*visit)(TElemType e))
{if(T){PostOrderTraverse(T->lchild,visit);PostOrderTraverse(T->rchild,visit);(*visit)(T->data);}}//前序遍历非递归
Status  PreOrder(BiTree T,void(*visit)(TElemType e))
{Stack S;InitStack(&S);BiTree p;SElemType e;e.ptr = T;e.task = Travel;if(T)Push(&S,e);while(!IsEmpty(S)){Pop(&S,&e);if(e.task == Visit)visit(e.ptr->data);else{if(e.ptr){p = e.ptr;e.ptr = p->rchild;e.task = Travel;Push(&S,e);e.ptr = p->lchild;e.task = Travel;Push(&S,e);e.ptr = p;e.task = Visit;Push(&S,e);}}}}
//中序遍历非递归
Status  InOrder(BiTree T,void(*visit)(TElemType e))
{Stack S;InitStack(&S);BiTree p;SElemType e;e.ptr = T;e.task = Travel;if(T)Push(&S,e);while(!IsEmpty(S)){Pop(&S,&e);if(e.task == Visit)visit(e.ptr->data);else{if(e.ptr){p = e.ptr;e.ptr = p->rchild;Push(&S,e);e.ptr = p;e.task = Visit;Push(&S,e);e.ptr = p->lchild;e.task = Travel;Push(&S,e);}}}}//houxu非递归
Status  PostOrder(BiTree T,void(*visit)(TElemType e))
{Stack S;InitStack(&S);BiTree p;SElemType e;e.ptr = T;e.task = Travel;if(T)Push(&S,e);while(!IsEmpty(S)){Pop(&S,&e);if(e.task == Visit)visit(e.ptr->data);else{if(e.ptr){e.task = Visit;Push(&S,e);p = e.ptr;e.ptr = p->rchild;e.task = Travel;Push(&S,e);e.ptr = p->lchild;e.task = Travel;Push(&S,e);}}}}int main()
{BiTree T;printf("创建树，输入0为空树：\n");CreateBiTree(&T);printf("先序遍历递归：");PreOrderTraverse(T, *visit);printf("\n中序遍历递归：");InOrderTraverse(T, *visit);printf("\n后序遍历递归：");PostOrderTraverse(T, *visit);printf("\n");printf("\n前序非递归算法: ");PreOrder( T,*visit);printf("\n中序非递归算法: ");InOrder( T,*visit);printf("\n后序非递归算法: ");PostOrder( T,*visit);return 0;
}