数据结构证明题

1、试证明：一棵非空的满m叉树上叶子结点数n0和非叶子结点数N之间满足以下关系：n0=（m-1）*N+1证明：设分支总数为B，结点总数为M。因为在满m叉树上，只存在度为m和度为0的结点，所以，B=m*NM=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上，其中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是树中的两个结点，且结点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（1≤i≤k），试证明以下关系成立。kn0=1+∑(i-1)*nii=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)*nii=1证毕。5、证明:在结点数多于1的哈夫曼树中不存在度为1的结点。证明：假设有一个以上结点的huffman树中有度为1的结点A,其子结点为B,则我们可以将A.B合并为一个结点，则B以下的叶子结点的路径长度减小，树的带权路径长度减小。新树的WPL小于huffman树，这与huffman树的定义是相矛盾的。故得证。6、证明：由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。证明：采用递归法证明。当n=1时，前序序列和中序序列均只有一个元素，且相同，即为树的根，由此惟一确定了一棵二叉树。假设n≤m-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}一确定左子树。若2≤j≤m-1，则子序列{a2，...，aj}和{b1，...，bjá1}惟一确定了左子树，子序列{aj+1，...，am}和{bj+1，...，bm}惟一确定了右子树。由此，证明了惟一的根及其左、右子树只能构成一棵确定的二叉树。