第6章 证明题_答案.doc

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证毕。总结：1. 除了根结点外，每个结点有唯一的分支与之对应；2. 满m叉树上，只存在度为m和度为0的结点。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结点的祖先结点。证毕。要点：1. 先序遍历和后序思想； 2. 结点的层次关系； 2. 证明思路清晰。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之后。故命题得证。要点：1、说明树的先序遍历算法、后序遍历算法。2、论证树的先序遍历序列中u在v之前。3、论证树的后序遍历序列中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即有，n0 + n1 + n2 + +nk = n1 + 2*n2 + +k*nk