请教高手啊 谢谢；了

1
/ \
2 5
/ \ / \
3 4 6 7
以这棵树为例

[此贴子已经被作者于2006-6-1 19:43:30编辑过]

int i=0;
分别求出两点的层数m,n;指针pq分别指向这两点
int f(&m,&n,*p,*q){
if (m==n)
{
if(这两点是同一点)return(i);//返回的i的值就是距离
else { 指向两点的两指针p,q分别指向其双亲，m-=1;n-=1;i+=2; f(m,n,p,q) }
}
if (m!=n){
if (m>n){m-=1;i+=1;p指向其双亲;f(m,n,p,q)};
if (m<n){n-=1;i+=1;q指向其双亲;f(m,n,p,q)};
}
if(m<1或n<1)出错,这树不存在.
}

假设要求3和5之间的距离,分别求出3和5所在的层数,m=3,n=2,因为m>n,所以i+=1;m-=1;p指向2。这时m=2=n;由于2和5不是同一点,所以i+=2; p指向1，q指向1 。这时p，q指向同一点，返回i的值。
此时i=3;为3和5之间的距离。

[此贴子已经被作者于2006-6-1 22:40:55编辑过]

算法已经写的很清楚了，程序自己搞定

,给我评了个精华啊，那我再说清楚点好了。
最基本的思想是，无论是哪两个点，只要它们在同一棵树中，那么他们必定会有共同的祖先（不包含一个是另一个的祖先的情况）或是一个是另一个的祖先。那么前一种只要找到距离它们最近的共同祖先，然后算出他们和共同祖先的距离，相加就可以得到结果了。后一种更简单了，一个是另一个的祖先，直接算距离，很容易就求出来了。
以2楼的树再举例子，3和6的最近共同祖先是1，3到1的距离为2，6到1的距离为2，所以3和6的距离为2+2＝4；而如果要求3和1的距离，那么直接计算就行了。
实际上在具体的算法中不必这么麻烦，或是想办法去判断到底是第一种情况还是第2种情况。当所求的两点在同一层次的时候，只需要判断他们是不是同一点，如果是同一点，那么要么已经找到了共同的祖先，要么其中一个是另一个的祖先。如果不是同一点，那就说明还没找到共同祖先，继续将指向两个点的指针指向其双亲。而不在同一层时，只需要 把指向深度大的那点的指针，指向其双亲。

感觉比较简单的算法：
1。算出两个点的深度。 (复杂度约Log(2)N)
2。深度多的找父亲节点，知道和另一个同深度。(每走一步距离加1)
3。两个节点同时向上一级找，直到找到相同的父亲。(每走一步距离各加1)

和我最开始的时候想的是一样的。不过这个算法不大完全,当一个节点是另一个节点的祖先时会多算2的距离。据个简单的例子，A是B的父亲，那么AB间距离为1。安照算法B首先找到A，+1,然后AB有共同的父亲，分别+1，那么算出来的距离就为3了。所以当AB到达同一深度的时候，有必要判断AB是不是同一个点，光判断是否有同一个父亲是不够的。

当然，写程序的时候对这种情况while语句是进不去的，第0次就结束了。

原来如此，咱两的算法本质上是一样的，只不过你用while循环，我用的是递归。
PS： 有时间多过来坐坐，切磋切磋，我们这里正缺一个C++高手呢。

呵呵，就这么个简单的程序还争论这么多啊~！佩服