数据结构报告二.doc

数据结构实习报告二 学院：经管学院 姓名: 王大山 指导教师：朱晓莲 题目：唯一确定一棵二叉树 需求分析 【问题描述】 如果给出了遍历二叉树的前序序列和中序序列，则可以构造出唯一的一棵二叉树。试编写实现上述功能的程序。 【基本要求】 已知一棵二叉树的前序和中序遍历序列，试设计完成下列任务的一个算法： （1）构造一棵二叉树； （2）证明构造正确（即分别以前序和中序遍历该树，将得到的结果与给出的序列进行比较）。 【测试数据】 前序序列为ABDEGCFHIJ，中序序列为DBGEAHFIJC。 设计 1.设计思想? （1）存储结构：结构体；? （2）主要算法基本思想：两序列读入两数组，根据前序和中序特点逐步建立。? 2.设计表示? （1）函数调用关系图? main-Initiate-CreateTree-PrintBiTree? （2）函数接口规格说明? void?Initiate(BiTNode?**root)/*初始化*/? void?CreateTree(BiTNode?*T,int?pre_f,int?pre_l,int?in_f,int?in_l,char?pre[],char?in[])/*建立二叉树*/? void?PrintBiTree(BiTNode?*T,int?n)/*输出二叉树*/?? 3.详细设计? （1）用两个一维数组A和B分别存放前序和中序序列。? （2）将前序和中序序列分别读入数组A和B。? （3）根据定义，前序序列中第一个元素一定是树根，在中序序列中该元素之前的所有元素一定在左子树中，其余元素则在右子树中。所以，首先从数组A中取出第一个元素A[0]作根结点，然后在数组B中找到A[0]，以它为界，在其前面的是左子树中序序列，在其后面的是右子树中序序列。? （4）若左子树不为空，沿前序序列向后移动，找到左子树根结点，转2。? （5）左子树构造完毕后，若右子树不为空，沿前序序列向后移动，找到右子树根结点，转2。? （6）前序序列中各元素取完则二叉树构造完毕。? （7）对二叉树进行前序和中序遍历，并将结果分别与数组A和B进行比较，若相同，则证明二叉树构造正确。 ?? 三、调试分析? 1、算法的时间复杂度分析：函数的时间复杂度与所要构建二叉树的节点数n有关。由分析知算法实现的时间复杂度为：O(n)。? ? 2、空间复杂度分析：空间复杂度也是与二叉树的节点数n有关，由分析知算法实现的空间复杂度为：O(n)。 3、经验体会 在设计和调试过程中我遇到了很多问题，虽说平时上课听讲也算比较认真，但是真的实际操作起来却又是不是一样的了。最 开始的时候我在主函数中初始化时申请了一个节点，然后在创建二叉树的时候有申请了一个节点，所以就多了一个根节点，在函数运行输出的序列中多了一个问号。解决方法是，把主函数中的节点在调用函数后返回根节点。还有很多其他的问题，我都是一筹莫展，还好通过认真看书还有请教老师以及和同学商量讨论后减少了一些些疑惑。 用户手册 在通常情况下，只要已知二叉树的前序和中序序列，就可以唯一地确定一颗二叉树。程序的功能是实现在已知前序和中序序列的情况下唯一地创建一颗二叉树，并以前序和中序遍历输出这颗创建好的二叉树的前序和中序序列，并且把原输入的序列进行比较。 运行结果 1、输入的数据为：? 前序序列为ABDEGCFHIJ，中序序列为DBGEAHFIJC。 2、运行结果 源程序清单 #include?stdio.h? #include?Stdlib.h? #include?string.h? #define?MaxSize?50? ? typedef?struct?Node? {? char?data;? struct?Node?*LeftChild;? struct?Node?*RightChild;? }BiTNode;? void?Initiate(BiTNode?**root) {? *root=(BiTNode?*)malloc(sizeof(BiTNode));? (*root)-LeftChild=NULL;? (*root)-RightChild=NULL;? }? void?Visit(char?item)? {? printf(%c,item); }? void?PreOrde