* *
第六章 树和二叉树 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;
严蔚敏《数据结构(c语言知识学习版)作业资料》答案解析第六章树和二叉树文库
