求二叉树中两结点最近的共同祖先文档格式.doc
- 文档编号:4642452
- 上传时间:2023-05-03
- 格式:DOC
- 页数:21
- 大小:403.24KB
求二叉树中两结点最近的共同祖先文档格式.doc
《求二叉树中两结点最近的共同祖先文档格式.doc》由会员分享,可在线阅读,更多相关《求二叉树中两结点最近的共同祖先文档格式.doc(21页珍藏版)》请在冰点文库上搜索。
2、假设二叉树采用二叉链的结构存储,p^和q^为二叉树中的两个结点,编写程序计算它们最近的共同祖先并输出。
1.2功能要求
1、有提示语句可以选择是否退出程序。
2、具有判别输入结点是否为该树结点的功能。
3、p、q两个结点可选,输出显示出树的大概构成情况。
2课程设计原理
2.1课设题目粗略分析
根据课设题目要求,拟将程序设计成八个模块。
以下是八个模块的大体分析:
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)清空标记模块
2.2原理图介绍
2.2.1功能模块
LCA
生成模板
查找模板
显示模板
计算模板
图2.2.1功能模块
2.2.2intmain()主函数模块
图2.2.2主函数模块
2.2.3Node*Create()创建二叉树模块
图2.2.3创建二叉树模块
2.2.4Node*closest_common_ancestor(Node*r,intu,intv)计算公共结点模块
图2.24计算最近共同结点模块
3主要函数描述
3.1创建二叉树函数
调用递归,采用先序遍历创建二叉树,同时创建每个结点的父结点。
根结点的父结点为NULL,左孩子和右孩子的父结点为他们的双亲,以链式存储结构存储二叉树。
3.2计算最近共同祖先函数
给出任意两个结点P和Q后,先从P开始向上遍历父结点,并进行标记,直至指针指向NULL。
接着,从Q开始遍历其父结点,当指针遇到标记时退出循环。
输出最近共同祖先,否则无共同结点。
3.3画出二叉树函数
用一个二维数组graph[][]表示图型,第一维表示图的横坐标,第二维表示图的纵坐标,然后通过cal_d()函数计算出整个二叉树的高度,cal_d()函数是一个递归函数,从根结点向下遍历,获取最大深度即为二叉树高度,然后从二叉树顶部向左右结点递归建图,在二维数组中画出主要形状后,以打印字符形式把图形输出。
沈阳航空航天大学课程设计报告
4调试与分析
4.1调试过程
在调试程序是主要遇到以下几类问题:
1、基本语法错误
解决方法:
因为这属于对于C语言基础知识掌握的问题,所以查阅了相关书籍询问了老师和同学,最终改正。
2、如何创建二叉树,并创建每个结点的父结点
调用递归,采用链式存储结构先序遍历创建二叉树,空结点设为-1。
根结点的父结点为NULL,左孩子和右孩子的父结点为他们的双亲。
3、二叉树表示模块
解决方法:
用一个二维数组表示二叉树,然后计算出整个二叉树的高度,从顶部向下递归建图。
5运行结果
5.1初始界面
5.2创建二叉树界面
采用先序遍历创建二叉树,空结点为-1,创建二叉树:
2
1
7
4
9
3
8
5.3显示二叉树大概构成界面
5.4输入两个结点计算最近共同祖先界面
选择输入4和7两个结点,它们的最近共同祖先为4。
输入1和8两个结点,它们的最近共同祖先为2。
输入5和7两个结点,它们没有最近共同祖先。
参考文献
[1]高富平,张楚.电子商务法[M].北京:
北京大学出版社,2002
[2]HuangSC,HuangYM,ShiehSM.Vibrationandstabilityofarotatingshaftcontainingatransersecrack[J],JSoundandVibration,1993,162(3):
387-401.
[3]严蔚敏,吴伟民.数据结构(c语言版)[M].北京:
清华大学教育出版社,2006
[4]戴艳等.零基础学算法[M].北京:
机械工业出版社.2012
20
沈阳航空航天大学课程设计报告
附录(关键部分程序清单)
#include<
stdio.h>
stdlib.h>
string.h>
#definemaxv1024
typedefstructNode{
intvalue,mark;
structNode*lc,*rc,*pa;
}Node;
intgraph[maxv][maxv];
Node*Create();
voiddfs(Node*p,Node*r);
//**设置父结点
Node*find(Node*p,intu);
//**查找
voidclear(Node*p);
//**清空标记
Node*closest_common_ancestor(Node*r,intu,intv);
//**计算最近共同祖先
intmenu();
Node*Build();
//**构建二叉树
voidCalculate(Node*r);
intMax(inta,intb);
//**比较a和b谁大
intcal_d(Node*r,intd);
//**计算二叉树的高度
voidDFS(Node*r,inth,intw,intd);
//**递归建图
voidDraw(Node*r);
//**画出二叉树
intmain()
{
Node*r;
while
(1){
switch(menu()){
case1:
r=Build();
break;
case2:
Calculate(r);
case3:
Draw(r);
case0:
return0;
}
}
return0;
}
Node*Create()
intn;
Node*p;
scanf("
%d"
&
n);
if(n==-1)returnNULL;
p=(Node*)malloc(sizeof(Node));
p->
value=n;
lc=Create();
rc=Create();
returnp;
voiddfs(Node*p,Node*r)
pa=r;
if(p->
lc)dfs(p->
lc,p);
rc)dfs(p->
rc,p);
Node*find(Node*p,intu)
Node*t;
value==u)returnp;
lc){
t=find(p->
lc,u);
if(t)returnt;
rc){
rc,u);
Node*closest_common_ancestor(Node*r,intu,intv)
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->
returnq;
voidclear(Node*r)
r->
mark=0;
if(r->
lc)clear(r->
lc);
rc)clear(r->
rc);
intmenu()
intoption;
printf("
\n---------------------------\n"
);
1、创建二叉树\n"
2、计算最近公共祖先\n"
3、显示二叉树\n"
0、退出\n"
---------------------------\n"
option);
returnoption;
Node*Build()
前序遍历创建一棵二叉树:
\n"
p=Create();
dfs(p,0);
voidCalculate(Node*r)
intu,v;
输入两点:
%d%d"
u,&
v);
clear(r);
p=closest_common_ancestor(r,u,v);
if(!
p)printf("
没有公共祖先\n"
elseprintf("
%d和%d的最近公共祖先是:
%d\n"
u,v,p->
value);
intMax(inta,intb)
returna>
b?
a:
b;
intcal_d(Node*r,intd)
intt=d;
lc)t=Max(t,cal_d(r->
lc,d+1));
rc)t=Max(t,cal_d(r->
rc,d+1));
returnt;
voidDFS(Node*r,inth,intw,intd)
inti;
r->
lc&
&
!
graph[h][w]=r->
value+'
0'
;
return;
graph[h][w]=r->
for(i=1;
i<
=(1<
<
d-2);
i++)
graph[h][w-i]='
-'
graph[h-1][w-(1<
d-2)]='
|'
DFS(r->
lc,h-2,w-(1<
d-2),d-1);
graph[h][w+i]='
graph[h-1][w+(1<
rc,h-2,w+(1<
voidDraw(Node*r)/**画出二叉树
intd,h,w,i,j;
r)return;
d=cal_d(r,1);
h=d*2;
w=1<
d-1;
DFS(r,h,w,d);
for(i=h;
i>
=0;
i--){
for(j=0;
j<
w*2;
j++){
if(!
graph[i][j])putchar('
'
elseputchar(graph[i][j]);
putchar('
\n'
沈阳航空航天大学课程设计报告
课程设计总结:
这次课程设计让我收获很多。
这次的课设题目是求二叉树中任意两点的最近共同祖先,即经典的LCA(LowestCommonAncestor)题型。
求解此问题的算法有很多,我在做这次的课设中采用的主要思路是:
令每条树上左孩子和右孩子的父亲为父结点,根结点的父结点为NULL,在存储二叉树的同时存储每个结点的父结点。
给出任意两个结点P和Q后,先从P开始向上遍历父结点,并进行标记,直至NULL。
通过这次课设,让自己学到很多,首先是在面对自己从未见过的问题时,应该从已知的知识入手,首先是二叉树的先序存储,其次是二叉树中祖先与子孙之间的关系。
此次课设,运用了递归的调用,以前对于递归只知道递归的形式不知道如何调用,面临瓶颈的时候,身边的同学给予了很大的帮助,同时,在数据结构性相关书籍中也找到了相应的内容。
同时在这次课设中个,我也发现了自己许多的不足。
一方面,C语言的基础
并没有很扎实,会犯低级错误。
另一方面,缺少实践积累,面对经典题型时会手足无措。
为了解决这两个问题,我计划利用假期时间,重新学习C语言,同时扩充自己的眼界,寻找经典例题进行编译。
在今后的学习中,多多请教身边的同学和老师,同时勤加练习。
最后,再一次感谢此次课设中帮助过我的同学和我的指导老师,谢谢!
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉 树中两 结点 最近 共同 祖先