北京理工大学数据结构实验报告3

1、数据结构与算法统计实验报告实验三一、实验目的熟悉VC环境，学会使用C+解决关于二叉树的问题。在上机、调试的过程中，加强对二叉树的理解和运用。二、实验内容遍历二叉树。请输入一棵二叉树的扩展的前序序列，经过处理后生成一棵二叉树，然后对于该二叉树输出前序、中序和后序遍历序列。三、程序设计1、概要设计为实现上述程序功能，首先需要二叉树的抽象数据结构。二叉树的抽象数据类型定义为：ADT BinaryTree 数据对象D：D 数据关系R：D= ，则R= ，称BinaryTreeD ，则R=H，H在Droot，它在关系H若D-root，则存在D-root=D1,DrD1Dr =；D1D1D1H1HDrDrx

2、r，H，且存在上的关系HrH；H=,H1,Hr；（4）(D1,H1)是一棵符合本定义的二叉树，称为根的左子树；(Dr,Hr)是一棵符合本定义的二叉树，称为根的右子树。基本操作：CreatBiTree(BiTree &T)操作结果：按先序次序建立二叉链表表示的二叉树T PreOrderTraverse(BiTree T,int (*visit)(char e)初始条件：二叉树T 已经存在，visit 是对结点操作的应用函数操作结果：先序遍历二叉树T ，对每个结点调用visit visit（）失败，则操作失败。InOrderTraverse(BiTree T,int (*visit)(char e

3、)初始条件：二叉树T 已经存在，visit 是对结点操作的应用函数操作结果：中序遍历二叉树T ，对每个结点调用visit visit（）失败，则操作失败。PostOrderTraverse(BiTree T,int (*visit)(char e)初始条件：二叉树T 已经存在，visit 是对结点操作的应用函数操作结果：后序遍历二叉树T ，对每个结点调用visit visit（）失败，则操作失败。 ADT BinaryTree2主程序流程主程序先调用 CreatBiTree(BiTree &T)函数，根据输入的先序序列构造出一棵二叉树，再依次调用PreOrderTraverse(BiTree

4、T,int (*visit)(char e)，InOrderTraverse(BiTree T,int (*visit)(char e)，PostOrderTraverse(BiTree T,int (*visit)(char 函数，对该二叉树进行先序、中序、后序遍历并输出结果。模块调用关系由主函数调用创建模块，再调用计算模块，由计算模块将结果输出。流程图开始开始按照先序序列构造出一棵二叉树先序遍历并输出中序遍历并输出后序遍历并输出结束2、详细设计数据类型设计typedef struct BiTNode/二叉树结构类型char data;/建立数据域struct BiTNode *lchild

5、,*rchild;/建立左指针和右指针BiTNode,*BiTree;操作算法设计int CreatBiTree(BiTree &T)/按先序次序建立二叉链表表示的二叉树Tchar ch; scanf(%c,&ch); if(ch= )3elseT=NULL;T=(BiTNode *)malloc(sizeof(BiTNode); if(!T)exit (OVERFLOW);T-data=ch; CreatBiTree(T-lchild); CreatBiTree(T-rchild);return 1;int visit(char e)/对数据进行输出printf(%c,e); return

6、1;int PreOrderTraverse(BiTree T,int (*visit)(char e)/先序遍历二叉树T 的递归算法if(T)elseif(visit(T-data)if(PreOrderTraverse(T-lchild,visit) if(PreOrderTraverse(T-rchild,visit) return 1;return 0;return 1;int InOrderTraverse(BiTree T,int (*visit)(char e)/中序遍历二叉树T 的递归算法if(T)if(InOrderTraverse(T-lchild,visit) if(vi

7、sit(T-data)4elsereturn 1;if(InOrderTraverse(T-rchild,visit) return 1;return 0;int PostOrderTraverse(BiTree T,int (*visit)(char e)/后序遍历二叉树T 的递归算法if(T)elseif(PostOrderTraverse(T-lchild,visit) if(PostOrderTraverse(T-rchild,visit)if(visit(T-data) return 1;return 0;return 1;主函数设计void main()/主函数BiTree T;C

8、reatBiTree(T); 按先序次序建立二叉链表表示的二叉树printf(PreOrderTraverse:n);PreOrderTraverse(T,visit); printf(n);printf(InOrderTraverse:n); InOrderTraverse(T,visit); printf(n);printf(PostOrderTraverse:n); PostOrderTraverse(T,visit); printf(n);四、程序调试分析调试时，输入时有时候有输出有时候没输。向老师请教，老师说是比如abc，则b 下完整的树。进行先序遍历时，访问左子树后程序即结束，不访

9、问根结点和右子树。后来发现是return 0return 1的问题。递归时return return 5到原位置继续执行。以后应加强对于基础知识的理解。五、程序运行结果测试一：ABCDE GFPreOrderTraverse: ABCDEGFInOrderTraverse: CBEGDFAPostOrderTraverse: CGEFDBA测试二：12345 76PreOrderTraverse: InOrderTraverse: PostOrderTraverse:六 、 程 序 清 单 #include #include #include #define OVERFLOWtypedef s

10、truct BiTNode/二叉树结构类型char data;/建立数据域struct BiTNode *lchild,*rchild;/建立左指针和右指针BiTNode,*BiTree;int CreatBiTree(BiTree &T);/按先序次序建立二叉链表表示的二叉树T int visit(char e);/对数据进行输出int PreOrderTraverse(BiTree T,int (*visit)(char e);/ int InOrderTraverse(BiTree T,int (*visit)(char e);/ /序遍历二叉树T 序遍历二叉树T 的递归算法int Po

11、stOrderTraverse(BiTree T,int (*visit)(char e);/ /序遍历二叉树T 的递归算法void main()/主函数BiTree T;CreatBiTree(T); 按先序次序建立二叉链表表示的二叉树printf(PreOrderTraverse:n);6PreOrderTraverse(T,visit); printf(n);printf(InOrderTraverse:n); InOrderTraverse(T,visit); printf(n);printf(PostOrderTraverse:n); PostOrderTraverse(T,visi

12、t); printf(n);int CreatBiTree(BiTree &T)/按先序次序建立二叉链表表示的二叉树Tchar ch; scanf(%c,&ch); if(ch= )elseT=NULL;T=(BiTNode *)malloc(sizeof(BiTNode); if(!T)exit (OVERFLOW);T-data=ch; CreatBiTree(T-lchild); CreatBiTree(T-rchild);return 1;int visit(char e)/对数据进行输出printf(%c,e); return 1;int PreOrderTraverse(BiTre

13、e T,int (*visit)(char e)/ /序遍历二叉树T 的递归算法if(T)if(visit(T-data)if(PreOrderTraverse(T-lchild,visit)7elsereturn 1;if(PreOrderTraverse(T-rchild,visit) return 1;return 0;int InOrderTraverse(BiTree T,int (*visit)(char e)/ /序遍历二叉树T 的递归算法if(T)elseif(InOrderTraverse(T-lchild,visit) if(visit(T-data)if(InOrderTraverse(T-rchild,visit) return 1;retur