数据结构证明题(共2页).docx
精选优质文档-倾情为你奉上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的祖先。证明：用反证法证明本题：假设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，rk中的任意一个结点x，若v结点在x结点的子树Xi上，u结点在x结点的子树Xj上，其中i<j。于是，在对以x结点为根的树做先序遍历时，v结点应在u结点之前出现（x结点为根的先序遍历是BT的先序遍历序列的子序列），从而与原题的条件矛盾；若u结点在x结点的子树Xi上，v结点在x结点的子树Xj上，其中i<j。于是，在对以x结点为根的树做后序遍历时，u结点应在v结点之前出现（x结点为根的后序遍历是BT的后序遍历序列的子序列），从而与原题的条件矛盾。所以，u结点不能是r，r1，r2，rk以外的结点，只能是r，r1，r2，rk中的某个结点，即u结点是v结点的祖先结点。证毕。3、证明题 设结点u和结点v是树中的两个结点，且结点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、证明题设一棵度为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的结点。证明：假设有一个以上结点的huffman 树中有度为1的结点A,其子结点为B,则我们可以将A.B合并为一个结点，则B以下的叶子结点的路径长度减小，树的带权路径长度减小。新树的WPL小于huffman树，这与huffman树的定义是相矛盾的。故得证。6、证明：由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。 证明：采用递归法证明。 当 n=1 时，前序序列和中序序列均只有一个元素，且相同，即为树的根，由此惟一确定了一棵二叉树。 假设 nm-1 时命题均成立，则证明 n=m 时亦成立。 假设前序序列为 a1，a2，.，am，中序序列为 b1，b2，.，bm。 因为前序序列由前序遍历二叉树所得，则 a1即为根结点的元素，又中序序列由中序遍历二叉树所得，则在中序序列中必能找到和 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，.，bjá1惟一确定了左子树，子序列aj+1，.，am和bj+1，.，bm惟一确定了右子树。 由此，证明了惟一的根及其左、右子树只能构成一棵确定的二叉树。专心-专注-专业
