二叉树的最近公共祖先

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