寻找二叉树中任意两个数的公共祖先

代码如下：

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);

}