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

．最低高度二叉树的特点是除最下层结点个数不满外其余各层的结点数都应达到各层的最大值设n个结点的二叉树的最低高度是h则n应满足h<n<=h关系式解此不等式并考虑h是整数则有h=ëlognû+即任一结点个数为n 的二叉树的高度至少为O(logn)

．n(本题等价于高度为n的满二叉树有多少叶子结点从根结点到各叶子结点的单枝树是不同的二叉树)

．由于本题求二叉树的结点数最多是多少第层共有=个结点已知有个叶子其余个结点均为分支结点它在第八层上有个叶子结点所以该二叉树的结点数最多可达(+)=(注意本题并未明说完全二叉树的高度但根据题意只能层)

．（=）

．证明设度为和 的结点数是n和n则二叉树结点数n为n=m+n+n…………()

由于二叉树根结点没有分枝所指度为和的结点各有个和个分枝度为 的结点没有分枝故二叉树的结点数n与分枝数B有如下关系n=B+=n+*n+…………()

由（）和（）得n=m即n个结点的二叉树若叶子结点数是m则非叶子结点中有（m）个度为其余度为

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