二叉树共同祖先求解课设报告.doc

沈阳航空航天大学 课 程 设 计 报 告 课程设计名称：数据结构课程设计 课程设计题目： 二叉树中两结点共同祖先求解 院（系）：计算机学院 专 业：计算机科学与技术  目 录 1 课程设计介绍 1 1.1 课程设计内容 1 1.2 课程设计要求 1 2 课程设计原理 2 2.1 课设题目粗略分析 2 2.2 原理图介绍 2 2.2.1 功能模块图 3 2.2.2 流程图分析 4 3 数据结构分析 8 3.1 存储结构 8 3.2 算法描述 8 4 调试与分析 10 4.1 调试过程 10 4.2程序执行过程 10 参考文献 12 附 录（关键部分程序清单） 13 1 课程设计介绍 此章介绍了本程序的设计内容及要求，本程序利用了栈对二叉树中两结点的共同祖先的求解问题进行了系统化。 1.1 课程设计内容 结点的祖先是指从根结点到所查找结点经过的不包括自身在内的结点。 假设二叉树采用二叉链的结构存储，建立一棵树，然后输入两个值，判断是否在树中存在，若存在则求解这两个值的共同祖先并输出。 1.2 课程设计要求 （1）利用所学知识，设计相应的数据结构； （2）熟练运用开发环境； （3）完成软件的设计与编码； （4）熟练掌握基本的调试方法； （5）提交符合课程设计规范的报告。 2 课程设计原理 此章介绍了本程序的设计原理，对课设题目进行了分析，并对流程图进行了分析介绍。 2.1 课设题目粗略分析 根据课设题目要求，拟将整体程序分为三大模块。此三个模块相互独立，没有嵌套调用的情况，以下是三个模块的大体分析：(通过实例讲解写算法的思路，运行过程) （1）二叉树的创建模块。此模块通过输入二叉树的先序遍历序列创建二叉链表表示的二叉树，输入时以空格键表示空结点。 （2）分别查找祖先模块。此模块用两个栈分别存储输入的两个结点的祖先，通过循环判断，对二叉树的结点进行压栈与出栈操作，最后将从根结点到所输结点经过的结点（即结点的祖先）存入栈中。 （3）共同祖先查找模块。此模块通过比较两个栈中元素，找到所输入的两结点的共同祖先，并执行出栈操作，以实现对两结点共同祖先的查找。 2.2 原理图介绍 此部分主要分为功能模块图和流程图分析两部分。功能模块图将各模块的简单关系表示出来，而流程图则将模块内的执行过程表示出来，更为详尽。 2.2.1 功能模块图 图2.1 功能模块图 功能模块图如图2.1所示。本程序主要分为三大模块：创建二叉树模块，查找祖先模块，查找共同祖先模块。这三个模块是独立的，不互相调用。查找共同祖先模块在查找过程中需要用到查找结点祖先模块得到的栈，通过比较存有两个结点祖先的栈中数据，找到两结点共同祖先。 （1）二叉树的创建模块。此模块通过输入二叉树的先序遍历序列创建二叉链表表示的二叉树，输入时以空格键表示空结点。 （2）分别查找祖先模块。此模块用两个栈分别存储输入的两个结点的祖先，通过循环判断，对二叉树的结点进行压栈与出栈操作，最后将从根结点到所输结点经过的结点（即结点的祖先）存入栈中。 （3）共同祖先查找模块。此模块通过比较两个栈中元素，找到所输入的两结点的共同祖先，并执行出栈操作，以实现对两结点共同祖先的查找。  2.2.2 流程图分析 （1）主函数流程图如图2.2所示。 图2.2 主函数流程图 主函数通过调用子函数实现程序整体的执行。首先调用creatree（）函数创建一棵二叉链式存储结构的二叉树，然后调用preorder（）函数遍历二叉树，再调用find（）函数分别查找所输入两结点的祖先，。当x或y值为-1时，所输入结点在创建的二叉树中不存在；祖先是指从根结点到所查找结点经过的不包括自身在内的结点，因此，当所输结点值与根结点值相等时，找不到输入的两结点的共同祖先；其他情况下，通过调用Ancestor（）函数可以输出共同祖先。 （2）先序遍历创建二叉树的流程图如图2.3所示。 图2.3 先序遍历创建二叉树流程图 此函数的作用是读取所输入的二叉树的先序遍历序列，建立一棵二叉树，若输入空格则该结点为空。对此函数创建的二叉树，再通过preorder()函数先序遍历并输出先序遍历序列。 （3）查找单个结点祖先的流程图如图2.4所示。 图2.4 查找单个结点祖先函数流程图 此函数通过标记数组辅助进行判断，将结点的祖先入栈。若结点有左孩子，则标记为0，循环判断，到左侧分支的最后一个结点时，标记为1。最后，找不到结点或结点祖先时，将x返回-1；当树中结点与所输入的结点相等时，将x返回栈顶位置数值。 （4）查找两结点共同祖先的流程图如图2.5所示。 图2.5 查找共同祖先函数流程图 此函数中，栈sq和sp分别储存所输入的两结点的祖先。只有在树的同一层才可能找到两结点的共同祖先，因此，在栈的top指针位置相同时，比较两