《证明题_答案.doc》由会员分享，可在线阅读，更多相关《证明题_答案.doc（4页珍藏版）》请在三一文库上搜索。
1、1试证明：一棵非空的满 m叉树上叶子结点数 no和非叶子结点数 N之间满足以下关系: n0 =（m - 1）*N + 1证明：设分支总数为B，结点总数为M。因为在满 m 叉树上，只存在度为 m 和度为 0 的结点， 所以， B = m*NM=n 0 + N 又因为除了根结点外，每个结点有唯一的分支与之对应。 所以， M = B + 1 = m*N + 1 即有， n0 + N = m*N + 1 也即， n0 =（ m - 1） *N +1 证毕。总结：1. 除了根结点外，每个结点有唯一的分支与之对应；2. 满 m 叉树上，只存在度为 m 和度为 0 的结点。42、证明题设结点 u 和结点 v
2、 是树中的两个结点， 且在对该树的先序遍历序列中 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结
3、点的路径序列为：r，口，（,v即，r,r2，rk是从r结点到v结点的路径上的结点，都是 v结点的祖先结点。贝U, u结点只能在以r , r1 , r2，rk为根的，且不包含 v结点作为子孙结点 的子树中。对r, ri, Q,，rk中的任意一个结点 x,若 v 结点在 x 结点的子树 Xi 上， u 结点在 x 结点的子树 Xj 上，其中 i<j 。于是， 在对以 x 结点为根的树做先序遍历时， v 结点应在 u 结点之前出现（ x 结点为根的先序 遍历是 BT 的先序遍历序列的子序列） ，从而与原题的条件矛盾；若 u 结点在 x 结点的子树 Xi 上， v 结点在 x 结点的子树 Xj
4、上，其中 i<j 。于是， 在对以 x 结点为根的树做后序遍历时， u 结点应在 v 结点之前出现（ x 结点为根的后序 遍历是 BT 的后序遍历序列的子序列） ，从而与原题的条件矛盾。所以，u结点不能是r, ri,，rk以外的结点，只能是 r, ri,匕，g中的 某个结点，即 u 结点是 v 结点的祖先结点。证毕。要点： 1. 先序遍历和后序思想；2. 结点的层次关系；2. 证明思路清晰。3、证明题设结点 u 和结点 v 是树中的两个结点， 且结点 u 是结点 v 的祖先。 试证明在对该树的先序 遍历序列中U在v之前，而在其后序遍历序列中U在v之后。证明： 树的先序遍历算法：先访问树的
5、根结点，然后依次先序遍历根的每棵子树。 树的后序遍历算法：先依次后序遍历根的每棵子树，然后访问树的根结点。因为结点 u 是结点 v 的祖先，则以结点 根据树的先序遍历算法，当遍历到以结点 必然在 u 的后面，即对该树的先序遍历序列中根据树的后序遍历算法，当遍历到以结点 必然在 u 的前面，即对该树的后序遍历序列中故命题得证。u 为根的子树必包括结点 v， v 是 u 的子树。u 为根的子树时，第一个遍历的结点为 u， v u在v之刖。u 为根的子树时，最后一个遍历的结点为 u， v u在v之后。要点：1、说明树的先序遍历算法、后序遍历算法。2、论证树的先序遍历序列中 u 在 v 之前。3、论证
6、树的后序遍历序列中 u 在 v 之后。4、证明题设一棵度为k的非空树上的叶子结点数为n°,度为i的结点数为ni ( K i< k),试证明以下关系成立。kno = 1 + 另1)* n ii =1证明：设分支总数为B，结点总数为N。根据题意,有B= ni + 2*n 2 + +<*n kN= no + ni + n2 + +nk又因为 除了根结点外,每个结点有唯一的分支与之对应 。所以, N = B + i即有, no + ni + n2+ +nk =ni + 2*n2+ +k*nk + i也即,k no = 1 + 另1) * n ii =i证毕。要点： 1. 除了根结点外,每个结点有唯一的分支与之对应 ；2. 结点总数 = 分支总数 +1。