数据结构课后习题解答第六章树和二叉树

习题及参考答案第六章树和二叉树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_Descendant_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-lchild,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);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});//根结点入栈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);//访问结点,返回}}//while}//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域和双亲指针域的二叉树结点类型voidPostOrder_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_Nonrecursive分析:本题思路与上一题完全相同,只不过结点的mark值是储存在结点中的,而不是暂存在堆栈中,所以访问完毕后要将mark域恢复为0,以备下一次遍历.6.40typedefstruct{intdata;PBTNode*lchild;PBTNode*rchild;PBTNode*parent;}PBTNode,PBitree;//有双亲指针域的二叉树结点类型voidInorder_Nonrecursive(PBitreeT)//不设栈非递归遍历有双亲指针的二叉树{p=T;while(p-lchild)p=p-lchild;//向左走到尽头while(p){visit(p);if(p-rchild)//寻找中序后继:当有右子树时{p=p-rchild;while(p-lchild)p=p-lchild;//后继就是在右子树中向左走到尽头}elseif(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_Nonrecursive6.41intc,k;//这里把k和计数器c作为全局变量处理voidGet_PreSeq(BitreeT)//求先序序列为k的结点的值{if(T){c++;//每访问一个子树的根都会使前序序号计数器加1if(c==k){printf(Valueis%d\n,T-data);exit(1);}else{Get_PreSeq(T-lchild);//在左子树中查找Get_PreSeq(T-rchild);//在右子树中查找}}//if}//Get_PreSeqmain(){...scanf(%d,&k);c=0;//在主函数中调用前,要给计数器赋初值0Get_PreSeq(T,k);...}//main6.42intLeafCount_BiTree(BitreeT)//求二叉树中叶子结点的数目{if(!T)return0;//空树没有叶子elseif(!T-lchild&&!T-rchild)return1;//叶子结点elsereturnLeaf_Count(T-lchild)+Leaf_Count(T-rchild);//左子树的叶子数加上右子树的叶子数}//LeafCount_BiTree6.43voidBitree_Revolute(BitreeT)//交换所有结点的左右子树{T-lchild-T-rchild;//交换左右子树if(T-lchild)Bitree_Revolute(T-lchild);if(T-rchild)Bitree_Revolute(T-rchild);//左右子树再分别交换各自的左右子树}//Bitree_Revolute6.44intGet_Sub_Depth(BitreeT,intx)//求二叉树中以值为x的结点为根的子树深度{if(T-data==x){printf(%d\n,Get_Depth(T));//找到了值为x的结点,求其深度exit1;}else{if(T-lchild)Get_Sub_Depth(T-lchild,x);if(T-rchild)Get_Sub_Depth(T-rchild,x);//在左右子树中继续寻找}}//Get_Sub_DepthintGet_Depth(BitreeT)//求子树深度的递归算法{if(!T)return0;else{m=Get_Depth(T-lchild);n=Get_Depth(T-rchild);return(mn?m:n)+1;}}//Get_Depth6.45voidDel_Sub_x(BitreeT,intx)//删除所有以元素x为根的子树{if(T-data==x)Del_Sub(T);//删除该子树else{if(T-lchild)Del_Sub_x(T-lchild,x);if(T-rchild)Del_Sub_x(T-rchild,x);//在左右子树中继续查找}//else}//Del_Sub_xvoidDel_Sub(BitreeT)//删除子树T{if(T-lchild)Del_Sub(T-lchild);if(T-rchild)Del_Sub(T-rchild);free(T);}//Del_Sub6.46voidBitree_Copy_Nonrecursive(BitreeT,Bitree&U)//非递归复制二叉树{InitStack(S1);InitStack(S2);push(S1,T);//根指针进栈U=(BTNode*)malloc(sizeof(BTNode));U-data=T-data;q=U;push(S2,U);while(!StackEmpty(S)){while(Gettop(S1,p)&&p){q-lchild=(BTNode*)malloc(sizeof(BTNode));q=q-lchild;q-data=p-data;push(S1,p-lchild);push(S2,q);}//向左走到尽头pop(S1,p);pop(S2,q);if(!StackEmpty(S1)){pop(S1,p);pop(S2,q);q-rchild=(BTNode*)malloc(sizeof(BTNode));q=q-rchild;q-data=p-data;push(S1,p-rchild);//向右一步push(S2,q);}}//while}//BiTree_Copy_Nonrecursive分析:本题的算法系从6.37改写而来.6.47voidLayerOrder(BitreeT)//层序遍历二叉树{InitQueue(Q);//建立工作队列EnQueue(Q,T);while(!QueueEmpty(Q)){DeQueue(Q,p);visit(p);if(p-lchild)EnQueue(Q,p-lchild);if(p-rchild)EnQueue(Q,p-rchild);}}//LayerOrder6.48intfound=FALSE;Bitree*Find_Near_Ancient(BitreeT,Bitreep,Bitreeq)//求二叉树T中结点p和q的最近共同祖先{Bitreepathp[100],pathq[100]//设立两个辅助数组暂存从根到p,q的路径Findpath(T,p,pathp,0);found=FALSE;Findpath(T,q,pathq,0);//求从根到p,q的路径放在pathp和pathq中for(i=0;pathp[i]==pathq[i]&&pathp[i];i++);//查找两条路径上最后一个相同结点returnpathp[--i];}//Find_Near_AncientvoidFindpath(BitreeT,Bitreep,Bitreepath[],inti)//求从T到p路径的递归算法{if(T==p){found=TRUE;return;//找到}path[i]=T;//当前结点存入路径if(T-lchild)Findpath(T-lchild,p,path,i+1);//在左子树中继续寻找if(T-rchild&&!found)Findp