前面一篇博客：http://blog.csdn.net/kay_zhyu/article/details/8867839讲了二叉树的一些基本的操作，鉴于内容有点多，所以分成两个，这一部分主要是将怎么求给定的两个节点之间的距离。有两种情况：
3、如果很频繁的询问两个节点的距离，那么就用一个二维数组来维护这个距离，询问的时间就是O(1).当然，如果只是一次询问，那这样做就很费时。
OK，先不管那么多，先说说怎么去维护任意两个节点的距离。假设我需要求b和e两个节点的距离。那么他们之间的最小距离也就是b到e的父节点和e到b的父节点的距离+1，即dis[b][e]=min(dis[b][parent[e]],dis[parent[b]][e])+1。好吧，被你发现了，其实这就是动态规划的思想啦。初始条件是什么？当然是自己到自己的距离为0，到其它点的距离是一个比较大的数咯！废话不多说，直接上代码：
//情况一的代码：
#include<stdio.h>
#include<string.h>
struct NODE
{
int data;
NODE *Left;
NODE *Right;
};
const int N = 20;
const int Inf = 1e5;
NODE node[N];
int parent[N];//节点的父节点
int dis[N][N];//已访问过的节点到未访问过的节点的距离
inline int min(const int a, const int b)
{
return a < b ? a : b;
}
void FindDis(int root)//得到任意两点的距离矩阵
{
NODE *Queue[N];
int head,tail;
NODE *p;
memset(parent, -1, sizeof(parent));
memset(dis, 1, sizeof(dis));
head = tail = 0;
int i;
for(i = 0; i < N; ++i)
dis[i][i] = 0;
Queue[head] = &node[root];
parent[root] = root;
while(head <= tail)
{
p = Queue[head];
if(p->Left != NULL)
{
Queue[++tail] = p->Left;
parent[p->Left->data] = p->data;
dis[p->Left->data][p->data] = dis[p->data][p->Left->data] = 1;
}
if(p->Right != NULL)
{
Queue[++tail] = p->Right;
parent[p->Right->data] = p->data;
dis[p->Right->data][p->data] = dis[p->data][p->Right->data] = 1;
}
//更新访问过的节点与新加入的节点的距离
for(i = 0; i < N; ++i)
{
//该节点访问过 节点的父节点不是p 节点自己不是p
if(parent[i] > -1 && parent[i] != p->data && i != p->data)
{
if(i == root)
dis[i][p->data] = dis[i][parent[p->data]] + 1;
else if(p->data == root)
dis[i][p->data] = dis[parent[i]][p->data] + 1;
else
dis[i][p->data] = min(dis[parent[i]][p->data], dis[i][parent[p->data]]) + 1;
dis[p->data][i] = dis[i][p->data];
}
}
++head;
}
}
4、OK，现在拿出我的杀手锏...................如果只是单次的求两个节点的距离怎么办呢？怎么样使最快的！！！嘿嘿，代码写出来之后再说啦！！
好，这个问题中根节点到目标节点的路径可以抽象成一个链表。怎么抽象？其实就是树的前序遍历，想想，好像是这样的耶！OK，那问题就转化成两个链表之间求最后一个公共节点的问题了。我觉得我有必要写一个链表求公共节点的专题。好吧。额......这个等有空了再说吧。不过写好之后，会再链接发过来的。
//情况二的代码#include<stdio.h>
bool used[N];//标记节点是否被访问过
//其他的变量定义跟前面一样，这里加了一个used数组
//用前序遍历来抽取根节点到目标节点的路径
int FindRoad(NODE **stack, int root, int n)
{
int top = -1;
NODE *p = &node[root];
memset(used, 0, sizeof(used));
while(top > -1 || p != NULL)
{
while(p != NULL)
{
stack[++top] = p;
if(p->data == n)
return top;
p = p->Left;
}
while(top > -1 && used[stack[top]->data])
--top;
if(top > -1)
{
p = stack[top]->Right;
used[stack[top]->data] = true;
}
}
return -1;//未找到
}
//计算两个节点之间的距离
int FindDis(int root, int b, int e)
{
NODE *stack1[N];
NODE *stack2[N];
int top1,top2;
int i,j;
//找到根节点到b的路径，保存在stack1中
top1 = FindRoad(stack1, root, b);
top2 = FindRoad(stack2, root, e);
if(top1 < 0 || top2 < 0)//如果不在树中，返回不可达
return Inf;
for(i = 0, j = 0; i <= top1 && j <= top2; ++i, ++j)
{
if(stack1[i] != stack2[j])
break;
}
int nLen = 0;
if(i <= top1)
nLen += top1 - i + 1;
if(j <= top2)
nLen += top2 - j + 1;
return nLen;
}
5、如果不是求树中的距离，而是需要找到数组符合条件的路径呢？参考另一篇博客：http://blog.csdn.net/kay_zhyu/article/details/8870048OK,为了方便，下面给出两种情况下的main函数的调用，如果不需要可以直接pass掉这一部分。
//情况1的main函数
int main()
{
int n,i,m;
int root,num,r;//r为1表示左节点，0表示右节点
int nLen;
while(scanf("%d %d", &n, &m) != EOF)
{
memset(node, 0, sizeof(node));
nLen = 0;
for(i = 0; i < n; ++i)
{
scanf("%d %d %d", &r, &root, &num);
Add(root, num, r);
}
FindDis(0);//数据输入保证以0作为根节点
for(i = 0; i < m; ++i)
{
printf("Enter the b and e:");
scanf("%d %d", &num, &r);
//其实需要判断一下节点在不在树中，其实也很简单，直接判断parent是不是大于0
printf("节点%d与节点%d的距离为%d\n", num, r, dis[num][r]);
}
}
}
//情况二的main函数
int main()
{
int n,i,m;
int root,num,r;//r为1表示左节点，0表示右节点
int nLen;
while(scanf("%d %d", &n, &m) != EOF)
{
memset(node, 0, sizeof(node));
nLen = 0;
for(i = 0; i < n; ++i)
{
scanf("%d %d %d", &r, &root, &num);
Add(root, num, r);
}
for(i = 0; i < m; ++i)
{
printf("Enter the b and e:");
scanf("%d %d", &num, &r);
nLen = FindDis(0, num, r);//数据输入保证以0作为根节点
printf("节点%d与节点%d的距离为%d\n", num, r, nLen);
}
}
}