2005-d-三

/**
  1、顺序存储，假设根的存储下标是1 将当前结点的下标连续整除以2，直到1为止，
     中间所有得到的商的下标都是其祖先，并且是从其双亲直到根为止。
  2、链式存储
     （1）使用非递归的后序遍历，当遍历到该结点时，辅助栈中从栈顶到栈底依次为该结点从双亲开始到根为止的所有祖先。
     （2）递归实现。
**/

//顺序存储，采用下标关系找出祖先结点
void ancestor(int bt[],int i,int x)
{
    if(bt[i]==x)//满足条件，输出祖先
    {
        while(i!=1)
        {
            printf("%d",i/2);
            i/=2;
        }
    }
    else
    {
        ancestor(bt,2*i,x);
        ancestor(bt,2*i+1,x);
    }
}

//后序非递归遍历,输出值为x的所有祖先

void afterOrder(BiTree *root,int x)
{
   struct Tree
   {
       BiTree *bt;
       int tag;//1-第一次访问(左孩子)、2-非第一次访问（右孩子）
   };
   
   Tree stack[maxSize],top=0;//定义一个栈
   Tree p; p.bt=root; p.tag=1;//根结点入栈
   
   while(p!=NULL || top>0)//此处当p==NULL时，继续出栈
   {
       while(p.bt!=NULL)
       {
           ++top;
           stack[top].bt=p;
           stack[top].tag=1;
           p.bt=p.bt->lchild;//指向左孩子
       }
       
       //添加代码功能START
       if(bt->data==x)//找到x
        {
            printf("所查结点的所有祖先结点的值为：\n");
            for(i=1;i<=top;i++)
                printf("%d",stack[i].bt->data);//输出结点值
            exit(1);
        }//END
        
       if(top>0)//栈不空，此时p==NULL
       {
           p=stack[top--];//出栈
           if(p.tag==1)//只访问过一次
           {
               p.tag=2;//标记第二次访问
               stack[++top]=p;
               
               p.bt=p.bt->rchild;
           }
       }
   }
}

//采用递归实现
int printAncestors(BTNode *root, int target)
{
  if (root == NULL)
     return 0;

  if (root->data == target)
     return 1;
  //子树可以找到，当前节点肯定为祖先节点
  if ( printAncestors(root->left, target) ||
       printAncestors(root->right, target) )
  {
    printf("%d ",root->data);
    return 1;
  }
  return 0;
}