资源描述：
《严蔚敏《数据结构(c语言版)习题集》答案第六章 树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、严蔚敏《数据结构(c语言版)习题集》答案第六章树和二叉树第六章树和二叉树6.33intIs_Descendant_C(intu,intv)//在孩子存储结构上判断u是否v的子孙,是则返回1,否则返回0{if(u==v)return1;else{if(L[v])if(Is_Descendant(u,L[v]))return1;if(R[v])if(Is_Descendant(u,R[v]))return1;//这是个递归算法}return0;}//Is_Descendant_C6.34intIs_Descendan
2、t_P(intu,intv)//在双亲存储结构上判断u是否v的子孙,是则返回1,否则返回0{for(p=u;p!=v&&p;p=T[p]);if(p==v)return1;elsereturn0;}//Is_Descendant_P6.35这一题根本不需要写什么算法,见书后注释:两个整数的值是相等的.6.36intBitree_Sim(BitreeB1,BitreeB2)//判断两棵树是否相似的递归算法{if(!B1&&!B2)return1;elseif(B1&&B2&&Bitree_Sim(B1->lchil
3、d,B2->lchild)&&Bitree_Sim(B1->rchild,B2->rchild))return1;elsereturn0;}//Bitree_Sim6.37voidPreOrder_Nonrecursive(BitreeT)//先序遍历二叉树的非递归算法{InitStack(S);Push(S,T);//根指针进栈while(!StackEmpty(S)){while(Gettop(S,p)&&p){visit(p->data);push(S,p->lchild);}//向左走到尽头pop(S,p
4、);if(!StackEmpty(S)){pop(S,p);push(S,p->rchild);//向右一步}}//while}//PreOrder_Nonrecursive6.38typedefstruct{BTNode*ptr;enum{0,1,2}mark;}PMType;//有mark域的结点指针类型voidPostOrder_Stack(BiTreeT)//后续遍历二叉树的非递归算法,用栈{PMTypea;InitStack(S);//S的元素为PMType类型Push(S,{T,0});//根结点入栈
5、while(!StackEmpty(S)){Pop(S,a);switch(a.mark){case0:Push(S,{a.ptr,1});//修改mark域if(a.ptr->lchild)Push(S,{a.ptr->lchild,0});//访问左子树break;case1:Push(S,{a.ptr,2});//修改mark域if(a.ptr->rchild)Push(S,{a.ptr->rchild,0});//访问右子树break;case2:visit(a.ptr);//访问结点,返回}}//whi
6、le}//PostOrder_Stack分析:为了区分两次过栈的不同处理方式,在堆栈中增加一个mark域,mark=0表示刚刚访问此结点,mark=1表示左子树处理结束返回,mark=2表示右子树处理结束返回.每次根据栈顶元素的mark域值决定做何种动作.6.39typedefstruct{intdata;EBTNode*lchild;EBTNode*rchild;EBTNode*parent;enum{0,1,2}mark;}EBTNode,EBitree;//有mark域和双亲指针域的二叉树结点类型voidP
7、ostOrder_Nonrecursive(EBitreeT)//后序遍历二叉树的非递归算法,不用栈{p=T;while(p)switch(p->mark){case0:p->mark=1;if(p->lchild)p=p->lchild;//访问左子树break;case1:p->mark=2;if(p->rchild)p=p->rchild;//访问右子树break;case2:visit(p);p->mark=0;//恢复mark值p=p->parent;//返回双亲结点}}//PostOrder_Nonr
8、ecursive分析:本题思路与上一题完全相同,只不过结点的mark值是储存在结点中的,而不是暂存在堆栈中,所以访问完毕后要将mark域恢复为0,以备下一次遍历.6.40typedefstruct{intdata;PBTNode*lchild;PBTNode*rchild;PBTNode*parent;}PBTNode,PBitree;//有双亲指针域的二叉树结点类型vo
