代码如下：
void Anales(int arr[],int p, int q)
{
int pos = -1;
int size = 0;
int as[1] = { 0 };
int indexP = 0;
int indexQ = 0;
while (arr[size] != as[1])
{
if (arr[size] == p)
{
indexP = size;
}
if (arr[size] == q)
{
indexQ = size;
}
size++;
}
if (indexP > indexQ)
{
int subInt = indexP - indexQ; //如索引的间隔正好等于更小的那个索引，那么它们的公//共祖先索引为0
if (subInt == indexQ)
{
pos = 0;
}
else
{
int fatherP = indexP;
while (fatherP > indexQ)
{
if (fatherP % 2) //如果当前索引为偶数，它的上一级 = (当前索引 - 2)/2
{
fatherP = (fatherP - 2) / 2;
}
else //如果当前索引为奇数，它的上一级 = (当前索引 - 1)/2
{
fatherP = (fatherP - 1) / 2;
}
}
if (fatherP == indexQ)
{
pos = fatherP;
}
else
{
//同时寻找上级直到相等
while (fatherP != indexQ)
{
if (fatherP % 2)
{
fatherP = (fatherP - 2) / 2;
}
else
{
fatherP = (fatherP - 1) / 2;
}
if (indexQ % 2)
{
indexQ = (indexQ - 2) / 2;
}
else
{
indexQ = (indexQ - 1) / 2;
}
}
pos = indexQ;
}
}
}
else if (indexQ > indexP)
{
int subInt = indexQ - indexP;
if (subInt == indexP)
{
pos = 0;
}
else
{
while (indexQ > indexP)
{
if (indexQ % 2)
{
indexQ = (indexQ - 2) / 2;
}
else
{
indexQ = (indexQ - 1) / 2;
}
}
if (indexP == indexQ)
{
pos = indexQ;
}
else
{
while (indexP != indexQ)
{
if (indexP % 2)
{
indexP = (indexP - 2) / 2;
}
else
{
indexP = (indexP - 1) / 2;
}
if (indexQ % 2)
{
indexQ = (indexQ - 2) / 2;
}
else
{
indexQ = (indexQ - 1) / 2;
}
}
pos = indexQ;
}
}
}
else
{
pos = indexP;
}
std::cout << "公共祖先:" << arr[pos] << "t 索引:" << pos << std::endl;
}
int main()
{
int arr[15] = { 3,5,1,6,2,0,8,0,0,7,4,0,0,0,0 };
Anales(arr,5,4);
}
