数据结构二叉树报告

《数据结构二叉树报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构二叉树报告题目：编制一个可执行二叉树操作的程序一、需求分析1.本演示程序演示了输入缓冲区的执行过程，需要输入的包括字符和选择字符，字符则可以随意输入，特別强调字符为特殊的定义字符，程序最低层节点值为“*”，字符的输入以一个“冋车符”为结束标志的字符芈。2.演示程序的输出以用户和计算机对话的方式进行，即在计算机终端上显示“提示信息”后，由客户通过键盘输入数据并执行相应的命令；客户的输入数据和计算机的运算结果显示在其后。3.程序采用二叉树进行数据的存储和操作，二叉树的遍历采用先序遍历法，输入需要建立的二叉树的节点值，程序会自动计算出其所需，本程序同吋支持循环使用，程序运行后的结果作为依

2、据。4.测试数据：输入数据：abc林d#e*f**预计结果：先序递归遍历：abcdef屮序非递伯遍历：cbdacf后序递归遍历：cdbfea按层次遍历：abecdf度为一结点个数：1树的深度：35.程序的执行命令：(1)创建二叉树(2)递归算法先序遍历二叉树(3)非递归©法中序遍历二叉树(4)递归算法后序遍历二叉树(5)求二叉树叶子结点个数(6)按层次遍历二叉树(7)求二叉树树深二、概要设计1.设定二叉树的抽象数据类型定义为：ADTbtree{数据对象：D={a(i)

3、a(i)EIntSet,i=l，2,3…,n,n>0}数据关系：R(l)={

4、a(i-1),a(i)

5、GD,i=l,2,…，n}基本操作：btreecreat(&T)操作结果：创建一个二义树perorder(T)初始条件：二叉树存在操作结果：递归先序遍历二义树incorder(T)初始条件：二叉树存在操作结果：非递归屮序遍历二叉树，同时计算出度为1节点个数postorder(T)初始条件：二义树存在操作结果：递归后序遍历二叉树traverse(T)初始条件：二叉树存在操作结果：按层次遍历二叉树depth(T)初始条件：二叉树存在操作结果：求二叉树树深}ADTbtree1.队列的数据抽象类型：初始化一个带头结点的队列initqueue(q)操作结果：初始化一个带头结点的队列enqueue(&

6、q,T)初始条件：队列存在操作结果：入队列dequeue(&q,&T)初始条件：队列存在操作结果：出队列queueempty(q)初始条件：队列存在操作结果：判断队列是否为空2.本程序包含三个个模块：(1)主程序模块：voidmain(){调用命令；执行运算；输出结果；循环使用；}(2)二叉树模块：实现二叉树数据抽象类型(3)队列模块：执行层次遍历操作等各个模块的调用关系阁：主程序模块二叉树模块I队列模块三、详细设计1.二叉树结构类型typedefstructbtnode{chardata;structbtnode*1chiId;structbtnode*rchild;}btree2.二叉

7、树的基木操作设置：btreecreat(&T)//初始化，创建二叉树Tperorder()//递归先序遍历二义树Tinorder(T)//非递归中序遍历二叉树T//计算叶子结点个数并返回其值postorder(T)//递归后序遍历二义树Ttraverse(T)//对二叉树T进行层次遍历intdepth(btree*t)//求二叉树的树深3.队列的基本操作设罝：initqueue(q)//初始化一个带头结点的队列enqueue(&q,T)//入队列dequeue(&q,&T)//出队列queueempty(q)//判断队列是否为空其中部分操作的算法：voidcreat(bitree&T)//

8、创建二叉树{if(ch=='*’)T:NULL;else{T=(bitree)malloc(sizeof(bitnode));if(T==NULL)exit(OVERFLOW);T->data=ch;creat(T~>lch);creat(T_〉rch);}voidperorder(bitreeT)//先序遍历if(T){printf("%c〃，T->data);perorder(T-〉lch);perorder(T-〉rch);}}voidincordcr(bitrccT)//中序非递归遍历{boolboolean;boolean二1;do{while(p){if((p->rch==NU

9、LL&&p->lch!=NULL)

10、

11、(p->rch!=NULL&&p->lch==NULL))m++;s[top]=p;top++;p=p-〉lch;if(top==0)boolean二0;else{top—;p=s[top];printf(〃%c〃,p-〉data);p=p->rch;ij}while(boolean);voidpostorder(bitreeT)//后序遍历if(T){postordcr(T->lc