include.doc

#include#include#include#define STACK_INIT_SIZE 10#define STACKINCREMENT 5typedef struct BiTNode char data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;typedef struct BiTree *base; BiTree *top; int stacksize;SqStack;int InitStack(SqStack *S) S-base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree); if(!S-base)exit(-1); S-top=S-base; S-stacksize=STACK_INIT_SIZE; return 1;void Push(SqStack *S,BiTree T) if(S-top-S-base=S-stacksize) S-base=(BiTree*)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(BiTree); if(!S-base)exit(-1); S-top=S-base+S-stacksize; S-stacksize+=STACKINCREMENT; *(S-top)+=T;int Pop(SqStack *S,BiTree *T) if(S-top=S-base)return 0; *T=*-(S-top); return 1;BiTree CreateBiTree(BiTree *T) char ch; scanf(%c,&ch); if(ch=#) *T=NULL; else *T=(BiTree)malloc(sizeof(BiTNode); (*T)-data=ch; CreateBiTree(&(*T)-lchild); CreateBiTree(&(*T)-rchild); return *T;void PreOrderTraverse(BiTree T) if (T) printf(%c ,T-data); if(T-lchild) PreOrderTraverse(T-lchild); if(T-rchild) PreOrderTraverse(T-rchild); void PreOrder(BiTree T) SqStack S; InitStack(&S); while(T|S.base!=S.top) if(T) Push(&S,T); printf(%c ,T-data); T=T-lchild; else Pop(&S,&T); T=T-rchild; void InOrderTraverse(BiTree T) if (T) if (T-lchild) InOrderTraverse(T-lchild); printf(%c ,T-data); if (T-rchild) InOrderTraverse(T-rchild); void InOrder(BiTree T) SqStack S; InitStack(&S); while(T|S.base!=S.top) if(T) Push(&S,T); T=T-lchild; else Pop(&S,&T); printf(%c ,T-data); T=T-rchild; void PostOrderTraverse(BiTree T) if (T) if (T-lchild) PostOrderTraverse(T-lchild); if (T-rchild) PostOrderTraverse(T-rchild); printf(%c ,T-data); void Getnum(BiTree T) int n=0,m=0; SqStack S; InitStack(&S); while(T|S.base!=S.top) if(T) Push(&S,T); n+; if(T-lchild=NULL&T-rchild=NULL) m+; T=T-lchild; else Pop(&S,&T); T=T-rchild; printf(%d %d,n,m);void main() BiTree T; printf(建立一个二叉树:); CreateBiTree(&T); if(T) printf(先序递归遍历:); PreOrderTraverse(T); putchar(n); printf(中序递归遍历:); InOrderTraverse(T); putchar(n); printf(后序递归遍历:); PostOrderTraverse(T); putchar(n); printf(先序非递归遍历:); Pr