二叉树的建立、遍历、各种算法.doc

基于二叉树的二叉链表存储结构实现以下操作: 用先序遍历创建二叉树 对二叉树进行非递归遍历（先序、中序、后序） 求二叉树所有结点和叶子结点个数 求二叉树的深度 #includestdio.h #includemalloc.h #includemath.h #includestdlib.h #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 //#define OVERFLOW #define NULL 0 typedef int Status; typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; }BiTNode, *BiTree; typedef BiTree SElemType;//tepedef BiNode SElemType; //#define MAX_TREE_SIZE 100 //typedef TElemtype SqBiTree[MAX_TREE_SIZE ]; //SqBiTree bt; typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 Status InitStack(SqStack S) { S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } Status GetTop(SqStack S,SElemType e) { if(S.top==S.base) return ERROR; e=*(S.top-1); return OK; } Status Push(SqStack S,SElemType e) { if(S.top-S.base=S.stacksize) { S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK; } Status Pop(SqStack S,SElemType e) { if(S.top==S.base)return ERROR; e=*--S.top; return OK; } Status StackEmpty(SqStack S) { if(S.top==S.base)return TRUE; else return FALSE; } Status CreateBiTree(BiTree T) { //按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树， //构造二叉链表表示的二叉树T。 char ch; scanf(%c,ch); if(ch==@)T=NULL; else { if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW); T-data=ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild); } return OK; }//CreateBiTree Status PreoderTraverse(BiTree T) {//二叉树先序遍历非递归算法 SqStack S;BiTree p; InitStack(S); p=T; while(p||!StackEmpty(S)) { if(p) { printf(%c\t,p-data);p=p-lchild; Push(S,p-rchild); } else Pop(S,p); } return OK; }// PostoderTraverse Status InoderTraverse(BiTree T) {//二叉树中序遍历非递归算法 SqStack S;BiTree