《严蔚敏数据结构题集c语言版答案第六章》由会员分享，可在线阅读，更多相关《严蔚敏数据结构题集c语言版答案第六章（21页珍藏版）》请在金锄头文库上搜索。
1、第六章 树和二叉树 6.33 int Is_Descendant_C(int u,int v)/在孩子存储结构上判断 u 是否 v 的子孙,是则返 回 1,否则返回 0 if(u=v) return 1;elseif(Lv)if (Is_Descendant(u,Lv) return 1;if(Rv)if (Is_Descendant(u,Rv) return 1; /这是个递归算法return 0; /Is_Descendant_C 6.34 int Is_Descendant_P(int u,int v)/在双亲存储结构上判断 u 是否 v 的子孙,是则返回 1,否则返回 0 for(p=
2、u;p!=vp=Tp);if(p=v) return 1;else return 0; /Is_Descendant_P 6.35 这一题根本不需要写什么算法,见书后注释:两个整数的值是相等的. 6.36 int Bitree_Sim(Bitree B1,Bitree B2)/判断两棵树是否相似的递归算法 if(!B1else if(B1else return 0; /Bitree_Sim 6.37 void PreOrder_Nonrecursive(Bitree T)/先序遍历二叉树的非递归算法 InitStack(S);Push(S,T); /根指针进栈while(!StackEmpty
3、(S)while(Gettop(S,p)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
4、(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 分析:为了区分两次过栈的不同处
5、理方式,在堆栈中增加一个 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;w
6、hile(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
7、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
8、-parent-lchild=p) p=p-parent; /当自己是双亲的左孩子时后继就是 双亲elsep=p-parent;while(p-parentp=p-parent; /当自己是双亲的右孩子时后继就是向上返回直到遇到自己是在其左子树中 的祖先/while /Inorder_Nonrecursive 6.41 int c,k; /这里把 k 和计数器 c 作为全局变量处理 void Get_PreSeq(Bitree T)/求先序序列为 k 的结点的值 if(T)c+; /每访问一个子树的根都会使前序序号计数器加 1if(c=k)printf(“Value is %dn“,T-dat
9、a);exit (1);elseGet_PreSeq(T-lchild); /在左子树中查找Get_PreSeq(T-rchild); /在右子树中查找/if /Get_PreSeq main() .scanf(“%d“,c=0; /在主函数中调用前,要给计数器赋初值 0Get_PreSeq(T,k);. /main 6.42 int LeafCount_BiTree(Bitree T)/求二叉树中叶子结点的数目 if(!T) return 0; /空树没有叶子else if(!T-lchild /叶子结点else return Leaf_Count(T-lchild)+Leaf_Count(
10、T-rchild);/左子树的叶子数加上 右子树的叶子数 /LeafCount_BiTree 6.43 void Bitree_Revolute(Bitree T)/交换所有结点的左右子树 T-lchildT-rchild; /交换左右子树if(T-lchild) Bitree_Revolute(T-lchild);if(T-rchild) Bitree_Revolute(T-rchild); /左右子树再分别交换各自的左右子树 /Bitree_Revolute 6.44 int Get_Sub_Depth(Bitree T,int x)/求二叉树中以值为 x 的结点为根的子树深度 if(T-
11、data=x)printf(“%dn“,Get_Depth(T); /找到了值为 x 的结点,求其深度exit 1;elseif(T-lchild) Get_Sub_Depth(T-lchild,x);if(T-rchild) Get_Sub_Depth(T-rchild,x); /在左右子树中继续寻找 /Get_Sub_Depth int Get_Depth(Bitree T)/求子树深度的递归算法 if(!T) return 0;elsem=Get_Depth(T-lchild);n=Get_Depth(T-rchild);return (mn?m:n)+1; /Get_Depth 6.4
12、5 void Del_Sub_x(Bitree T,int x)/删除所有以元素 x 为根的子树 if(T-data=x) Del_Sub(T); /删除该子树elseif(T-lchild) Del_Sub_x(T-lchild,x);if(T-rchild) Del_Sub_x(T-rchild,x); /在左右子树中继续查找/else /Del_Sub_x void Del_Sub(Bitree T)/删除子树 T if(T-lchild) Del_Sub(T-lchild);if(T-rchild) Del_Sub(T-rchild);free(T); /Del_Sub 6.46 vo
13、id Bitree_Copy_Nonrecursive(Bitree T,Bitree 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)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-rc
14、hild=(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.47 void LayerOrder(Bitree T)/层序遍历二叉树 InitQueue(Q); /建立工作队列EnQueue(Q,T);while(!QueueEmpty(Q)DeQueue(Q,p);visit(p);if(p-lchild) EnQueue(Q,p-lchild);i
15、f(p-rchild) EnQueue(Q,p-rchild); /LayerOrder 6.48 int found=FALSE; Bitree* Find_Near_Ancient(Bitree T,Bitree p,Bitree q)/求二叉树 T 中结点 p 和 q 的最近共同祖先Bitree pathp 100 ,pathq 100 /设立两个辅助数组暂存从根到 p,q 的路径Findpath(T,p,pathp,0);found=FALSE;Findpath(T,q,pathq,0); /求从根到 p,q 的路径放在 pathp 和 pathq 中for(i=0;pathpi=pathqii+); /查找两条路径上最后一个相同结点return pathp-i; /Find_Near_Ancient void Findpath(Bitree T,Bitree p,Bitree path ,int i)/求从 T 到 p 路径的递归算法 if(T=p)found=TRUE;return; /找到pathi=T; /当前结点存入路径if(T-lchild) F
