问题：按层序从root节点开始给一个完全二叉树标号，对任意两个节点，求其最短路径。
描述：二叉树的最短路径问题可以转化为求两个节点最小公共父节点问题，而两节点到最小公共父节点的路径即为所求。
代码如下：
#include<iostream>
using namespace std;
int main()
{
int A,B; //两个节点
cout<<"Please Enter:"<<endl;
cin>>A>>B; //输入两个节点
if(A > B)
{
A = A^B;
B = B^A;
A = A^B;
} //确保A<B
int FA,FB; //定义父节点
FA = A/2;
FB = B/2;
while(FA != FB) //求A,B的最小父节点
{
if(FA <FB)FB = FB/2;
else
FA = FA/2;
}
while(A >= FA) //输出A到父节点路径
{
cout<<A<<" ";
A = A/2;
}
int S[100];
int i = 0;
while(B >= FA) //存入父节点到B路径
{
S[i] = B;
B = B/2;
i++;
}
for(i = i-1;i--;i>=0)cout<<S[i]<<" "; //输出父节点到B路径
return 0;
}
| 
转播
