数据结构常考题第6章 证明题

设分支总数为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上，其中i若u结点在x结点的子树Xi上，v结点在x结点的子树Xj上，其中i所以，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的结点数为n（，i1≤i≤k）试证明以下关系成立。 k

n0 = 1 + ∑(i-1)* ni

i =1 证明：

设分支总数为B，结点总数为N。 根据题意，有

B= n1 + 2*n2 + … +k*nk N= n0 + n1 + n2 + … +nk

又因为除了根结点外，每个结点有唯一的分支与之对应。 所以，B = N -1

即有，n0 + n1 + n2 + … +nk = n1 + 2*n2 + … +k*nk 也即，

k

n0 = 1 + ∑(i-1) * ni

i =1 证毕。

要点：1. 除了根结点外，每个结点有唯一的分支与之对应；

2. 结点总数 = 分支总数+1。