河海大学自命题数据结构及程序设计（838）-------树的相关证明题
1.证明任一结点个数为n 的二叉树的高度至少为O(logn)
证明：最低高度二叉树的特点是，除最下层结点个数不满外，其余各层的结点数都应达到各层的最大值。设n个结点的二叉树的最低高度是h，则n应满足2h-1<n<=2h-1关系式。解此不等式，并考虑h是整数，则有h=⎣logn⎦+1，即任一结点个数为n 的二叉树的高度至少为O(logn)。
2．任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有（m-1）
个度为2，其余度为1。
证明：证明：设度为1和2 的结点数是n1和n2，则二叉树结点数n为n=m+n1+n2………… (1)由于
二叉树根结点没有分枝所指，度为1和2的结点各有1个和2个分枝，度为0 的结点没有分枝，故二叉
树的结点数n与分枝数B有如下关系n=B+1=n1+2*n2+1……………………….(2)由（1）和（2），得n2=m-1。即n个结点的二叉树，若叶子结点数是m，则非叶子结点中有（m-1）个度为2，其余度为1。
3.试证明，在具有n(n>=1)个结点的m次树中，有n(m-1)+1个指针是空的。
证明：n个结点的m次树，共有n*m个指针。除根结点外，其余n-1个结点均有指针所指，故空指针
数为n*m-(n-1)=n*(m-1)+1。证毕。
4.对于任意一棵非空的二叉树T，我们用n0表示T中叶子结点的个数，用n2表示T中有两
棵非空子树的结点的个数。（1）给出n0和n2所满足的关系式。（2）证明你在（1）中给出
的关系式成立。
证明：证明设度为1和2 及叶子结点数分别为n0，n1和n2，则二叉树结点数n为n=n0+n1+n2  (1)再看二叉树的分支数，除根结点外，其余结点都有一个分支进入，设B为分支总数，则n=B+1。度为1和2
的结点各有1个和2个分支，度为0 的结点没有分支，故n=n1+2n2+1                  (2)由（1）和（2），得n0= n2+1。
5.对于具有n个叶子结点，且所有非叶子结点都有左右孩子的二叉树，
(1)试问这种二叉树的结点总数是多少？
(2)试证明∑
=
-
-
n
i
l i
1
)1
(
2
=1。其中:l i表示第i个叶子结点所在的层号(设根结点所在层号为1)。
证明：(1)根据二叉树度为2 结点个数等于叶子结点个数减1的性质，故具有n个叶子结点且非叶子结点均有左左子树的二叉树的结点数是2n-1。
(2)证明：当i=1时，2-（1-1）=20=1，公式成立。设当i=n-1时公式成立，证明当i=n时公式仍成立。设某叶子结点的层号为t，当将该结点变为内部结点，从而再增加两个叶子结点时，这两个叶子结点的层号都是t+1，对于公式的变化，是减少了一个原来的叶子结点，增加了两个新叶子结点，反映到公式中，因为2-(t-1)=2-(t+1-1)+2-(t+1-1)，所以结果不变，这就证明当i=n时公式仍成立。证毕．
6. 设T是具有n个内结点的扩充二叉树，I是它的内路径长度，E是它的外路径长度。（1）试利用归纳法证明E=I+2n,  n>=0.
（2）利用（1）的结果试说明：成功查的平均比较次数s与不成功查的平均比较次数u 之间的关系可用公式表示s=(1+1/n)u-1,n>=1。
证明：（1）设n=1，则e=0+2*1=2（只有一个根结点时，有两个外部结点），公式成立。
设有n个结点时，公式成立，即
E n=I n+2n                                          (1)
现在要证明，当有n+1个结点时公式成立。
增加一个内部结点，设路径长度为l，则
I n+1=I n+l                                          (2)
该内部结点，其实是从一个外部结点变来的，即这时相当于也增加了一个外部结点（原外部结点变成内部结点时，增加两个外部结点），则
E n+1=E n+l+2                                        (3)
由（1）和（2），则（3）推导为
E n+1=I n+2n+l+2=I n+1-l+2n+l+2
=I n+1+2(n+1）
故命题成立
二叉树公式
（2）成功查的平均比较次数s=I/n
不成功查的平均比较次数u=（E-n）/（n+1）=（I+n）/n+1
由以上二式，有s=（1+1/n）*u-1 。
7.证明：在任何一棵非空二叉树中有下面的等式成立：叶结点的个数=二度结点的个数+1
证明：证明设度为1和2 及叶子结点数分别为n0，n1和n2，则二叉树结点数n为n=n0+n1+n2  (1)再看二叉树的分支数，除根结点外，其余结点都有一个分支进入，设B为分支总数，则n=B+1。度为1和2的结点各有1个和2个分支，度为0 的结点没有分支，故n=n1+2n2+1                  (2)由（1）和（2），得n0= n2+1。
8. 如果给出了一个二叉树结点的前序序列和对称序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。如果给出了一个二叉树结点的前序序列和后序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例
证明：给定二叉树结点的前序序列和对称序（中序）序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（设l个元素）表示左子树，若左边无元素，则说明左子树为空；右边（设r个元素）是右子树，若为空，则右子树为空。根据前序遍历中“根—左子树—右子树”的顺序，则由从第二元素开始的l个结点序列和中序序列根左边的l个结点序列构造左子树，由前序序列最后r个元素序列与中序序列根右边的r个元素序列构造右子树。
由二叉树的前序序列和后序序列不能唯一确定一棵二叉树，因无法确定左右子树两部分。例如，任何结点只有左子树的二叉树和任何结点只有右子树的二叉树，其前序序列相同，后序序列相同，但却是两棵
不同的二叉树。
9.在二叉树的三种遍历序列中，所有叶子结点间的先后关系都是相同的。要求每步论断都指出根据
证明：前序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。若将“根”去掉，三种遍历就剩“左右”。三种遍历中的差别就是访问根结点的时机不同。二叉树是递归定义的，对左右子树均是按左右顺序来遍历的，因此所有叶子结点间的先后关系都是相同的。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。