资源描述：
《北京理工大学数据结构实验报告3》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《数据结构与算法统计》实验报告——实验三学院：班级：学号：姓名：8一、实验目的1熟悉VC环境，学会使用C++解决关于二叉树的问题。2在上机、调试的过程中，加强对二叉树的理解和运用。3锻炼动手编程和独立思考的能力。二、实验内容遍历二叉树。请输入一棵二叉树的扩展的前序序列，经过处理后生成一棵二叉树，然后对于该二叉树输出前序、中序和后序遍历序列。三、程序设计1、概要设计为实现上述程序功能，首先需要二叉树的抽象数据结构。⑴二叉树的抽象数据类型定义为：ADTBinaryTree{数据对象D：D是具有相同特性的数据元素的集合。
2、数据关系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中存在惟一的元素xr，∈H，且存在上的关系Hr⊆H；H={,,H1,Hr}；（4）(D
3、1,{H1})是一棵符合本定义的二叉树，称为根的左子树；(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。基本操作：CreatBiTree(BiTree&T)操作结果：按先序次序建立二叉链表表示的二叉树TPreOrderTraverse(BiTreeT,int(*visit)(chare))初始条件：二叉树T已经存在，visit是对结点操作的应用函数操作结果：先序遍历二叉树T，对每个结点调用visit函数仅一次；一旦visit（）失败，则操作失败。InOrderTraverse(BiTreeT,int(*
4、visit)(chare))初始条件：二叉树T已经存在，visit是对结点操作的应用函数操作结果：中序遍历二叉树T，对每个结点调用visit函数仅一次；一旦visit（）失败，则操作失败。PostOrderTraverse(BiTreeT,int(*visit)(chare))初始条件：二叉树T已经存在，visit是对结点操作的应用函数操作结果：后序遍历二叉树T，对每个结点调用visit函数仅一次；一旦visit（）失败，则操作失败。}ADTBinaryTree8⑵主程序流程主程序先调用CreatBiTree(Bi
5、Tree&T)函数，根据输入的先序序列构造出一棵二叉树，再依次调用PreOrderTraverse(BiTreeT,int(*visit)(chare))，InOrderTraverse(BiTreeT,int(*visit)(chare))，PostOrderTraverse(BiTreeT,int(*visit)(chare))函数，对该二叉树进行先序、中序、后序遍历并输出结果。⑶模块调用关系由主函数调用创建模块，再调用计算模块，由计算模块将结果输出。⑷流程图按照先序序列构造出一棵二叉树先序遍历并输出中序遍历并
6、输出后序遍历并输出开始结束2、详细设计⑴数据类型设计typedefstructBiTNode//二叉树结构类型{chardata;//建立数据域structBiTNode*lchild,*rchild;//建立左指针和右指针}BiTNode,*BiTree;⑵操作算法设计intCreatBiTree(BiTree&T)//按先序次序建立二叉链表表示的二叉树T{charch;scanf("%c",&ch);if(ch==''){8T=NULL;}else{T=(BiTNode*)malloc(sizeof(BiTNo
7、de));if(!T){exit(OVERFLOW);}T->data=ch;CreatBiTree(T->lchild);CreatBiTree(T->rchild);}return1;}intvisit(chare)//对数据进行输出{printf("%c",e);return1;}intPreOrderTraverse(BiTreeT,int(*visit)(chare))//先序遍历二叉树T的递归算法{if(T){if(visit(T->data))if(PreOrderTraverse(T->lchild
8、,visit))if(PreOrderTraverse(T->rchild,visit))return1;return0;}elsereturn1;}intInOrderTraverse(BiTreeT,int(*visit)(chare))//中序遍历二叉树T的递归算法{if(T){if(InOrderTraverse(T->lchild,visit))i
