最近公共祖先

❶ 數據結構求兩節點的最近共同祖先，用二叉鏈表作為存儲結構，嚴蔚敏習題集答案如下，一疑點求解釋

額，你所使用方法是來很慢的，並源且不常用的。
我說一個一般的演算法，不僅僅適用於二叉樹，多叉樹也可以。
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;
}