数据结构课后答案个人

数据结构作业（6—9章）理学院信计1001孙建伟201006646.4一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序从1开始对全部结点编号，问：(1)各层的结点数目是多少？(2)编号为p的结点的父结点（若存在）的编号是多少？(3)编号为p的结点的第i个儿子结点（若存在）的编号是多少？(4)编号为p的结点有右兄弟的条件是什么？其右兄弟的编号是多少？解：(1)11kkH(2)如果p是其双亲的最小的孩子（右孩子），则p减去根结点的一个结点，应是k的整数倍，该整数即为所在的组数，每一组为一棵满k叉树，正好应为双亲结点的编号。如果p是其双亲的最大的孩子（左孩子），则p+k-1为其最小的弟弟，再减去一个根结点，除以k，即为其双亲结点的编号。综合来说，对于p是左孩子的情况，i=(p+k-2)/k；对于p是右孩子的情况，i=(p-1)/k如果左孩子的编号为p，则其右孩子编号必为p+k-1，所以，其双亲结点的编号为kkpi2向下取整，如1.5向下取整为1(3)结点p的右孩子的编号为kp+1，左孩子的编号为kp+1-k+1=k(p-1)+2，第i个孩子的编号为k(p-1)+2+i-1=kp-k+i+1。(4)当(p-1)%k!=0时，结点p有右兄弟，其右兄弟的编号为p+1。6.6已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点。试求该树含有的叶子节点数目。解：利用上题结论易得结果。设度为k的结点个数为kn，则总结点数为knnk1。叶子结点的数目应等于总结点数减去度不为0的结点的数目，即knnnnnk106.8证明：一棵满k叉树上的叶子结点数0n和非叶子结点数1n之间满足以下关系：1110nkn解：一棵满k叉树的最后一层(深度为h)的结点数(叶子结点数)为10hkn，其总结点数为11kkh，则非叶子结点数00011111nkknnkknh，从而得1)1(10nkn6.13假设n和m为二叉树中两结点，用1、0或#（分别表示肯定、恰恰相反或不一定）填写下表：问已知前序遍历时n在m前？中序遍历时n在m前？后序遍历时n在m前？n在m左方n在m右左方n是m祖先n是m子孙注：如果(1)离a和b最近的共同祖先p存在，且(2)a在p的左子树中，b在p的右子树中，则称a在b的左方（即b在a的右方）。6.26解：不妨设这8个结点为A、B、C、D、E、F、G、H，其相应的权为7、19、2、6、32、3、21、10。A:1101B:01C:11111D:1110E:10F:11110G:00H:1100采用这种方式编码，电文最短。6.33解：intVisit(intu,intv){if(u==v)return1;if(L[v]==0){//左子树不存在if(R[v]==0)//右子树也不存在return0;else{//右子树存在，继续访问右子树if(Visit(u,R[v]))return1;elsereturn0;}}else{//左子树存在if(Visit(u,L[v]))//左子树中存在目标return1;else{//左子树中没有目标，需访问右子树if(R[v]==0)//没有右子树return0;else{//右子树存在，继续访问右子树if(Visit(u,R[v]))return1;elsereturn0;}}}}6.37解：//先序遍历的非递归算法StatusPOTraverse(BiTree&T,Status(*Visit)(TElemTypee)){BiTreep;Stacks;InitStack(s);p=T;while(p||!StackEmpty(s)){if(p){//如果根指针不空，访问根结点，//右指针域压栈，继续遍历左子树if(!Visit(p-data))returnERROR;Push(s,p-rchild);p=p-lchild;}//根指针已空，本子树已遍历完毕，//退栈返回上一层，继续遍历未曾访问的结点elsePop(s,p);}returnOK;}6.42解：//求二叉树中叶子结点的数目StatusPOLeafNodeNum(int&i,BiTree&T){if(T){if(!T-lchild&&!T-rchild)i++;POLeafNodeNum(i,T-lchild);POLeafNodeNum(i,T-rchild);}returnOK;}6.43解：//按先序交换二叉树的左右子树StatusExchangeBiTree(BiTree&T){BiTreep;if(T){p=T-lchild;T-lchild=T-rchild;T-rchild=p;ExchangeBiTree(T-lchild);ExchangeBiTree(T-rchild);}returnOK;}6.45解：//删除以元素值为x的结点为根的子树StatusDelChildTree(BiTree&T,TElemTypex){if(T){if(T-data==x){DelBTree(T);T=NULL;returnOK;}else{if(DelChildTree(T-lchild,x))returnOK;else{if(DelChildTree(T-rchild,x))returnOK;elsereturnERROR;}}}elsereturnERROR;}//删除二叉树StatusDelBTree(BiTree&T){if(T){DelBTree(T-lchild);DelBTree(T-rchild);deleteT;returnOK;}elsereturnERROR;}6.47解：typedefBiTreeQElemType;#includec:\Yin\include\Queue.hStatusLevelOrderTraverse(BiTree&T,Status(*Visit)(TElemTypee)){QElemTypep;Queueq;InitQueue(q);if(T)EnQueue(q,T);while(!QueueEmpty(q)){DeQueue(q,p);Visit(p-data);if(p-lchild)EnQueue(q,p-lchild);if(p-rchild)EnQueue(q,p-rchild);}returnOK;}6.56解：先对二叉树T进行先序线索，得到先序线索二叉树Thrt。然后再进行查找。//先序线索二叉树算法StatusPreOrderThreading(BiThrTree&Thrt,BiThrTree&T){BiThrTreepre;Thrt=newBiThrNode;//为线索二叉树建立头结点if(!Thrt)exit(OVERFLOW);Thrt-LTag=Thread;Thrt-RTag=Link;Thrt-lchild=Thrt;//左子树回指if(!T)Thrt-rchild=Thrt;//若二叉树空，右子树回指else{Thrt-rchild=T;pre=Thrt;PreThreading(T,pre);//先序遍历进行先序线索化pre-rchild=Thrt;//最后一个结点线索化pre-RTag=Thread;Thrt-lchild=pre;}returnOK;}StatusPreThreading(BiThrTree&T,BiThrTree&pre){if(T){if(!T-lchild){T-LTag=Thread;T-lchild=pre;}if(pre&&!pre-rchild){pre-RTag=Thread;pre-rchild=T;}pre=T;if(T-LTag==Link)PreThreading(T-lchild,pre);if(T-RTag==Link)PreThreading(T-rchild,pre);}returnOK;}//从二叉线索树上任一结点q开始查找结点*p。//如果找到，将*p的后继结点指针存于q中，返回TRUE；否则返回FALSEStatusFindNextInBiThrTree(BiThrTree&q,TElemType*p){BiThrTreept=q;if(!pt)returnFALSE;if(pt-data==*p){if(pt-LTag==Link)q=pt-lchild;elseq=pt-rchild;returnOK;}pt=q-rchild;while(pt!=q&&pt-data!=*p){if(pt-LTag==Link)pt=pt-lchild;elsept=pt-rchild;}if(pt==q)returnFALSE;if(pt-data==*p){if(pt-LTag==Link)q=pt-lchild;elseq=pt-rchild;}returnOK;}6.57解：StatusPostOrderThreading(BiThrTree&T,BiThrTree&pre);//首先建立后序线索树StatusFindNextInBiThrTree(BiThrTree&q,TElemType*p);//再进行查找//后序线索二叉树的算法StatusPostOrderThreading(BiThrTree&Thrt,BiThrTree&T){BiThrTreepre;Thrt=newBiThrNode;//为线索二叉树建立头结点if(!Thrt)exit(OVERFLOW);Thrt-LTag=Link;Thrt-RTag=Thread;Thrt-rchild=Thrt;//右子树回指if(!T)Thrt-lchild=Thrt;//若二叉树空，左子树回指else{Thrt-lchild=T;pre=Thrt;PostThreading(T,pre);//后序遍历进行后序线索化pre-rchild=Thrt;//最后一个结点线索化pre-RTag=Thread;Thrt-rchild=pre;}returnOK;}StatusPostThreading(BiThrTree&T,BiThrTree&pre){if(T){if(T-LTag==Link)PostThreading(T-lchild,pre);if(T-RTag==Link)PostThreading(T-rchild,pre);if(!T-lchild){T-LTag=Thread;T-lchild=pre;}if(pre&&!pre-rchild){pre-RTag=Thread;pre-rchild=T;}pre=T;}returnOK;}6.62解：//树的深度intDepth(CSTree&T){intd1,d2;if(T){d1=1+Depth(T-firstchild);d2=Depth(T-nextsibling);returnd1d2?d1:d2;}elsereturn0;}7.14解：StatusCreateAG(ALGraph&G){intn,e,k,i,j;cout请输入顶点数：;cinn;cout请输入边数：;cine;G.vernum=n;G.arcnum=e;//建立顶点数组for(k=0;kG.vernum;k++){cout请输入顶点信息：;cinG.vertices[k].data;G.vertices[k].firstarc=NULL;}//建立邻接表VertexTypev1,v2;ArcNode*p,*q;for(k=0;kG.arcnum;k++){cout请输入弧的始点和终点信息，中间用空格分开:;cinv1v2;i=LocateVex(G,v1);if(i0|