二叉树递归遍历 数据结构实验报告

《二叉树递归遍历 数据结构实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、南昌航空大学实验报告课程名称：数据结构实验名称：实验六二叉树的递归遍历及其应用班级：080611学生姓名：学号：08指导教师评定：签名:题目：假设二叉树采用二叉链表结构。设计并实现如下算法：先序递归建树，中序非递归遍历该树，输出各个结点的值，并求该树中单分支结点的个数。一、需求分析1.用户可以根据自己的需求分别输入任意的一个二叉树，并且能够实现中序非递归遍历该树输出各个结点的数值。2.通过已有的二叉树能够求出该树的单分支结点的个数。3.程序执行的命令包括：（1）构造二叉树T（2）遍历二叉树（3）求二叉树单分支结点的个数（4）求二叉树的总

2、结点数二、概要设计⒈为实现上述算法，需要链表的抽象数据类型：ADTBinarytree{数据对象：D是具有相同特性的数据元素的集合数据关系R：若D为空集，则R为空集，称binarytree为空二叉树；若D不为空集，则R为{H}，H是如下二元关系；（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D－{root}不为空，则存在D－{root}＝{D1，Dr}，且D1∩Dr为空集；（3）若D1不为空，则D1中存在唯一的元素x1，∈H，且存在D1上的关系H1是H的子集；若Dr不为空集，则Dr中存在唯

3、一的元素Xr，∈H，且存在Dr上的关系Hr为H的子集；H={,,H1,Hr};(4)(D1,{H1})是一颗符合本定义的二叉树，称为根的左子树，(Dr,{Hr})是一颗符合本定义的二叉树，称为根的右子树。基本操作:Creatbitree(&S，definition)初始条件：definition给出二叉树S的定义操作结果：按definition构造二叉树Scounter(T)初始条件：二叉树T已经存在操作结果：返回二叉树的总的结点数onecount(T)10初始条件：二叉树T已经存在

4、操作结果：返回二叉树单分支的节点数Clearbintree(S)初始条件：二叉树S已经存在操作结果：将二叉树S清为空树Bitreeempty(S)初始条件：二叉树S已经存在操作结果：若S为空二叉树，则返回TRUE，否则返回FALSEBitreedepth(S,&e)初始条件：二叉树S已经存在操作结果：返回S的深度Parent(S)初始条件：二叉树S已经存在，e是S中的某个结点操作结果：若e是T的非根结点，则返回它的双亲，否则返回空Preordertraverse(S)初始条件：二叉树S已经存在，Visit是对结点操作的应用函数。操作结果

5、：先序遍历S，对每个结点调用函数visit一次且仅一次。一旦visit失败，则操作失败。Inordertraverse(S,&e)初始条件：二叉树S已经存在，Visit是对结点操作的应用函数。操作结果：中序遍历S，对每个结点调用函数visit一次且仅一次。一旦visit失败，则操作失败。Postordertraverse(&S,e)初始条件：二叉树S已经存在，Visit是对结点操作的应用函数。操作结果：后序遍历S，对每个结点调用函数visit一次且仅一次。一旦visit失败，则操作失败。}ADTBinarytree2.本程序有三个模块：

6、⑴主程序模块main(){初始化；{接受命令；显示结果；｝｝⑵先序建树的模块：主要建立一棵二叉树；⑶中序遍历模块：输出中序遍历的结果；(4)单分支结点数模块：输出单分支的结点数。三、详细设计⒈元素类型，结点类型10/*定义二叉树*/typedefstructbitnode{chardata;structbitnode*lchild,*rchild;}bitnode;/*定义栈元素的类型*/typedefstructnode{structbitnode*p;}node;/*定义栈*/typedefstructstack{node*base

7、;node*top;intsize;}stack;2.对抽象数据类型中的部分基本操作的伪码算法如下：stack*initstack()/*构建空栈*/{s->base=(structnode*)malloc(MAX*sizeof(node));if(!s->base)exit(0);s->top=s->base;s->size=MAX;returns;}/*判断栈是否为空栈*/intstackempty(stack*s){if(s->top==s->base)return1;elsereturn0;}/*入栈*/stack*push(s

8、tack*s,structbitnode*t){if(s->top-s->base==s->size){s->base=(structnode*)realloc(s->base,(s->size+10)*s