求二叉树中两结点最近的共同祖先

《求二叉树中两结点最近的共同祖先》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、沈阳航空航天大学课程设计报告目录沈阳航空航天大学I学术诚信声明I1题目介绍和功能要求41.1题目介绍41.2功能要求42课程设计原理42.1课设题目粗略分析42.2原理图介绍52.2.1功能模块52.2.2intmain()主函数模块62.2.3Node*Create()创建二叉树模块72.2.4Node*closest_common_ancestor(Node*r,intu,intv)计算公共结点模块83主要函数描述93.1创建二叉树函数93.2计算最近共同祖先函数93.3画出二叉树函数94调试与分析104.1调试过程105运行结果115.1初始界面115.2创建二叉树界面115.3显

2、示二叉树大概构成界面125.4输入两个结点计算最近共同祖先界面12参考文献14附录（关键部分程序清单）156沈阳航空航天大学课程设计报告1题目介绍和功能要求1.1题目介绍1、根据键盘输入数据创建二叉树（默认采用先序遍历创建二叉树），结点数不少于5个。2、假设二叉树采用二叉链的结构存储，p^和q^为二叉树中的两个结点，编写程序计算它们最近的共同祖先并输出。1.2功能要求1、有提示语句可以选择是否退出程序。2、具有判别输入结点是否为该树结点的功能。3、p、q两个结点可选，输出显示出树的大概构成情况。2课程设计原理2.1课设题目粗略分析根据课设题目要求，拟将程序设计成八个模块。以下是八个模块的

3、大体分析：1、intmain()主函数模块2、intmenu()提示语句模块3、Node*Create()创建二叉树模块4、voiddds(Node*p,Node*r)创建父结点模块5、voidDraw(Node*r)显示二叉树大概构成模块6、Node*find(Node*p,intu)查找结点模块7、Node*closest_common_ancestor(Node*r,intu,intv)计算公共结点模块8、voidclear(Node*r)清空标记模块6沈阳航空航天大学课程设计报告2.2原理图介绍2.2.1功能模块LCA生成模板查找模板显示模板计算模板图2.2.1功能模块6沈阳航空

4、航天大学课程设计报告2.2.2intmain()主函数模块图2.2.2主函数模块6沈阳航空航天大学课程设计报告2.2.3Node*Create()创建二叉树模块图2.2.3创建二叉树模块6沈阳航空航天大学课程设计报告2.2.4Node*closest_common_ancestor(Node*r,intu,intv)计算公共结点模块图2.24计算最近共同结点模块3主要函数描述3.1创建二叉树函数6沈阳航空航天大学课程设计报告调用递归，采用先序遍历创建二叉树，同时创建每个结点的父结点。根结点的父结点为NULL，左孩子和右孩子的父结点为他们的双亲，以链式存储结构存储二叉树。3.2计算最近共同

5、祖先函数给出任意两个结点P和Q后，先从P开始向上遍历父结点，并进行标记，直至指针指向NULL。接着，从Q开始遍历其父结点，当指针遇到标记时退出循环。输出最近共同祖先，否则无共同结点。3.3画出二叉树函数用一个二维数组graph[][]表示图型，第一维表示图的横坐标，第二维表示图的纵坐标，然后通过cal_d()函数计算出整个二叉树的高度，cal_d()函数是一个递归函数，从根结点向下遍历，获取最大深度即为二叉树高度，然后从二叉树顶部向左右结点递归建图，在二维数组中画出主要形状后，以打印字符形式把图形输出。6沈阳航空航天大学课程设计报告4调试与分析4.1调试过程在调试程序是主要遇到以下几类问

6、题：1、基本语法错误解决方法：因为这属于对于C语言基础知识掌握的问题，所以查阅了相关书籍询问了老师和同学，最终改正。2、如何创建二叉树，并创建每个结点的父结点解决方法：调用递归，采用链式存储结构先序遍历创建二叉树，空结点设为-1。根结点的父结点为NULL，左孩子和右孩子的父结点为他们的双亲。3、二叉树表示模块解决方法：用一个二维数组表示二叉树，然后计算出整个二叉树的高度，从顶部向下递归建图。20沈阳航空航天大学课程设计报告5运行结果5.1初始界面5.2创建二叉树界面20沈阳航空航天大学课程设计报告采用先序遍历创建二叉树，空结点为-1，创建二叉树：21749385.3显示二叉树大概构成界面

7、5.4输入两个结点计算最近共同祖先界面选择输入4和7两个结点，它们的最近共同祖先为4。20沈阳航空航天大学课程设计报告输入1和8两个结点，它们的最近共同祖先为2。输入5和7两个结点，它们没有最近共同祖先。20沈阳航空航天大学课程设计报告参考文献[1]高富平，张楚.电子商务法［M］.北京：北京大学出版社，2002[2]HuangSC，HuangYM，ShiehSM．Vibrationandstabilityofarotatingsha