二叉树递归非递归先序中序后序遍历以及层次遍历和求叶子点数.docVIP

#include stdio.h#include malloc.h#include stdlib.h #define STACK_INT_SIZE 100 //存储空间初始分配量#define STACKINCREMENT 10 //存储空间分配增量#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define OVERFLOW -2 typedef char TElemType;typedef int Status;typedef char SElemType; //二叉树的二叉链表存储表示typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; //左右孩子指针}BiTNode, *BiTree; //用于存储二叉树结点的栈typedef struct { BiTree *base; BiTree *top; int stacksize; //当前已分配的存储空间}SqStack; //定义链式队列结点typedef struct QNode{ BiTree Queuedata; struct QNode * next;}QNode,* QueuePtr; //定义链式队列typedef struct{ QueuePtr front; // QueuePtr rear;}LinkQueue;//创建存储二叉树结点的空栈Status InitStack(SqStack S){ S.base = (BiTree *) malloc(sizeof(BiTree)); if(!S.base) exit(OVERFLOW); S.top = S.base; S.stacksize = STACK_INT_SIZE; return OK;} //存储二叉树结点的栈的取栈顶元素Status GetTop(SqStack S, BiTree e) { //若栈不空，则用e返回S的栈顶元素 if(S.top == S.base) return ERROR; e = *(S.top-1); return OK;} //存储二叉树结点的栈的入栈操作Status Push(SqStack S, BiTree e){ //插入元素e为栈顶元素 if(S.top - S.base = S.stacksize) { //若栈满，则追加存储空间 S.base = (BiTree *) realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(BiTree)); if(!S.base) return ERROR; S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *S.top = e; S.top++; return OK;} //用于存储二叉树结点的栈出栈操作Status Pop(SqStack S,BiTree e){ //删除S的栈顶元素，并用e返回 if(S.base == S.top) return ERROR; S.top--; e = *S.top; return OK;} //判断存储二叉树结点的栈是否为空 Status StackEmpty(SqStack S) {  // 若栈S为空栈，则返回TRUE，否则返回FALSE  if(S.top == S.base) return TRUE; else return FALSE; } //先序顺序创建一颗二叉树Status PreOrderCreateBiTree(BiTree T) { //按先序次序输入二叉树中结点的值 //构造二叉链表表示的二叉树T char ch; scanf(%c,ch); if(ch == 0) T = NULL; else { //if(!(T = (BiTree ) malloc(sizeof(BiTree)))) exit(OVERFLOW);//作用和下一语句的作用相同，注意两者的区别 if(!(T = (BiTNode* ) malloc(sizeof(BiTNode)))) exit(OVERFLOW); T-data = ch; //生成根结点 PreOrderCreateBiTree(T-lchild); //构造左子树 PreOrderCreateBiTree(T-rchild); //构造右