严蔚敏《数据结构(c语言)习题集》答案第六章树和二叉树文库.docVIP

第六章 树和二叉树 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!=vp;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(B1B2Bitree_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;