031040316张祥森实验四树和二叉树的应用

实验四 树和二叉树的应用 #include “stdio.h“ #include “stdlib.h“ #define STACK_INIT_SIZE 10 /栈的初始长度 #define STACKINCREMENT 5 /栈的追加长度 typedef struct bitree char data; struct bitree *lchild,*rchild; bitree; /二叉树结点定义 typedef struct bitree *base; bitree *top; int stacksize; sqstack; / 链栈结点定义 top 栈顶 base 栈底 且栈元素是指向二叉树结点 的二级指针 /建立一个空栈 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; /进栈 int push(sqstack *s,bitree *e) 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)=e;s-top+; /进栈 栈顶后移 return 1; /出栈 int pop(sqstack *s,bitree *e) if(s-top=s-base) return 0; /栈空 返回 0 -s-top;*e=*(s-top); /栈顶前移 取出栈顶元素给 e return 1; /取栈顶 int gettop(sqstack *s,bitree *e) /去栈顶元素 注意 top 指向的是栈顶的后一 个 if(s-top=s-base) return 0; /所以 s-top-1 *e=*(s-top-1); return 1; /*-非递归-先序建立二叉树-*/ bitree *createprebitree() char ch;bitree *ht,*p,*q; sqstack *s; s=malloc(sizeof(bitree); /加上这一句为 s 初始化开辟空间 ch=getchar(); if(ch!=# ht-data=ch; ht-lchild=ht-rchild=NULL; p=ht; initstack(s); push(s,ht); /根节点进栈 while(ch=getchar()!=n) / 算 if(ch!=#) q=(bitree *)malloc(sizeof(bitree); / 法 q-data=ch; / if(p=*(s-top-1) p-lchild=q; / 核 else p-rchild=q; / push(s,q);p=q; / 心 / else if(p=*(s-top-1) p-lchild=NULL; / 的 else p-rchild=NULL; / pop(s, / 步 / / 骤 return ht; else return NULL; /*-递归- 先序建立二叉树-*/ void CreateBiTree(bitree *T) /按先序次序输入二叉树中的结点的值（一个字符） ，空格字符表示空树， /构造二叉链表表示二叉树 char ch; scanf(“%c“, if(ch=#) *T=NULL; else *T=(bitree * )malloc(sizeof(bitree); if(!*T) exit(1); (*T)-data=ch; /生成根结点 CreateBiTree( /构造左子树 CreateBiTree( /构造右子树 /*-非递归-中序建立二叉树-*/ /*-递归- 中序建立二叉树-*/ /*-非递归-后序建立二叉树-*/ /*-递归- 后序建立二叉树-*/ /*-非递归-先序输出二叉树-*/ void preordertraverse(bitree *h) sqstack m; initstack( while(h|m.base!=m.top) if(h) push(printf(“%c“,h-data);h=h-lchild; elsepop( h=h-rchild; /*-非递归-中序输出二叉树-*/ void inordertraverse(bitree *h) sqstack m; initstack( while(h|m.base!=m.top) if(h) push(h=h-lchild; else pop( printf(“%c“,h-data); h=h-rchild; /*-非递归-后序遍历二叉树-*/ void postordertraverse(bitree *h) sqstack m; initstack( while(h|m.base!=m.top) if(h) push( h=h-lchild; else bitree *r; /使用 r 结点表示访问了右子树 代替标志域 gettop( if(h-rchild push( h=h-lchild; elsepop( printf(“%c“,h-data); r=h;h=NULL; /层次遍历二叉树 用队列 哈哈以后做 /*-主过程-*/ int main() bitree *ht; printf(“先序非递归建立一个二叉树:“); if(ht=createprebitree()!=NULL) /非递归建立 /CreateBiTree( /if(ht!=NULL) /递归建立 printf(“先序遍历输出二叉树:“); preordertraverse(ht); putchar(