数据结构考研分类复习真题 第六章 答案 (四)[8]

()根据二叉树度为 结点个数等于叶子结点个数减的性质故具有n个叶子结点且非叶子结点均有左左子树的二叉树的结点数是n

()证明当i=时（）==公式成立设当i=n时公式成立证明当i=n时公式仍成立

设某叶子结点的层号为t当将该结点变为内部结点从而再增加两个叶子结点时这两个叶子结点的层号都是t+对于公式的变化是减少了一个原来的叶子结点增加了两个新叶子结点反映到公式中因为(t)=(t+)+(t+)所以结果不变这就证明当i=n时公式仍成立证毕．

．结点数的最大值h（满二叉树）最小值h（第一层根结点其余每层均两个结点）

．（）k(u)++i () ë(v)/kû+ (参见第题推导)

．该二叉树是按前序遍历顺序编号以根结点为编号前序遍历的顺序是根左右

．（）设n=则e=+*=（只有一个根结点时有两个外部结点）公式成立

设有n个结点时公式成立即

En=In+n()

现在要证明当有n+个结点时公式成立

增加一个内部结点设路径长度为l则

In+=In+l ()

该内部结点其实是从一个外部结点变来的即这时相当于也增加了一个外部结点（原外部结点变成内部结点时增加两个外部结点）则

En+=En+l+()

由（）和（）则（）推导为

En+=In+n+l+=In+l+n+l+

=In++(n+）

故命题成立

（）成功查找的平均比较次数s=I/n

不成功查找的平均比较次数u=（En）/（n+）=（I+n）/n+

由以上二式有s=（+/n）*u

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []