二叉树的各种基本操作实验报告.doc

《二叉树的各种基本操作实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验项目二叉树的操作项目类型综合型完成时间2009-11-2实验目的及要求掌握二叉树的存储实现;掌握二叉树的遍历思想;掌握二叉树的常见算法的程序实现。【实验过程】（实验步骤、绘图、记录、数据、分析、结果）实验内容：a.输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD###CE##F##建立二叉树，实现先序、中序和后序以及按层次遍历序列。b.求所有叶子及结点总数。实验步骤：#include#include#defineMAX10#defineSTACK

2、_INIT_SIZE40//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量typedefstructBiTNode{chardata;structBiTNode*lchild;structBiTNode*rchild;}BiTNode,*BiTree;//将BiTree定义为指向二叉链表结点结构的指针类型BiTNode*bt;typedefstruct{BiTree*base;inttop;intstacksize;}SqStack;typedefstruct{

3、BiTree*base;intfront;intrear;}SqQueue;voidInitStack(SqStack&S){//构造一个空栈SS.base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree));if(!S.base)exit(0);//存储分配失败S.top=0;//空表长度为0S.stacksize=STACK_INIT_SIZE;//初始存储容量}//InitStackintStackEmpty(SqStack&S){//判断栈S是否是

4、空栈，是返回1，否则返回0if(S.top==0)return1;elsereturn0;}//StcakEmptyvoidPush(SqStack&S,BiTreee){//插入元素e为新的栈顶元素,if(S.top>=S.stacksize){//栈满追加空间S.base=(BiTree*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree));if(!S.base)exit(0);//存储分配失败S.stacksize+=STAC

5、KINCREMENT;}S.base[S.top++]=e;}//PushvoidPop(SqStack&S,BiTree&e){//若栈不空则删除S的栈顶元素，并用e返回其值if(S.top==0){printf("栈空");//栈为空exit(0);}e=S.base[--S.top];}//PopintGetTop(SqStackS,BiTree&e){//若栈不空则用e返回S的栈顶元素if(S.top==0){printf("栈空");return0;//栈为空}else{e=S.base[

6、S.top-1];return1;}}//GetTopvoidInitQueue(SqQueue&Q){//构建新队列QQ.base=(BiTree*)malloc(MAX*sizeof(BiTree));Q.front=Q.rear=0;}intQueueEmpty(SqQueueQ){//判断队列是否是一个空队列if(Q.front==Q.rear)return1;return0;}voidEnQueue(SqQueue&Q,BiTreee){//将元素e插入到队列Q中if((Q.rear+1)

7、%MAX==Q.front)exit(0);Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAX;}voidDeQueue(SqQueue&Q,BiTree&e){//将非空队列Q的队头元素出队列if(Q.front==Q.rear)exit(0);e=Q.base[Q.front];Q.front=(Q.front+1)%MAX;}//intn0,n;//n0统计叶子结点数，n统计总的结点数voidPreCreatBiTree(BiTree&bt){//按照先序建立二叉树的

8、二叉链表"#"表示虚结点charch;ch=getchar();if(ch=='#')bt=NULL;else{bt=(BiTree)malloc(sizeof(BiTNode));bt->data=ch;PreCreatBiTree(bt->lchild);PreCreatBiTree(bt->rchild);}}voidInOrderTraverse1(BiTreebt){//利用递归算法中序遍历一个二叉树if(bt){InOrderTraverse1(bt->l