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

《031040316张祥森实验四树和二叉树的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验四树和二叉树的应用#include"stdio.h"#include"stdlib.h"#defineSTACK_INIT_SIZE10//栈的初始长度#defineSTACKINCREMENT5//栈的追加长度typedefstructbitree{chardata;structbitree*lchild,*rchild;}bitree;//二叉树结点定义typedefstruct{bitree**base;bitree**top;intstacksize;}sqstack;//链栈结点定义top栈顶base栈底且栈元素是指向二叉树结点的二级指针//建立一个空栈inti

2、nitstack(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;//栈长度为开辟空间大小return1;}//进栈intpush(sqstack*s,bitree*e){if(s->top-s->base>=s->stacksize)//如果栈满追加开辟空间{s->base=(bitree*)realloc(s

3、->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++;//进栈栈顶后移return1;}//出栈intpop(sqstack*s,bitree**e){if(s->top==s->base)return0;//栈空返回0--s->top;*e=*(s->top);//栈顶前移取出栈顶元素给eretur

4、n1;}//取栈顶intgettop(sqstack*s,bitree**e)//去栈顶元素注意top指向的是栈顶的后一个{if(s->top==s->base)return0;//所以s->top-1ofwork,relationships,needandpossibility,putqualityfirst."Improvestructure",referspartycarefully".IsamustadheretotheindividualabsorptionTheprincipleofthedevelopmentofamatureone,andstrictlyper

5、formintheadmissionprocedure,topreventthePartymember*e=*(s->top-1);return1;}/*------------------------非递归-----先序建立二叉树----------------------------------*/bitree*createprebitree(){charch;bitree*ht,*p,*q;sqstack*s;s=malloc(sizeof(bitree));//加上这一句为s初始化开辟空间ch=getchar();if(ch!='#'&&ch!='')/*输入二叉

6、树先序顺序是以完全二叉树的先序顺序不是完全二叉树的把没有的结点以#表示*/{ht=(bitree*)malloc(sizeof(bitree));ht->data=ch;ht->lchild=ht->rchild=NULL;p=ht;initstack(s);push(s,ht);//根节点进栈while((ch=getchar())!='')//算{if(ch!='#'){q=(bitree*)malloc(sizeof(bitree));//法q->data=ch;//if(p==*(s->top-1))p->lchild=q;//核elsep->rchild=q;/

7、/push(s,q);p=q;//心}//else{if(p==*(s->top-1))p->lchild=NULL;//的elsep->rchild=NULL;//pop(s,&p);}//步//}//骤returnht;}elsereturnNULL;}/*--------------------------递归---------先序建立二叉树-------------------------------*/voidCreateBiTree(bitree**T){//按先序次序输入二叉树中的结点的值