最近公共祖先

❶ 数据结构求两节点的最近共同祖先，用二叉链表作为存储结构，严蔚敏习题集答案如下，一疑点求解释

额，你所使用方法是来很慢的，并源且不常用的。
我说一个一般的算法，不仅仅适用于二叉树，多叉树也可以。
f[i]表示i节点的父亲。d[i]表示i节点深度。//可以通过深搜预处理出来。
//求xy的最近公共祖先：
while (deep[x]>deep[y]) x=f[x];
while (deep[x]<deep[y]) y=f[y];
while (x<>y) {x=f[x];y=f[y]}
return x;

❷ 二叉树按顺序方式存储在数组A[1....N]中,设计算法求出下标分别为I和J的两个节点的最近的 公共祖先节点的值

就是上面这样 没有错误

❸ 求最近公共祖先的tarjan算法pascal标程

首先从顶点a出发，沿父指针将a至根的路径上的所有顶点设访问标志。然后从b顶点出发，沿父指针追溯到第1个已访问的顶点b，该顶点即为a和b的最近公共祖先。
var
n,rt,a,b,i:integer;{顶点数为n，根为rt}
l,r,pt:array[0..max]of integer; {左儿子序列、右儿子序列和父指针序列，其中顶点I的左儿子为l[i]、右儿子为r[i]、父指针为pt[i]}
vt:array[1..max]of boolean;{访问序列，其中vt[i]为顶点I的访问标志}
readln(f,n,rt);{输入顶点数及其根}
for i:=1 to n do
begin
readln(l[i],r[i]);{输入顶点I的左右儿子}
if i=rt then pt[rt]:=0
else pt[l[i]]:=i; pt[r[i]]:=i
end;
readln(a,b);{输入两个顶点}
while a*b<>0 do{反复计算，直至终止标志}
begin
fillchar(vt,sizeof(vt),0);{将a至根的路径上的所有顶点设访问标志}
repeat vt[a]:=true;a:=pt[a] until a=0;
while not vt[b] do b:=pt[b];{从b顶点出发，沿父指针追溯第1个已访问的顶点b，该顶点即为a和b的最近公共祖先}
writeln(b);readln(a,b);
End;

❹ 最近公共祖先的算法实例

问题描述：
设计一个算法，对于给定的树中2 结点返回它们的最近公共祖先。
编程任务：
对于给定的树，和树中结点对，编程计算结点对的最近公共祖先。
数据输入：
由文件input.txt给出输入数据。第一行有1个正整数n，表示给定的树有n个顶点，编
号为1，2，…，n。编号为1 的顶点是树根。接下来的n 行中，第i+1 行描述与i 个顶点相关联的子结点的信息。每行的第一个正整数k表示该顶点的儿子结点数。其后k个数中，每1 个数表示1 个儿子结点的编号。当k=0 时表示相应的结点是叶结点。文件的第n+2 行是1 个正整数m，表示要计算最近公共祖先的m个结点对。接下来的m行，每行2 个正整数，是要计算最近公共祖先的结点编号。
结果输出:
将编程计算出的m个结点对的最近公共祖先结点编号输出到文件output.txt。每行3 个
正整数，前2 个是结点对编号，第3 个是它们的最近公共祖先结点编号。
输入文件示例 输出文件示例
input.txt
12
3 2 3 4
2 5 6
0
0
2 7 8
2 9 10
0
0
0
2 11 12
0
0
5
3 11
7 12
4 8
9 12
8 10
output.txt
3 11 1
7 12 2
4 8 1
9 12 6
8 10 2 #include<iostream>#include<fstream>usingnamespacestd;/********************快速排序****************************************/inlinevoidSwap(int&a,int&b){inttemp=a;a=b;b=temp;}///:pintPartition(int*a,intp,intr){inti=p;intj=r+1;intx=a[p];while(true){while(a[++i]<x&&i<r);while(a[--j]>x);if(i>=j){break;}Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}///:pvoidQuickSort(int*a,intp,intr){if(p<r){intq=Partition(a,p,r);QuickSort(a,p,q-1);QuickSort(a,q+1,r);}}///:p/*******************************************************************//***************二分法查找******************************************/intFindSource(int*array,intsource,intlow,inthigh){intmid;while(low<=high){mid=(low+high)/2;if(source==array[mid]){returnsource;}else{if(source<array[mid]){high=mid-1;}else{low=mid+1;}}}return-1;}///:p/*******************************************************************/classCommonTree{public:CommonTree(intMax=10);~CommonTree();voidgetdata(int*treedata,intnum);intfind_same_ancestor(intNode1,intNode2,intarray_num);voidgetroot(inti);intSize();voidPrint()const;private:int*TreeArray;intsize;introot;};///:pCommonTree::CommonTree(intMax){size=Max;TreeArray=newint[size];if(TreeArray==NULL){exit(1);}}///:pCommonTree::~CommonTree(){delete[]TreeArray;}///:pvoidCommonTree::getdata(int*treedata,intnum){int*p_temp=TreeArray;TreeArray=treedata;treedata=p_temp;size=num;delete[]treedata;treedata=NULL;}///:pintCommonTree::find_same_ancestor(intNode1,intNode2,intarray_num){int*array_Node1=newint[array_num];int*array_Node2=newint[array_num];if(array_Node1==NULL&&array_Node2==NULL){exit(1);}intx=Node1,array_Node1_num=0;array_Node1[0]=x;while(x!=root){x=TreeArray[x];array_Node1_num++;array_Node1[array_Node1_num]=x;}x=Node2;intarray_Node2_num=0;array_Node2[0]=x;while(x!=root){x=TreeArray[x];array_Node2_num++;array_Node2[array_Node2_num]=x;}QuickSort(array_Node2,0,array_Node2_num);intresult=0;for(inti=0;i<=array_Node1_num;i++){result=FindSource(array_Node2,array_Node1[i],0,array_Node2_num);if(result!=-1){break;}}delete[]array_Node1;delete[]array_Node2;returnresult;}///:pinlineintCommonTree::Size(){returnsize;}///:pinlinevoidCommonTree::getroot(inti){root=i;}///:pvoidCommonTree::Print()const{for(inti=1;i<size;i++){cout<<this->TreeArray[i]<<;}cout<<endl;cout<<root<<endl;}///:pintmain(){ifstreamin(input.txt);if(in.fail()){cout<<inputerror!<<endl;exit(1);}ofstreamout(output.txt);intNodeNum;in>>NodeNum;int*AncestorTree=newint[NodeNum+1];if(AncestorTree==NULL){exit(1);}memset(AncestorTree,0,sizeof(int)*(NodeNum+1));intfather=1;for(intj=0;j<NodeNum;j++){intlop;in>>lop;for(inti=0;i<lop;i++){inttemp;in>>temp;AncestorTree[temp]=father;}father++;}for(j=1;j<=NodeNum;j++){if(AncestorTree[j]==0){AncestorTree[j]=j;break;}}intfind_num;in>>find_num;int*result=newint[3*find_num];if(result==NULL){exit(1);}for(inti=0;i<2*find_num;i++){in>>result[i];}CommonTreemain_tree(10);main_tree.getdata(AncestorTree,NodeNum+1);main_tree.getroot(j);intdisplace=0;for(i=0;i<find_num;i++){result[2*find_num+i]=main_tree.find_same_ancestor(result[displace],result[displace+1],NodeNum);displace+=2;}displace=0;for(i=0;i<find_num;i++){out<<result[displace]<<<<result[displace+1]<<<<result[2*find_num+i];displace+=2;out<<endl;}delete[]result;return0;}c++代码实现#include<iostream>#include<stdio.h>#include<memory.h>usingnamespacestd;#definemax_size1010intd[max_size],p[max_size][10];inthead[max_size];intcnt;//构造树时用到的机构体，看过一个大牛用的，感觉很好structEdge{intv;intpre;}eg[max_size];//建树的函数voidadd(intx,inty){eg[cnt].v=y;eg[cnt].pre=head[x];head[x]=cnt++;}//dfs()初始整颗数，算出d[1-n],p[1-n][j];voiddfs(intk){if(head[k]==0){return;}intm,x,i,j;for(i=head[k];i!=0;i=eg[i].pre){x=eg[i].v;p[x][0]=k;m=k;d[x]=d[k]+1;for(j=0;p[m][j]!=0;j++){p[x][j+1]=p[m][j];//利用公式p[x][j]=p[p[x][j-1]][j-1],这里的m就是p[x][j-1];m=p[m][j];}dfs(x);}}intfind_lca(intx,inty){intm,k;if(x==y)returnx;if(d[x]<d[y]){m=x;x=y;y=m;}m=d[x]-d[y];k=0;while(m)//将x的深度调到和y的深度一样{if(m&1)x=p[x][k];m>>=1;k++;}if(x==y)returnx;k=0;//向上调节，找最近公共祖先，算法的核心，相当于一个二分查找。while(x!=y){if(p[x][k]!=p[y][k]||p[x][k]==p[y][k]&&k==0)//如果p[x][k]还不相等，说明节点p[x][k]还在所求点的下面，所以继续向上调节//如果相等了，并且就是他们父节点，则那个节点一定就是所求点。{x=p[x][k];y=p[y][k];k++;}else//如果p[x][k]=p[y][k],可以说明p[x][k]一定是x和y的共祖先，但不一定是最近的。//所以向下找看还有没有更近的公共祖先{k--;}}returnx;}intmain(){inti,n,m,x,y;while(cin>>n>>m){memset(head,0,sizeof(head));memset(p,0,sizeof(p));memset(d,0,sizeof(d));cnt=1;for(i=2;i<=n;i++){scanf(%d,&x);add(x,i);}dfs(1);for(i=0;i<m;i++){scanf(%d%d,&x,&y);printf(%d/n,find_lca(x,y));}}return0;}

❺ 编写一个程序计算他们最近的共同祖先所指的结点(在线等)

说思路吧，很简单的，相信你写得出来
首先预处理每个结点在树中的深度
下面是主要步版骤
while( p所指权结点 != q 所指结点 )
{
if p所指结点较深 就将p指向它的父结点
if q所指结点较深 就将q指向它的父结点
if 深度相同 就同时指向各自的父结点
}
当循环退出时 p , q 所指结点就是最近公共祖先
你要用什么编程语言呢？

❻ 给出n，q 代表一个树有n个点 q代表有q个询问，询问a，b的最近公共祖先是哪一个

由题意知，每个字母代表两位数密码，即字母所处的位置，第一个数字是指行数，第二个版数字是指列数，权
所以，密码12-35-54代表单词为：BOX；
单词SEVEN所编译成的密码是：44-15-52-15-34．
故答案为：BOX，44-15-52-15-34．

❼ 最近公共祖先的简介

另一种理解方式是把T理解为一个无向无环图，而LCA(T,u,v)即u到v的最短路上深度最小的点。
这里给回出一个LCA的例子：
对于答T=<V,E>
V={1,2,3,4,5}
E={(1,2),(1,3),(3,4),(3,5)}
则有：
LCA(T,5,2)=1
LCA(T,3,4)=3
LCA(T,4,5)=3

❽ 如何求一个二叉排序树两个节点的公共祖先

搜索二叉树的特点：
任意一个节点的左子树的所有节点值都比该节点的专值小，其右子树的属所有节点值都比该节点的值大。
解决该问题方法：
从树的根节点开始和两个节点作比较，如果当前节点的值比两个节点的值都大，则这两个节点的最近公共祖先节点一定在该节点的左子树中，则下一步遍历当前节点的左子树；
如果当前节点的值比两个节点的值都小，则这两个节点的最近公共祖先节点一定在该节点的右子树中，下一步遍历当前节点的右子树；这样直到找到第一个值是两

❾ 根结点的祖先

根结点没有父结点,祖先结点
2和4的最近公共祖先结点是1

❿ 二叉搜索树中的最近公共祖先，求各位大神帮忙呀

//7(输入:二叉树的结点总数)
//4261357(输入:二叉树的结点)
//57(输入:两个结点u和v)
//LC=6(输出:最近公共祖先)

//对应的二叉树:
//
//4
///
//26
////
//1357

#include<stdio.h>
#include<stdlib.h>

#defineERROR-1
typedefstructTreeNode*Tree;
structTreeNode
{
intKey;
TreeLeft;
TreeRight;
};

TreeBuildTree();
intLCA(TreeT,intu,intv);

intmain()
{
TreeT;
intu,v,ans;

T=BuildTree();

scanf("%d%d",&u,&v);
ans=LCA(T,u,v);
if(ans==ERROR)
printf("Wronginput
");
else
printf("LCA=%d
",ans);

return0;
}

TreeinsertNode(Treeroot,intvalue)
{
Treenewnode;
Treecurrent;
Treeback;
newnode=(Tree)malloc(sizeof(structTreeNode));
if(newnode==NULL)
{
printf("
memoryoverflow!
");
exit(1);
}
newnode->Key=value;
newnode->Left=NULL;
newnode->Right=NULL;
if(root==NULL)
{
returnnewnode;
}
else
{
current=root;
while(current!=NULL)
{
back=current;
if(current->Key>value)
current=current->Left;
else
current=current->Right;
}
if(back->Key>value)
back->Left=newnode;
else
back->Right=newnode;
}
returnroot;
}

TreeBuildTree()//创建二叉树搜索树
{
Treeroot=NULL;
intlen;
intnum;
inti;

//输入结点的个数
scanf("%d",&len);
//连续输入len个数据(用空格隔开)
for(i=0;i<len;i++)
{
scanf("%d",&num);
root=insertNode(root,num);
}

returnroot;
}
intLCA(TreeT,intu,intv)
{
Treep;
intisHere;
p=T;
isHere=0;
while(p!=NULL)
{
if(p->Key==u)
{
isHere=1;
break;
}
else
{
if(p->Key>u)
{
p=p->Left;
}
else
{
p=p->Right;
}
}
}
if(isHere==0)//二叉树没有u
{
returnERROR;
}
p=T;
isHere=0;
while(p!=NULL)
{
if(p->Key==v)
{
isHere=1;
break;
}
else
{
if(p->Key>v)
{
p=p->Left;
}
else
{
p=p->Right;
}
}
}
if(isHere==0)//二叉树没有v
{
returnERROR;
}
p=T;
while(p!=NULL)
{
//如果u和v都小于Key，则LCA位于左子树中
if(p->Key>u&&p->Key>v)
{
p=p->Left;
}
//如果u和v都大于Key,则LCA位于右子树中
elseif(p->Key<u&&p->Key<v)
{
p=p->Right;
}
else//找到最近公共祖先
{
break;
}
}
returnp->Key;
}