求二叉树中两结点最近的共同祖先(共21页).doc

《求二叉树中两结点最近的共同祖先(共21页).doc》由会员分享，可在线阅读，更多相关《求二叉树中两结点最近的共同祖先(共21页).doc（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上目 录专心-专注-专业 1 题目介绍和功能要求1.1 题目介绍1、 根据键盘输入数据创建二叉树（默认采用先序遍历创建二叉树），结点数不少于5个。2、 假设二叉树采用二叉链的结构存储，p和q为二叉树中的两个结点，编写程序计算它们最近的共同祖先并输出。1.2 功能要求1、 有提示语句可以选择是否退出程序。2、 具有判别输入结点是否为该树结点的功能。3、 p、q两个结点可选，输出显示出树的大概构成情况。2 课程设计原理2.1 课设题目粗略分析根据课设题目要求，拟将程序设计成八个模块。以下是八个模块的大体分析：1、 int main()主函数模块2、 int menu()提示

2、语句模块3、 Node *Create()创建二叉树模块4、 void dds(Node *p, Node *r)创建父结点模块5、 void Draw(Node *r)显示二叉树大概构成模块6、 Node *find(Node *p, int u)查找结点模块7、 Node *closest_common_ancestor(Node *r, int u, int v)计算公共结点模块8、 void clear(Node *r)清空标记模块2.2 原理图介绍2.2.1 功能模块L C A生成模板查找模板显示模板计算模板图2.2.1 功能模块 2.2.2int main()主函数模块图2.2.2

3、 主函数模块2.2.3Node *Create()创建二叉树模块图2.2.3创建二叉树模块2.2.4 Node *closest_common_ancestor(Node *r, int u, int v)计算公共结点模块图2.24计算最近共同结点模块3 主要函数描述3.1 创建二叉树函数调用递归，采用先序遍历创建二叉树，同时创建每个结点的父结点。根结点的父结点为NULL，左孩子和右孩子的父结点为他们的双亲，以链式存储结构存储二叉树。3.2 计算最近共同祖先函数给出任意两个结点P和Q后，先从P开始向上遍历父结点，并进行标记，直至指针指向NULL。接着，从Q开始遍历其父结点，当指针遇到标记时退出

4、循环。输出最近共同祖先，否则无共同结点。3.3画出二叉树函数用一个二维数组graph 表示图型，第一维表示图的横坐标，第二维表示图的纵坐标，然后通过cal_d()函数计算出整个二叉树的高度，cal_d()函数是一个递归函数，从根结点向下遍历，获取最大深度即为二叉树高度，然后从二叉树顶部向左右结点递归建图，在二维数组中画出主要形状后，以打印字符形式把图形输出。4 调试与分析4.1 调试过程在调试程序是主要遇到以下几类问题：1、基本语法错误解决方法：因为这属于对于C语言基础知识掌握的问题，所以查阅了相关书籍询问了老师和同学，最终改正。2、 如何创建二叉树，并创建每个结点的父结点解决方法：调用递归，

5、采用链式存储结构先序遍历创建二叉树，空结点设为-1。根结点的父结点为NULL，左孩子和右孩子的父结点为他们的双亲。3、二叉树表示模块 解决方法：用一个二维数组表示二叉树，然后计算出整个二叉树的高度，从顶部向下递归建图 。5 运行结果5.1初始界面5.2创建二叉树界面采用先序遍历创建二叉树，空结点为-1，创建二叉树：21749385.3显示二叉树大概构成界面5.4输入两个结点计算最近共同祖先界面选择输入4 和 7两个结点，它们的最近共同祖先为4。输入 1 和8两个结点，它们的最近共同祖先为2。输入 5 和 7两个结点， 它们没有最近共同祖先。参考文献1 高富平，张楚 . 电子商务法M. 北京：北

6、京大学出版社，20022 Huang S C，Huang Y M，Shieh S MVibration and stability of a rotating shaft containing a transerse crackJ, J Sound and Vibration，1993，162（3）：3874013严蔚敏，吴伟民. 数据结构（c 语言版）M.北京：清华大学教育出版社，20064戴艳等.零基础学算法M.北京：机械工业出版社.2012附 录（关键部分程序清单）#include #include #include #define maxv 1024typedef struct Nod

7、e int value, mark; struct Node *lc, *rc, *pa; Node;int graphmaxvmaxv;Node *Create();void dfs(Node *p, Node *r); /*设置父结点Node *find(Node *p, int u); /*查找void clear(Node *p); /*清空标记Node *closest_common_ancestor(Node *r, int u, int v);/*计算最近共同祖先int menu();Node *Build(); /*构建二叉树void Calculate(Node *r);in

8、t Max(int a, int b); /*比较a和b谁大int cal_d(Node *r, int d); /*计算二叉树的高度void DFS(Node *r, int h, int w, int d); /*递归建图void Draw(Node *r); /*画出二叉树int main() Node *r; while(1) switch(menu() case 1: r = Build(); break; case 2: Calculate(r); break; case 3: Draw(r); break; case 0: return 0; return 0;Node *Cre

9、ate() int n; Node *p; scanf(%d, &n); if(n=-1) return NULL; p = (Node *)malloc(sizeof(Node); p-value = n; p-lc = Create(); p-rc = Create(); return p;void dfs(Node *p, Node *r) p-pa = r; if(p-lc) dfs(p-lc, p); if(p-rc) dfs(p-rc, p);Node *find(Node *p, int u) Node *t; if(p-value=u) return p; if(p-lc) t

10、 = find(p-lc, u); if(t) return t; if(p-rc) t = find(p-rc, u); if(t) return t; return 0;Node *closest_common_ancestor(Node *r, int u, int v) Node *p = find(r, u); Node *q = find(r, v); while(p) p-mark = 1; p = p-pa; while(q) if(q-mark) break; q = q-pa; return q;void clear(Node *r) r-mark = 0; if(r-lc

11、) clear(r-lc); if(r-rc) clear(r-rc);int menu() int option; printf(n-n); printf(1、创建二叉树n); printf(2、计算最近公共祖先n); printf(3、显示二叉树n); printf(0、退出n); printf(-n); scanf(%d, &option); return option;Node *Build() Node *p; printf(前序遍历创建一棵二叉树：n); p = Create(); dfs(p, 0); return p;void Calculate(Node *r) int u,

12、 v; Node *p; printf(输入两点：n); scanf(%d%d, &u, &v); clear(r); p = closest_common_ancestor(r, u, v); if(!p) printf(没有公共祖先n); else printf(%d和%d的最近公共祖先是：%dn, u, v, p-value);int Max(int a, int b) return ab ? a : b;int cal_d(Node *r, int d) int t = d; if(r-lc) t = Max(t, cal_d(r-lc, d+1); if(r-rc) t = Max(

13、t, cal_d(r-rc, d+1); return t;void DFS(Node *r, int h, int w, int d) int i; if(!r-lc & !r-rc) graphhw = r-value + 0; return ; graphhw = r-value + 0; if(r-lc) for(i=1; i=(1d-2); i+) graphhw-i = -; graphh-1w-(1lc, h-2, w-(1rc) for(i=1; i=(1d-2); i+) graphhw+i = -; graphh-1w+(1rc, h-2, w+(1d-2), d-1);

14、void Draw(Node *r)/*画出二叉树 int d, h, w, i, j; if(!r) return ; d = cal_d(r, 1); h = d*2; w = 1=0; i-) for(j=0; jw*2; j+) if(!graphij) putchar( ); else putchar(graphij); putchar(n); 课程设计总结：这次课程设计让我收获很多。这次的课设题目是求二叉树中任意两点的最近共同祖先，即经典的LCA（Lowest Common Ancestor）题型。求解此问题的算法有很多，我在做这次的课设中采用的主要思路是：令每条树上左孩子和右孩子

15、的父亲为父结点，根结点的父结点为NULL，在存储二叉树的同时存储每个结点的父结点。给出任意两个结点P和Q后，先从P开始向上遍历父结点，并进行标记，直至NULL。接着，从Q开始遍历其父结点，当指针遇到标记时退出循环。输出最近共同祖先，否则无共同结点。通过这次课设，让自己学到很多，首先是在面对自己从未见过的问题时，应该从已知的知识入手，首先是二叉树的先序存储，其次是二叉树中祖先与子孙之间的关系。此次课设，运用了递归的调用，以前对于递归只知道递归的形式不知道如何调用，面临瓶颈的时候，身边的同学给予了很大的帮助，同时，在数据结构性相关书籍中也找到了相应的内容。同时在这次课设中个，我也发现了自己许多的不足。一方面，C语言的基础并没有很扎实，会犯低级错误。另一方面，缺少实践积累，面对经典题型时会手足无措。为了解决这两个问题，我计划利用假期时间，重新学习C语言，同时扩充自己的眼界，寻找经典例题进行编译。在今后的学习中，多多请教身边的同学和老师，同时勤加练习。 最后，再一次感谢此次课设中帮助过我的同学和我的指导老师，谢谢！