数据结构二叉树作业.doc

《数据结构二叉树作业.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、个人收集整理勿做商业用途1.实验目的：通过上机实验进一步掌握栈、队列、二叉树的存储结构及基本操作的实现方法.2.实验内容与要求：基于二叉链表存储结构实现二叉树的基本运算,要求:⑴能建立非空二叉树;⑵实现二叉树的先、中、后序递归遍历算法；⑶实现二叉树的非递归的先(或中、或后)序遍历算法及层序遍历算法;⑷记录运行结果并对递归算法和非递归算法的效率加以分析。3.数据结构设计：逻辑结构：树形结构存储结构：链式存储结构4.算法设计:个人收集整理勿做商业用途＃include〈stdio.h>＃include

2、#defineOK1＃defineERROR0//使用二叉链表存储形式typedefstructBiTNode{chardata；structBiTNode＊lchild，＊rchild;｝BiTNode，*BiTree;//这里是将指向节点的指针放到栈里，而通过调试是//可以看到指针指向的值的,所以不是将树放进去了typedefstruct{BiTree*base；BiTree＊top;intstacksize；｝SqStack;typedefstruct{BiTree＊

3、base；intfront；intrear;}SqQueue;intInitStack（SqStack&S)｛S.base=（BiTree＊)malloc(100＊sizeof(BiTree）);if(！S。base)exit(2)；S.top=S.base；S.stacksize=100；returnOK；｝intGetTop(SqStackS,BiTree＆e){if(S。top==S.base)returnERROR；e=*（S。top—1);returnOK;}intPUSH（SqSta

4、ck&S,BiTreee)｛if(S。top—S。base〉=S.stacksize){S.base=(BiTree*）realloc(S.base,(S。stacksize+10)*sizeof(BiTree）)；if（！S。base）exit（2)；S.top=S。base+S。stacksize；S.stacksize=S.stacksize+10;}＊S.top++=e;returnOK；｝intPOP(SqStack＆S,BiTree&e）{个人收集整理勿做商业用途if(S.top==

5、S.base)returnERROR；e=*—-S。top;returnOK;｝intStackEmpty(SqStackS）{if（S。base==NULL)returnERROR；if(S。base==S。top）returnOK；returnERROR;｝//队列的东西伤不起啊intInitQueue（SqQueue&Q）{Q.base=(BiTree*)malloc(100*sizeof（BiTree))；if(！Q.base）exit(2);Q。front=Q。rear=0；retur

6、nOK;}intEnQueue（SqQueue&Q，BiTreee){if（(Q。rear+1）％100==Q。front）returnERROR；Q。base［Q。rear]=e;Q.rear=（Q。rear+1)%100；returnOK;}intDeQueue(SqQueue＆Q,BiTree&e）{if(Q。front==Q.rear）returnERROR；e=Q.base［Q.front]；Q。front=(Q.front+1）%100；returnOK；｝intQueueEmpty

7、（SqQueueQ)｛if(Q。base==NULL)returnERROR；if(Q.front==Q.rear）returnOK;returnERROR;｝BiTreeCreateBiTree(BiTree&T){//算法6。4//按先序次序输入二叉树中结点的值（一个字符）,空格字符表示空树，//构造二叉链表表示的二叉树T。charch；scanf(”％c",＆ch）;//这里表明了输入形式是ABCDE＃＃FG然后是回车if(ch==’#’)T=NULL；else{if(！(T=(BiTNo

8、de＊)malloc(sizeof(BiTNode)）)）returnERROR；T—>data=ch；//生成根结点CreateBiTree(T-〉lchild);//构造左子树CreateBiTree(T->rchild)；//构造右子树}returnT；}//CreateBiTreeintPrintElement(chare）｛//输出元素e的值printf（"%c",e）；returnOK；}intPreOrderTraverse（BiTreeT，int（＊Visit）（char）){/