二叉樹的最近公共祖先

A. 最近公共祖先的演算法實例

問題描述：
設計一個演算法，對於給定的樹中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;}

B. 二叉樹按順序方式存儲在數組A[1....N]中,設計演算法求出下標分別為I和J的兩個節點的最近的 公共祖先節點的值

就是上面這樣 沒有錯誤

C. 最近公共祖先的簡介

另一種理解方式是把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

D. 如何求二叉樹最接近的共同祖先

【以下轉載自網路】
首先，題目中沒有明確說明節點的結構，所以這里分這兩種情況討論：

1. 二叉樹節點具有父指針

在節點具有父指針的情況下，顯然此二叉樹就可以看成是通過父指針連接的"T"型鏈表，題目也就轉化成查找"T"型鏈表的第一個公共節點。假設p，q分別為所求的兩個節點，則通過遍歷一遍可以知道p，q分別到根節點的長度pLen和qLen。這樣就知道pLen和qLen之間長度之差，也就知道p、q到它們的第一個公共祖先節點k長度之差L。因為p，q到根節點的路徑中都包含k到根節點的路徑，所以pLen和qLen之差等於p、q到k的長度之差。然後，讓p、q到根節點路徑長度大的先向前走L，然後長度小再和大的同時向前遍歷，當它們兩指向同一個節點時，則那個節點即是所求。

[java] view plainprint?
/**
* 有父指針情況下，查找兩個節點的最低公共節點
* @author chosen0ne
* 2011-01-18
*/
class BTree<T>{
private BTNode<T> root;
public BTree(BTNode<T> r){
this.root=r;
}
/**
* 查找兩個節點的最低公共祖先節點
* @param p
* @param q
* @return BTNode<T> 最低公共祖先節點，沒有找到返回null
*/
public BTNode<T> findLowestAncestor(BTNode<T> p,BTNode<T> q){
if(p==null||q==null)
throw new NullPointerException();
int pLen=0,qLen=0;//p，q兩個節點到根節點的路徑長度
//計算p到根節點的長度
for(BTNode<T> ancestor=p.parent;ancestor!=null;ancestor=ancestor.parent)
pLen++;
//計算q到根節點的長度
for(BTNode<T> ancestor=q.parent;ancestor!=null;ancestor=ancestor.parent)
qLen++;
//如果p到根節點的長度比q長，則讓p前進pLen-qLen
for(;pLen>qLen;pLen--)
p=p.parent;
//如果q到根節點的長度比p長，則讓q前進qLen-pLen
for(;qLen>pLen;qLen--)
q=q.parent;
//此時，p和q到根節點的長度相同。假設k是最近的公共節點，則p和q到k的長度相同
//p和q按照相同步長1向前遍歷，如果存在公共節點則p和去會同時指向它
while(q!=null&&p!=null&&p!=q){
q=q.parent;
p=p.parent;
}
if(p==q)
return p;
return null;
}
/**
* 測試方法，在t中查找a，b的最低公共祖先節點
* @param t
* @param a
* @param b
*/
private static<T> void test(BTree<T> t, BTNode<T> a, BTNode<T> b){
BTree.BTNode<T> p=t.findLowestAncestor(b,a);
if(p!=null)
System.out.println(a.data+","+b.data+"的最低公共祖先節點是 ："+p.data);
else
System.out.println(a.data+","+b.data+"沒有公共祖先節點");
}
public static void main(String[] arg){
/* 構造如下二叉樹
a
/ /
b c
/ / / /
d e f g
*/
BTree.BTNode<String> g=new BTree.BTNode().data("g");
BTree.BTNode<String> f=new BTree.BTNode().data("f");
BTree.BTNode<String> e=new BTree.BTNode().data("e");
BTree.BTNode<String> d=new BTree.BTNode().data("d");
BTree.BTNode<String> c=new BTree.BTNode().data("c").left(f).right(g);
f.parent(c);
g.parent(c);
BTree.BTNode<String> b=new BTree.BTNode().data("b").left(d).right(e);
d.parent(b);
e.parent(b);
BTree.BTNode<String> a=new BTree.BTNode().data("a").left(b).right(c);
b.parent(a);
c.parent(a);
BTree<String> t=new BTree<String>(a);
test(t,c,f);
}
static class BTNode<T>
{
BTNode<T> left;
BTNode<T> right;
BTNode<T> parent;
T data;
public BTNode(){}
public BTNode(BTNode<T> l,BTNode<T> r,BTNode<T> p,T d){
this.left=l;
this.right=r;
this.parent=p;
this.data=d;
}
BTNode<T> left(BTNode<T> l){
this.left=l;
return this;
}
BTNode<T> right(BTNode<T> r){
this.right=r;
return this;
}
BTNode<T> parent(BTNode<T> p){
this.parent=p;
return this;
}
BTNode<T> data(T d){
this.data=d;
return this;
}
}
}

2.二叉樹節點不具有父指針
這種情況下，必須通過遍歷查找一個節點的祖先集合，然後比較兩個節點的祖先集合就可以找到最低的那個。這里採用後序遍歷，並傳入一個棧記錄該節點的祖先節點。在每次訪問一個節點時，先把這個節點壓入棧，然後判斷該節點是不是要查找的那個節點，如果是返回。接著查找它的左子樹和右子樹，當要查找的節點在它的左右子樹中則返回。然後判斷該節點與棧頂節點是否相同，是則彈出棧頂元素。這是因為相同就代表了在訪問它的左右子樹時沒有添加新的節點，也就是說要查找的那個節點不在它的左右子樹中，則該節點也就是不是要查找的節點的祖先。

[java] view plainprint?
import java.util.ArrayList;
/**
* 沒有父指針情況下，查找兩個節點的最低公共節點
* @author chosen0ne
* 2011-01-18
*/
class BTree<T>
{
private BTNode<T> root;
public BTree(BTNode<T> r){
this.root=r;
}
/**
* 查找兩個節點的最低公共祖先節點
* @param p
* @param q
* @return BTNode<T> 最低公共祖先節點，沒有找到返回null
*/
public BTNode<T> findLowestAncestor(BTNode<T> p,BTNode<T> q){
if(p==null||q==null)
throw new NullPointerException();
ArrayList<BTNode<T>> sp=new ArrayList<BTNode<T>>();
ArrayList<BTNode<T>> sq=new ArrayList<BTNode<T>>();
travalPostOrder(root,p,sp);
travalPostOrder(root,q,sq);
//祖先棧中，以先後順序存儲，所以這里倒序來遍歷以便找到最低的那個祖先節點
for(int i=sp.size()-1;i>=0;i--)
for(int j=sq.size()-1;j>=0;j--)
if(sp.get(i)==sq.get(j))
return sp.get(i);
return null;
}
/**
* 後序遍歷二叉樹，進行節點的搜索，當搜索成功時，將該節點的所有祖先存入棧中
* @param n 遍歷的節點
* @param p 欲搜索的節點
* @param stack 存儲祖先節點的棧，這里使用ArrayList，因為後續查找最低公共祖先時需要遍歷所有元素
* @return boolean 是否搜索到該節點
*/
private boolean travalPostOrder(BTNode<T> n,BTNode<T> p,ArrayList<BTNode<T>> stack){
if(n!=null){
stack.add(n);
if(n==p)
return true;
if(travalPostOrder(n.left,p,stack))
return true;
if(travalPostOrder(n.right,p,stack))
return true;
int lastIndex=stack.size()-1;
//如果搜索完n的左右子樹後，棧頂還是n，則代表n不是p的祖先節點，所以將n從棧中刪除
if(n==stack.get(lastIndex)){
stack.remove(lastIndex);
}
}
return false;
}
/**
* 測試方法，在t中查找a，b的最低公共祖先節點
* @param t
* @param a
* @param b
*/
private static<T> void test(BTree<T> t, BTNode<T> a, BTNode<T> b){
BTree.BTNode<T> p=t.findLowestAncestor(b,a);
if(p!=null)
System.out.println(a.data+","+b.data+"的最低公共祖先節點是 ："+p.data);
else
System.out.println(a.data+","+b.data+"沒有公共祖先節點");
}
public static void main(String[] arg){
/* 構造如下二叉樹
a
/ /
b c
/ / / /
d e f g
*/
BTree.BTNode<String> g=new BTree.BTNode().data("g");
BTree.BTNode<String> f=new BTree.BTNode().data("f");
BTree.BTNode<String> e=new BTree.BTNode().data("e");
BTree.BTNode<String> d=new BTree.BTNode().data("d");
BTree.BTNode<String> c=new BTree.BTNode().data("c").left(f).right(g);
BTree.BTNode<String> b=new BTree.BTNode().data("b").left(d).right(e);
BTree.BTNode<String> a=new BTree.BTNode().data("a").left(b).right(c);
BTree<String> t=new BTree<String>(a);
test(t,a,b);
}
static class BTNode<T>
{
BTNode<T> left;
BTNode<T> right;
T data;
public BTNode(){}
public BTNode(BTNode<T> l,BTNode<T> r,T d){
this.left=l;
this.right=r;
this.data=d;
}
BTNode<T> left(BTNode<T> l){
this.left=l;
return this;
}
BTNode<T> right(BTNode<T> r){
this.right=r;
return this;
}
BTNode<T> data(T d){
this.data=d;
return this;
}
}
}

在沒有父指針時，還可以給每個節點添加一個計數器，在進入一個節點時加1，在退出該節點時減1。訪問該節點時，如果要查找的節點在該節點的子樹中，則返回。實際上，這和上面的演算法思想是一樣的，只是實現不同。
這兩種演算法的時間復雜度都是O(n)，效率不錯。沒有父指針的情況，空間復雜度也是O(n)。

E. 編寫一個程序計算他們最近的共同祖先所指的結點(在線等)

說思路吧，很簡單的，相信你寫得出來
首先預處理每個結點在樹中的深度
下面是主要步版驟
while( p所指權結點 != q 所指結點 )
{
if p所指結點較深 就將p指向它的父結點
if q所指結點較深 就將q指向它的父結點
if 深度相同 就同時指向各自的父結點
}
當循環退出時 p , q 所指結點就是最近公共祖先
你要用什麼編程語言呢？

F. 如何求一個二叉排序樹兩個節點的公共祖先

搜索二叉樹的特點：
任意一個節點的左子樹的所有節點值都比該節點的專值小，其右子樹的屬所有節點值都比該節點的值大。
解決該問題方法：
從樹的根節點開始和兩個節點作比較，如果當前節點的值比兩個節點的值都大，則這兩個節點的最近公共祖先節點一定在該節點的左子樹中，則下一步遍歷當前節點的左子樹；
如果當前節點的值比兩個節點的值都小，則這兩個節點的最近公共祖先節點一定在該節點的右子樹中，下一步遍歷當前節點的右子樹；這樣直到找到第一個值是兩

G. 二叉搜索樹中的最近公共祖先，求各位大神幫忙呀

//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;
}

H. 給出n，q 代表一個樹有n個點 q代表有q個詢問，詢問a，b的最近公共祖先是哪一個

由題意知，每個字母代表兩位數密碼，即字母所處的位置，第一個數字是指行數，第二個版數字是指列數，權
所以，密碼12-35-54代表單詞為：BOX；
單詞SEVEN所編譯成的密碼是：44-15-52-15-34．
故答案為：BOX，44-15-52-15-34．

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

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

J. 根結點的祖先

根結點沒有父結點,祖先結點
2和4的最近公共祖先結點是1