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

．证明设二叉树度为和的结点数及总的结点数分别为nn 和n则n=n+n ………()

再设二叉树的分支数为B除根结点外每个结点都有一个分支所指则n=B+ ………()

度为零的结点是叶子没有分支而度为的结点有两个分支因此（）式可写为n=*n+ …………()

由（）（）得n=n代入（）并由（）和（）得B=*(n) 证毕

．()kh(h为层数)

（）因为该树每层上均有Kh个结点从根开始编号为则结点i的从右向左数第２个孩子的结点编号为ki设n 为结点i的子女则关系式(i)k+<=n<=ik+成立因i是整数故结点n的双亲i的编号为ën)/kû+

() 结点n(n>)的前一结点编号为n（其最右边子女编号是(n)*k+）故结点 n的第 i个孩子的编号是(n)*k++i

() 根据以上分析结点n有右兄弟的条件是它不是双亲的从右数的第一子女即 (n)%k!=其右兄弟编号是n+

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