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

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

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

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

3、nt;intrear;JSqQueue;voidInitStack(SqStack&S){//构造一个空栈SS.base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTi*ee));if(!S.base)exit(0);//存储分配失败S.top=0;〃空表长度为0S.stacksize二STACK」NIT_SIZE;〃初始存储容量}//InitStackintStackEmpty(SqStack&S){〃判断栈S是否是空栈，是返回1,否则返回0if(S.top==0)ret

4、urn1;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+二STACKINCREMENT;}S.base[S・top++]二e;}//Pus

5、hvoidPop(SqStack&S,BiTree&e){〃若栈不空则删除S的栈顶元素，并用e返回其值if(S.top==0){printfC栈空”);//栈为空exit(O);}e=S.base[—S.top];}//PopintGetTop(SqStackS,BiTree&e){〃若栈不空则用e返回S的栈顶元素讦(S.top==0){printf(”栈空”)；return0;//栈为空}else{e=S.base[S.top-l];return1;}}//GetTopvoidInitQueue(SqQueue

6、&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+l)%MAX==Q.front)exit(0);Q.base[Q.rearJ=e;Q.reai-(Q.rear+1)%M

7、AX;voidDeQueue(SqQueue&Q,BiTree&e){〃将非空队列Q的队头元素出队列if(Q.front==Q.rear)exit(O);e=Q.base[Q.front];Q.front=(Q.front+1)%MAX;//intnO,n;//nO统计叶子结点数，n统计总的结点数voidPreCreatBiTree(BiTree&bt){〃按照先序建立二叉树的二叉链表”捫表示虚结点charch;ch=getchar();if(ch=#)bt=NULL;else{bt=(BiTree)malloc

8、(sizeof(BiTNode));bt->data=ch;PreCreatBiTree(bt->lchild);PreCreatBiTree(bt->rchild);}}voidInOrderTraverse1(BiTreebt){〃利用递归算法屮序遍历一个二叉树if(bt){InOrderTraversel(bt->lchild);printf("%2c,bt->d