《北京理工大学数据结构实验报(1).docx》由会员分享，可在线阅读，更多相关《北京理工大学数据结构实验报(1).docx（10页珍藏版）》请在三一办公上搜索。
1、北京理工大学数据结构实验报数据结构与算法统计 实验报告 实验三 学院： 班级： 学号： 姓名： 1 一、实验目的 1 熟悉VC环境，学会使用C+解决关于二叉树的问题。 2 在上机、调试的过程中，加强对二叉树的理解和运用。 3 锻炼动手编程和独立思考的能力。 二、实验内容 遍历二叉树。 请输入一棵二叉树的扩展的前序序列，经过处理后生成一棵二叉树，然后对于该二叉树输出前序、中序和后序遍历序列。 三、程序设计 1、概要设计 为实现上述程序功能，首先需要二叉树的抽象数据结构。 二叉树的抽象数据类型定义为： ADT BinaryTree 数据对象D： D是具有相同特性的数据元素的集合。 数据关系R： 若
2、D=，则R=，称BinaryTree为空二叉树； 若D，则R=H，H是如下二元关系； 在D中存在惟一的称为根的数据元素root，它在关系H下无前驱； 若D-root，则存在D-root=D1,Dr，且D1Dr =； 若D1，则D1中存在惟一的元素x1，H，且存在D1上的关系H1 H；若Dr，则Dr中存在惟一的元素xr，H，且存在上的关系Hr H；H=,H1,Hr； (D1,H1)是一棵符合本定义的二叉树，称为根的左子树；(Dr,Hr)是一棵符合本定义的二叉树，称为根的右子树。 基本操作： CreatBiTree(BiTree &T) 操作结果：按先序次序建立二叉链表表示的二叉树T PreOrd
3、erTraverse(BiTree T,int (*visit)(char e) 初始条件：二叉树T已经存在，visit是对结点操作的应用函数 操作结果：先序遍历二叉树T ，对每个结点调用visit函数仅一次；一旦visit失败，则操作失败。 InOrderTraverse(BiTree T,int (*visit)(char e) 初始条件：二叉树T已经存在，visit是对结点操作的应用函数 操作结果：中序遍历二叉树T ，对每个结点调用visit函数仅一次；一旦visit失败，则操作失败。 PostOrderTraverse(BiTree T,int (*visit)(char e) 初始条
4、件：二叉树T已经存在，visit是对结点操作的应用函数 操作结果：后序遍历二叉树T ，对每个结点调用visit函数仅一次；一旦visit失败，则操作失败。 ADT BinaryTree 2 主程序流程 主程序先调用CreatBiTree(BiTree &T)函数，根据输入的先序序列构造出一棵二叉树，再依次调用PreOrderTraverse(BiTree T,int (*visit)(char e)，InOrderTraverse(BiTree T,int (*visit)(char e)，PostOrderTraverse(BiTree T,int (*visit)(char e)函数，对该
5、二叉树进行先序、中序、后序遍历并输出结果。 模块调用关系 由主函数调用创建模块，再调用计算模块，由计算模块将结果输出。 流程图 开始 按照先序序列构造出一棵二叉树 先序遍历并输出 中序遍历并输出 后序遍历并输出 结束 2、详细设计 数据类型设计 typedef struct BiTNode/二叉树结构类型 char data;/建立数据域 struct BiTNode *lchild,*rchild;/建立左指针和右指针 BiTNode,*BiTree; 操作算法设计 int CreatBiTree(BiTree &T) /按先序次序建立二叉链表表示的二叉树T char ch; scanf(%
6、c,&ch); if(ch= ) 3 T=NULL; else 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(BiTree T,int (*visit)(char e) /先序遍历二叉树T的递归算法 if(T) if(visit(T-data)
7、if(PreOrderTraverse(T-lchild,visit) if(PreOrderTraverse(T-rchild,visit) return 1; return 0; else int InOrderTraverse(BiTree T,int (*visit)(char e) /中序遍历二叉树T的递归算法 return 1; if(T) if(InOrderTraverse(T-lchild,visit) if(visit(T-data) 4 if(InOrderTraverse(T-rchild,visit) return 1; return 0; else return 1
8、; int PostOrderTraverse(BiTree T,int (*visit)(char e) /后序遍历二叉树T的递归算法 主函数设计 void main /主函数 四、程序调试分析 调试时，输入时有时候有输出有时候没输。向老师请教，老师说是比如abc，则b下的两个孩子是空的也应该打出空格，后来试了一下，果然是这样，也就是说应该要输入一个完整的树。 进行先序遍历时，访问左子树后程序即结束，不访问根结点和右子树。后来发现是“return 0;”还是“return 1;”的问题。递归时，“return 0；”代表程序结束，“return 1；”代表回BiTree T; CreatBi
9、Tree(T); /按先序次序建立二叉链表表示的二叉树T printf(PreOrderTraverse:n); PreOrderTraverse(T,visit); ;/先序遍历二叉树T printf(n); printf(InOrderTraverse:n); InOrderTraverse(T,visit); /中序遍历二叉树T printf(n); printf(PostOrderTraverse:n); PostOrderTraverse(T,visit); /后序遍历二叉树T printf(n); if(T) if(PostOrderTraverse(T-lchild,visit)
10、 if(PostOrderTraverse(T-rchild,visit) if(visit(T-data) return 1; return 0; else return 1; 5 到原位置继续执行。以后应加强对于基础知识的理解。 五、程序运行结果 测试一： ABC DE G F PreOrderTraverse: ABCDEGF InOrderTraverse: CBEGDFA PostOrderTraverse: CGEFDBA 测试二： 123 45 7 6 PreOrderTraverse: 1234576 InOrderTraverse: 3257461 PostOrderTrav
11、erse: 3756421 六、程序清单 #include #include #include #define OVERFLOW 0 typedef struct 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);/
12、先序遍历二叉树T的递归算法 int InOrderTraverse(BiTree T,int (*visit)(char e);/中序遍历二叉树T的递归算法 int PostOrderTraverse(BiTree T,int (*visit)(char e);/后序遍历二叉树T的递归算法 void main/主函数 BiTree T; CreatBiTree(T); /按先序次序建立二叉链表表示的二叉树T printf(PreOrderTraverse:n); 6 PreOrderTraverse(T,visit); ;/先序遍历二叉树T printf(n); printf(InOrderT
13、raverse:n); InOrderTraverse(T,visit); /中序遍历二叉树T printf(n); printf(PostOrderTraverse:n); PostOrderTraverse(T,visit); /后序遍历二叉树T printf(n); int CreatBiTree(BiTree &T)/按先序次序建立二叉链表表示的二叉树T char ch; scanf(%c,&ch); if(ch= ) T=NULL; else T=(BiTNode *)malloc(sizeof(BiTNode); if(!T) exit (OVERFLOW); T-data=ch;
14、 CreatBiTree(T-lchild); CreatBiTree(T-rchild); return 1; int visit(char e)/对数据进行输出 int PreOrderTraverse(BiTree T,int (*visit)(char e)/先序遍历二叉树T的递归算法 printf(%c,e); return 1; if(T) if(visit(T-data) if(PreOrderTraverse(T-lchild,visit) 7 if(PreOrderTraverse(T-rchild,visit) return 1; return 0; else return
15、 1; int InOrderTraverse(BiTree T,int (*visit)(char e)/中序遍历二叉树T的递归算法 if(T) if(InOrderTraverse(T-lchild,visit) if(visit(T-data) if(InOrderTraverse(T-rchild,visit) return 1; return 0; else return 1; int PostOrderTraverse(BiTree T,int (*visit)(char e)/后序遍历二叉树T的递归算法 if(T) if(PostOrderTraverse(T-lchild,visit) if(PostOrderTraverse(T-rchild,visit) if(visit(T-data) return 1; return 0; else return 1; 8
