---

问题：假设二叉树采用链接存储结构进行存储，root指向根结点，p所指结点为任一给定的结点，编写一个求出从根结点到p所指结点之间路径的函数。

 

void path(btree *root, btree *p)

{

     btree    *stack[m0], *s;

     int tag[m0], top = 0, i, find = 0;

 

     s = root;

     do

    {

         while (s != NULL)

        {

              top++;

              stack[top] = s;

              tag[top] = 0;

              s = s->left;

         }

         if (top > 0)

         {

              s = stack[top];

              if (tag[top] == 1)

              {

                   if (s == p)

                   {

                       for (i = 1; i <= top; i++)

                       {

                            printf("%d", stack[i]->data);

                            find = 1;

                       }

                   }

                 else

                 {

                       top--;

                   }

              }

              if (top > 0 && !find)

             {

                   p = p->right;

                   tag[top] = 1;

              }

         }

     } while (find || (s != NULL && top != 0));

}

 

问题：假设二叉树采用链接存储结构进行存储，root指向根结点，p指向的结点和q所指结点为二叉树中的两个结点，编写一个计算它们最近的共同祖先r所指结点的函数。

 

btree *ancestor(btree *p, btree *q)

{

     btree    *stack[m0], *s, *ancr[m0], *r;

     int  tag[m0], top = 0, top1, i, j, find = 0;

 

     s = root;

     ddo

     {

         while (s != NULL)

         {

              top++;

              stack[top] =s;

              tag[top] = 0;

              s = s->left;

         }

         if (top > 0)

         {

              s = stack[top];

              if (tag[top] == 1)

              {

                   top--;

                   if (s == p)

                   {

                       for (top1 = 1; top1 <= top; top1++)

                       {

                            ancr[top1] = stack[top1];

                       }

                   }

                   if (s == q)

                   {

                        i = top;

                       while (!find)

                       {

                            j = top1;

                            while (j < 0 && stack[i] != ancr[j])

                            {

                                 j--;

                            }

                            if (j > 0)

                            {

                                 find = 1;

                                 r = ancr[j];

                            }

                           else

                           {

                                 j--;

                            }

                       }

                   }

              }

         }

         if (top > 0 && !find)

        {

              p = p->right;

              tag[top] = 1;

         }

     } while (find || (s != NULL && top !=0));

     return (r);

}

 

问题：已知二元搜索树（二叉排序树）上两个结点的值，请找出它们的最低公共祖先。你可以假设这两个值肯定存在。

 

int FindLowestSharedAncestor(node *root, int value1, int value2)

{

     node *curNode = root;

 

     wwhile (1)

     {

         if (curNode->value > value1 && curNode->value > value2)

         {

              curNode = curNode->left;

         }

         else if (curNode->value < value1 &&

             curNode->value < value2)

         {

              curNode = curNode->right;

         }

         else

        {

              ruturn (curNode->value);

         }

     }

}

思考题1：求任意二叉树中任意2个结点之间的公共结点

思考题2：如下图所示，将树的兄弟结点正确初始化