1、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即有，n 0 + N = m*N + 1也即，n 0 =（m - 1）*N +1证毕。总结：1. 除了根结点外，每个结点有唯一的分支与之对应；2. 满 m 叉树上，只存在度为 m 和度为 0 的结点。2、证明题设结点 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结点到
3、v 结点的路径序列为：r，r 1，r 2，r k，v即，r，r 1，r 2，r k 是从 r 结点到 v 结点的路径上的结点，都是 v 结点的祖先结点。则，u 结点只能在以 r ，r1，r2，rk 为根的，且不包含 v 结点作为子孙结点的子树中。对 r，r 1，r 2，r k 中的任意一个结点 x，若 v 结点在 x 结点的子树 Xi 上，u 结点在 x 结点的子树 Xj 上，其中 ij。于是，在对以 x 结点为根的树做先序遍历时，v 结点应在 u 结点之前出现（x 结点为根的先序遍历是 BT 的先序遍历序列的子序列） ，从而与原题的条件矛盾；若 u 结点在 x 结点的子树 Xi 上，v 结点
4、在 x 结点的子树 Xj 上，其中 ij。于是，在对以 x 结点为根的树做后序遍历时，u 结点应在 v 结点之前出现（x 结点为根的后序遍历是 BT 的后序遍历序列的子序列） ，从而与原题的条件矛盾。所以，u 结点不能是 r，r 1，r 2，r k 以外的结点，只能是 r，r 1，r 2，r k 中的某个结点，即 u 结点是 v 结点的祖先结点。证毕。要点：1. 先序遍历和后序思想； 2. 结点的层次关系； 2. 证明思路清晰。3、证明题 设结点 u 和结点 v 是树中的两个结点，且结点 u 是结点 v 的祖先。试证明在对该树的先序遍历序列中 u 在 v 之前，而在其后序遍历序列中 u 在 v
5、 之后。证明：树的先序遍历算法：先访问树的根结点，然后依次先序遍历根的每棵子树。树的后序遍历算法：先依次后序遍历根的每棵子树，然后访问树的根结点。因为结点 u 是结点 v 的祖先，则以结点 u 为根的子树必包括结点 v，v 是 u 的子树。根据树的先序遍历算法，当遍历到以结点 u 为根的子树时，第一个遍历的结点为 u，v必然在 u 的后面，即对该树的先序遍历序列中 u 在 v 之前。根据树的后序遍历算法，当遍历到以结点 u 为根的子树时，最后一个遍历的结点为u，v 必然在 u 的前面，即对该树的后序遍历序列中 u 在 v 之后。故命题得证。要点：1、说明树的先序遍历算法、后序遍历算法。2、论证
6、树的先序遍历序列中 u 在 v 之前。3、论证树的后序遍历序列中 u 在 v 之后。4、证明题设一棵度为 k 的非空树上的叶子结点数为 n0，度为 i 的结点数为 ni（1ik） ，试证明以下关系成立。kn0 = 1 + (i-1)* nii =1证明：设分支总数为 B，结点总数为 N。根据题意，有B= n1 + 2*n2 + +k*nkN= n0 + n1 + n2 + +nk又因为除了根结点外，每个结点有唯一的分支与之对应。所以，N = B + 1即有，n 0 + n1 + n2 + +nk = n1 + 2*n2 + +k*nk + 1也即，kn0 = 1 + (i-1) * nii =1证毕。要点：1. 除了根结点外，每个结点有唯一的分支与之对应；2. 结点总数 = 分支总数+1 。
