严蔚敏 数据结构 第六章答案.doc

int Is_Descendant_C(int u,int v)//在孩子存储结构上判断u是否v的子孙,是则返回1,否则返回0
{
  if(u==v) return 1;
  else
  {
    if(L[v])
      if (Is_Descendant(u,L[v])) return 1;
    if(R[v])
      if (Is_Descendant(u,R[v])) return 1; //这是个递归算法
  }
  return 0;
}//Is_Descendant_C

int Is_Descendant_P(int u,int v)//在双亲存储结构上判断u是否v的子孙,是则返回1,否则返回0
{
  for(p=u;p!=v&&p;p=T[p]);
  if(p==v) return 1;
  else return 0;
}//Is_Descendant_P

这一题根本不需要写什么算法,见书后注释:两个整数的值是相等的.

int Bitree_Sim(Bitree B1,Bitree B2)//判断两棵树是否相似的递归算法
{
  if(!B1&&!B2) return 1;
  else if(B1&&B2&&Bitree_Sim(B1->lchild,B2->lchild)&&Bitree_Sim(B1->rchild,B2->rchild))
    return 1;
  else return 0;
}//Bitree_Sim

void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法
{
  InitStack(S);
  Push(S,T); //根指针进栈
  while(!StackEmpty(S))
  {
    while(Gettop(S,p)&&p)
    {
      visit(p->data);
      push(S,p->lchild);
    } //
向左走到尽头
    pop(S,p);
    if(!StackEmpty(S))
    {
     pop(S,p);
     push(S,p->rchild); //向右一步
    }
  }//while
}//PreOrder_Nonrecursive

typedef struct {
                  BTNode* ptr;
                  enum {0,1,2} mark;
                } PMType; //有mark域的结点指针类型
void PostOrder_Stack(BiTree T)//后续遍历二叉树的非递归算法,用栈
{
  PMType a;
  InitStack(S); //S的元素为PMType类型
  Push (S,{T,0}); //根结点入栈
  while(!StackEmpty(S))
  {
    Pop(S,a);
    switch()
    {
      case 0:
        Push(S,{,1}); //修改mark域
        if(->lchild) Push(S,{->lchild,0}); //访问左子树
        break;
      case 1:
        Push(S,{,2}); //修改mark域
        if(->rchild) Push(S,{->rchild,0}); //访问右子树
        break;
      case 2:
        visit(); //访问结点,返回
    }
  }//while
}//PostOrder_Stack
分析:为了区分两次过栈的不同处理方式,在堆栈中增加一个mark域,mark=0表示刚刚访问此结点,mark=1表示左子树处理结束返回,mark=.

typedef struct {
                  int data;
                  EBTNode *lchild;
                  EBTNode *rchild;