《实验报告3 数据结构与算法 》由会员分享，可在线阅读，更多相关《实验报告3 数据结构与算法 （8页珍藏版）》请在金锄头文库上搜索。
1、实实 验验 报报 告告 课程名称课程名称 数据结构与算法数据结构与算法 实验学期实验学期 20152015 年年 春季春季 学期学期所在学院所在学院 交通科学与工程学院交通科学与工程学院 所属专业所属专业 交通信息与控制工程系交通信息与控制工程系 年级年级 20122012 专业班级专业班级 学生姓名学生姓名 学号学号 指导教师指导教师 实验最终成绩实验最终成绩 实验报告（三）实验报告（三）实验题目二叉树的基本操作及应用实验时间 2015 年 6 月 10 日实验地点B07-B214实验成绩实验性质应用性 设计性 综合性教师评阅： 实验目的明确； 操作步骤正确； 设计文稿（表格、程序、数据库、
2、网页）符合要求； 保存路径正确； 实验结果正确； 实验分析总结全面； 实验报告规范； 其他：评阅教师签名：一、实验目的一、实验目的1 熟悉二叉树的存储结构和对二叉树的基本操作。2 掌握对二叉树前序、中序、后序遍历操作的具体实现。3 学习利用递归方法编写对二叉树这种递归数据结构进行处理的算法。4 会应用二叉树的基本操作解决简单的实际问题二、实验内容和要求二、实验内容和要求( (说明算法的时间复杂度说明算法的时间复杂度) )1 基于二叉链表的存储格式，输入二叉树的先序序列，用*代表空节点，如ABD*CE*F*建立二叉树，然后中序遍历二叉树，输出节点的值。2 针对建好的二叉树，编写递归程序，求树中叶
3、子节点个数。3 针对建好的二叉树，编写递归程序，求二叉树的高度。4 针对建好的二叉树，试编写二叉树的前序非递归非递归遍历算法。三、主要设计思想与算法三、主要设计思想与算法 （此处不够可加页，或在反面书写）（此处不够可加页，或在反面书写）该实验主要包括一下几个函数，算法核心分别在各函数中。该实验主要包括一下几个函数，算法核心分别在各函数中。1.1.建立树的结构。建立树的结构。typedeftypedefstructstruct BiTNodeBiTNodechar element;Tree lchild,rchild;/B 数的基本结点输入输入 ABD*CE*F*ABD*CE*F* TreeTr
4、ee CreateBTree(void)/CreateBTree(void)/可以返回一个可以返回一个 TreeTree 指针指针Tree pTree;char val;scanf(“%c“,printf(“%c“,val);if(val=*|val=p) return NULL;/根据输入字符先序建树 else/*代表空pTree=(Tree)malloc(sizeof(struct BiTNode);if(pTree=NULL)printf(“内存分配失败！“);exit(-1);/防止程序不知道空间不够用了pTree-element=val;pTree-lchild=CreateBTre
5、e();pTree-rchild=CreateBTree();/递归，NLR 地创建结点returnreturn pTree;pTree;2.2.数叶结点个数数叶结点个数intint CountLeaf(TreeCountLeaf(Tree T)T)if(T=NULL)return 0;if(!T-lchild/两个儿子都空则说明是叶子，返回 1elsereturn CountLeaf(T-lchild)+CountLeaf(T-rchild);/数左右子树总共的叶结点 ;3.3. 数树的深度数树的深度intint CountLevel(TreeCountLevel(Tree T)T)if(!
6、T) return 0;elseintLeft=CountLevel(T-lchild);intRight=CountLevel(T-rchild);return 1+(LeftRight? Left:Right);/三目运算取最大;/最后数得树的最深层数，也是递归typedeftypedef structstructTree elementsMAXSIZE;/注意这里放的是指针int top;Stack;/这是一个用于装 Tree 指针的栈4.4. 这是用非递归实现先序遍历的这是用非递归实现先序遍历的voidvoid PreOrder(TreePreOrder(Tree T)T)Stack
7、S;Tree p;InitStack(/造一个栈待会儿用p=T; /用 p 指针来不断处理结点操作 while ( p|!IsEmpty(S)while(p)printf(“%c“,p-element);/只要不空则把 p 指的数据输出Push(p=p-lchild;/继续往左边找/一旦停下来说明找到了空结点，则开始往上一层的右边找一下if(!IsEmpty(S) ) /栈非空p=Pop(/退栈，找到刚才说的上一层p=p-rchild;/找右边了/只要 while 还循环说明没有遍历完，现在再一次从刚才的右边执行先序遍历;四、实验结果（设计文档、文稿存放路径，可以截图描述实验结果）四、实验结果
8、（设计文档、文稿存放路径，可以截图描述实验结果）#include#include “3.h“int main(void)/改主程序对应上图结果Tree pTree;int i,j;pTree=CreateBTree();/创建二叉树 pTreei=CountLeaf(pTree);printf(“There are %d leaves!“,i);/递归程序数叶节点j=CountLevel(pTree);printf(“There are %d levels!“,j);/递归程序数层数PreOrder(pTree);/按照前序遍历输出该书的元素return 0;五、实验分析总结五、实验分析总结本
9、次实验采用二叉树存储了一系列的字符串，通过函数本次实验采用二叉树存储了一系列的字符串，通过函数 TreeTree CreateBTree(void)CreateBTree(void)得到一个根据输入创建的二叉树结构，时间复杂度是得到一个根据输入创建的二叉树结构，时间复杂度是O O（n n） ；通过函数；通过函数 intint CountLeaf(TreeCountLeaf(Tree T)T)递归返回叶子个数，时间复杂度递归返回叶子个数，时间复杂度O(n)O(n)；通过；通过 intint CountLevel(TreeCountLevel(Tree T)T)返回最深路径得到树的深度，时间复杂返
10、回最深路径得到树的深度，时间复杂度度 O O（n n） ；最后用；最后用 voidvoid PreOrder(TreePreOrder(Tree T)T)实现非递归写法的二叉树先序遍历，时间实现非递归写法的二叉树先序遍历，时间复杂度为复杂度为 O(n).O(n).综上所述，因为都是要遍历综上所述，因为都是要遍历 B B 数的每个节点，所以程序执行的时间长度数的每个节点，所以程序执行的时间长度和输入的字符串长度和输入的字符串长度 n n 是线性增长的。他们的时间复杂度都是是线性增长的。他们的时间复杂度都是 O(n).O(n).这次实验，我更深刻的理解了这次实验，我更深刻的理解了 B B 数的基本
11、性质如递归性，利用递归，我数的基本性质如递归性，利用递归，我们可以很方便的写出各种对树的操作；熟悉了创建树，遍历树的基本方法；们可以很方便的写出各种对树的操作；熟悉了创建树，遍历树的基本方法；体会了算法的代码实现细节。最后，特别是在用非递归方法实现遍历的函数体会了算法的代码实现细节。最后，特别是在用非递归方法实现遍历的函数中，我更加深刻的理解到了数是如何遍历的，以及递归是不断调用自己的本中，我更加深刻的理解到了数是如何遍历的，以及递归是不断调用自己的本质，而且不仅仅对质，而且不仅仅对 BTreeBTree 本身有运用，之前学习的栈也用于存储遍历的节点本身有运用，之前学习的栈也用于存储遍历的节点指针，所以数据结构的学习应该是一个融会贯通的过程，我在学习的过程中指针，所以数据结构的学习应该是一个融会贯通的过程，我在学习的过程中越来越有信心了。越来越有信心了。
