数据结构完全二叉树的计算

数据结构

• 题目
• • 第一题
  • 第二题
  • 第三题

题目 第一题

一个具有1025个节点的二叉树的高h为（ C）

A.11

B.10

C.11～1025

D.12～1024

当高度为 10时，此时即使树为满二叉树也不够1025个节点，所以树高的最小取值为 11
因为每层一个结点时二叉树的层次为最大，此时为1025层，即高度为1025
而二叉树为完全二叉树时其层次最小，2^10 - 1 < 1025 < 2^11 - 1 ，所以为完全二叉树时其层次为11层，即最小高度为11，最大高度为1025，所以选C

第二题

一棵完全二叉树中有501个叶子节点，则至少有 （ C） 个节点

A.501

B.502

C.1001

D.1002

引入例题：
1.设一棵完全二叉树共有500个结点，则在该二叉树中有250个叶子结点。

2.满2叉树的结点是2的K次方减1。

3.所以，满2叉树应该有511个结点、但现在只有500个。

所以缺少了11个右结点。

是最后一层上少了倒着少了11个结点。

明确的说是少了6个右，5个左。

4.所以，应该256-11，但是由于最后一层少了11个结点，所以上一层多了5个叶子结点，所以最终答案应该是：256-11+5=250。

501*2-1=1001

第三题

一棵高度为8的完全二叉树至少有（B）叶子节点

A.63
B.64
C.127
D.128

1.满二叉树情况下叶子结点最多了，h层高的满二叉树叶子结点公式为：2^(h-1)个
2.高度为8的完全二叉树至少有2的7次方个，即128
3.二叉树的度表示节点的子树或直接继承者的数目，二叉树的度是一个子树或单子树。

2度是两个孩子，或者左和右子树有两个叉树，最大度数为2。

完全二叉树在满二叉树的基础之上/2,[127/2]=64