数据结构证明题(共2页).docx

《数据结构证明题(共2页).docx》由会员分享，可在线阅读，更多相关《数据结构证明题(共2页).docx（2页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上1、 试证明：一棵非空的满m叉树上叶子结点数n0和非叶子结点数N之间满足以下关系：n0 =（m - 1）*N + 1证明：设分支总数为B，结点总数为M。因为在满m叉树上，只存在度为m和度为0的结点，所以，B = m*N M=n0 + N又因为除了根结点外，每个结点有唯一的分支与之对应。所以，M = B + 1 = m*N + 1即有，n0 + N = m*N + 1也即，n0 =（m - 1）*N +1证毕。2、证明题设结点u和结点v是树中的两个结点，且在对该树的先序遍历序列中u在v之前，而在其后序遍历序列中u在v之后，试证明结点u是结点v的祖先。证明：用反证法证明本

2、题：假设u结点不是v结点的祖先结点，并设该树为BT，其根结点为r结点。则u结点不在从r结点到v结点的路径上。分两种情况讨论：1若u结点是结点v的子树上的结点，则，在BT的先序遍历序列中，子树上的所有结点都在v结点之后，即u结点在v结点之后出现，故与原题条件矛盾，所以u结点不能是v的子树上的结点。2若u结点不是结点v的子树上的结点，即u结点不为v结点的子孙结点,可设从r结点到v结点的路径序列为：r，r1，r2，rk，v即，r，r1，r2，rk是从r结点到v结点的路径上的结点，都是v结点的祖先结点。则，u结点只能在以r ，r1，r2，rk为根的，且不包含v结点作为子孙结点的子树中。对r，r1，r2

3、，rk中的任意一个结点x，若v结点在x结点的子树Xi上，u结点在x结点的子树Xj上，其中ij。于是，在对以x结点为根的树做先序遍历时，v结点应在u结点之前出现（x结点为根的先序遍历是BT的先序遍历序列的子序列），从而与原题的条件矛盾；若u结点在x结点的子树Xi上，v结点在x结点的子树Xj上，其中ij。于是，在对以x结点为根的树做后序遍历时，u结点应在v结点之前出现（x结点为根的后序遍历是BT的后序遍历序列的子序列），从而与原题的条件矛盾。所以，u结点不能是r，r1，r2，rk以外的结点，只能是r，r1，r2，rk中的某个结点，即u结点是v结点的祖先结点。证毕。3、证明题 设结点u和结点v是树中

4、的两个结点，且结点u是结点v的祖先。试证明在对该树的先序遍历序列中u在v之前，而在其后序遍历序列中u在v之后。证明：树的先序遍历算法：先访问树的根结点，然后依次先序遍历根的每棵子树。树的后序遍历算法：先依次后序遍历根的每棵子树，然后访问树的根结点。因为结点u是结点v的祖先，则以结点u为根的子树必包括结点v，v是u的子树。根据树的先序遍历算法，当遍历到以结点u为根的子树时，第一个遍历的结点为u，v必然在u的后面，即对该树的先序遍历序列中u在v之前。根据树的后序遍历算法，当遍历到以结点u为根的子树时，最后一个遍历的结点为u，v必然在u的前面，即对该树的后序遍历序列中u在v之后。故命题得证。4、证明

5、题设一棵度为k的非空树上的叶子结点数为n0，度为i的结点数为ni（1ik），试证明以下关系成立。 kn0 = 1 + (i-1)* ni i =1证明：设分支总数为B，结点总数为N。根据题意，有B= n1 + 2*n2 + +k*nkN= n0 + n1 + n2 + +nk又因为除了根结点外，每个结点有唯一的分支与之对应。所以，N = B + 1结点总数 = 分支总数+1即有，n0 + n1 + n2 + +nk = n1 + 2*n2 + +k*nk + 1也即， kn0 = 1 + (i-1) * ni i =1证毕。5、证明:在结点数多于1的哈夫曼树中不存在度为1的结点。证明：假设有一

6、个以上结点的huffman 树中有度为1的结点A,其子结点为B,则我们可以将A.B合并为一个结点，则B以下的叶子结点的路径长度减小，树的带权路径长度减小。新树的WPL小于huffman树，这与huffman树的定义是相矛盾的。故得证。6、证明：由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。证明：采用递归法证明。当n=1时，前序序列和中序序列均只有一个元素，且相同，即为树的根，由此惟一确定了一棵二叉树。假设nm-1时命题均成立，则证明n=m时亦成立。假设前序序列为a1，a2，.，am，中序序列为b1，b2，.，bm。因为前序序列由前序遍历二叉树所得，则a1即为根结点的元素，又中序序列由中

7、序遍历二叉树所得，则在中序序列中必能找到和a1值相同的元素，设为bj，由此可以得到b1，.，bj-1为左子树的中序序列，bj+1，.bm为右子树的中序序列。若j=1，即b1为根，此时二叉树的左子树为空，a2，.，am为右子树的前序序列，b2，.，m为右子树的中序序列。右子树上的结点数为m-1，由此，这二个序列惟一确定了右子树，就惟一确定了二叉树。若j=m，即bm为根，此时二叉树的右子树为空，则子序列a2，.，am和b1，.，bm-1一确定左子树。若2jm-1，则子序列a2，.，aj和b1，.，bj1惟一确定了左子树，子序列aj+1，.，am和bj+1，.，bm惟一确定了右子树。由此，证明了惟一的根及其左、右子树只能构成一棵确定的二叉树。专心-专注-专业