第六章 树和二叉树 题解

核心提示：第六章 树和二叉树 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;

　　　　　　　　　　　　　　　　　　　　第六章 树和二叉树
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;
　　　　　　　　　　 EBTNode *parent;
　　　　　　　　　　 enum {0,1,2} mark;
　　　　　　　　  } EBTNode,EBitree; /*有mark域和双亲指针域的二叉树结点类型 */
void PostOrder_Nonrecursive(EBitree T)/*后序遍历二叉树的非递归算法,不用栈*/
{
  p=T;
  while(p)
　  switch(p->mark)
　  {
　　  case 0:
　　　  p->mark=1;
　　　  if(p->lchild) p=p->lchild; /*访问左子树*/
　　　  break;
　　  case 1:
　　　  p->mark=2;
　　　  if(p->rchild) p=p->rchild; /*访问右子树*/
　　　  break;
　　  case 2:
　　　  visit(p);
　　　  p->mark=0; /*恢复mark值*/
　　　  p=p->parent; /*返回双亲结点*/
　  }
}/*PostOrder_Nonrecursive*/
分析:本题思路与上一题完全相同,只不过结点的mark值是储存在结点中的,而不是暂存在堆栈中,所以访问完毕后要将mark域恢复为0,以备下一次遍历.
6.40
typedef struct {
　　　　　　　　　　 int data;
　　　　　　　　　　 PBTNode *lchild;
　　　　　　　　　　 PBTNode *rchild;
　　　　　　　　　　 PBTNode *parent;
　　　　　　　　　 } PBTNode,PBitree; /*有双亲指针域的二叉树结点类型 */
void Inorder_Nonrecursive(PBitree T)/*不设栈非递归遍历有双亲指针的二叉树*/
{
  p=T;
  while(p->lchild) p=p->lchild; /*向左走到尽头*/
  while(p)
  {
　  visit(p);
　  if(p->rchild) /*寻找中序后继:当有右子树时*/
　  {
　　  p=p->rchild;
　　  while(p->lchild) p=p->lchild; /*后继就是在右子树中向左走到尽头*/
　  }
　  else if(p->parent->lchild==p) p=p->parent; /*当自己是双亲的左孩子时后继就是双亲*/
　  else
　  {
　　  p=p->parent;
　　  while(p->parent&&p->parent->rchild==p) p=p->parent;
　　  p=p->parent;
　  } /*当自己是双亲的右孩子时后继就是向上返回直到碰到自己是在其左子树中的祖先*/
  }/*while*/
}/*Inorder_Nonrecursive */
6.41
int c,k; /*这里把k和计数器c作为全局变量处理 */
void Get_PreSeq(Bitree T)/*求先序序列为k的结点的值*/
{
  if(T)
  {
　  c++; /*每访问一个子树的根都会使前序序号计数器加1*/
　  if(c==k)
　  {
　　  printf("Value is %d\n",T->data);
　　  exit (1);
　  }
　  else
　  {
　　  Get_PreSeq(T->lchild); /*在左子树中查找*/
　　  Get_PreSeq(T->rchild); /*在右子树中