淘豆网
下载此文档放大查看缩小查看   1/20
0/100
您的浏览器不支持进度条
更多>>该用户其他文档
下载所得到的文件列表
严蔚敏 数据结构 第六章答案.doc
文档介绍:
6.33
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
6.34
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
6.35
这一题根本不需要写什么算法,见书后注释:两个整数的值是相等的.
6.36
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
6.37
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
6.38
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(a.mark)
    {
      case 0:
        Push(S,{a.ptr,1}); //修改mark域
        if(a.ptr->lchild) Push(S,{a.ptr->lchild,0}); //访问左子树
        break;
      case 1:
        Push(S,{a.ptr,2}); //修改mark域
        if(a.ptr->rchild) Push(S,{a.ptr->rchild,0}); //访问右子树
        break;
      case 2:
        visit(a.ptr); //访问结点,返回
    }
  }//while
}//PostOrder_Stack
分析:为了区分两次过栈的不同处理方式,在堆栈中增加一个mark域,mark=0表示刚刚访问此结点,mark=1表示左子树处理结束返回,mark=2表示右子树处理结束返回.每次根据栈顶元素的mark域值决定做何种动作.
6.39
typedef struct {
                  int data;
                  EBTNode *lchild;
                  EBTNode *rchild; 内容来自淘豆网www.taodocs.com转载请标明出处.
更多>>相关文档
文档信息
最近更新
文档标签