(2020年北化工考研真题已知一棵完全二叉树的第9层（设根为第1层）有100个叶结点，则该完全二叉树的结点个数最多

可以用完全二叉树结点个数的公式来求解，即$2^h-1$，其中$h$为树的高度。由于题目已知第9层有100个叶结点，因为是完全二叉树，所以第8层必定有50个结点（每个叶结点的父结点都是第8层的结点）。同理，第7层有25个结点，第6层有12个结点，第5层有6个结点，第4层有3个结点，第3层有2个结点，第2层有1个结点，第1层有1个结点。因此，该完全二叉树的高度为9，结点个数为$2^9-1=511$。

相关问题

已知一棵完全二叉树的第9层（设根为第1层）有100个叶结点，则该完全二叉树的结点个数最多是：

### 回答1：
该完全二叉树的第9层有100个叶结点，由于是完全二叉树，第8层的结点数为200，第7层的结点数为400，以此类推，第1层的结点数为2^8=256。因此，该完全二叉树的结点个数最多为：

1 + 2 + 4 + ... + 256 = 2^9 - 1 = 511

### 回答2：
我们知道，完全二叉树是指一棵二叉树中，除了最后一层，其他的层都是满的，而且最后一层的结点集中在左侧。对于一棵完全二叉树，设其深度为h，则第一层至第h-1层的结点共有2^(h-1)-1个。

根据题目条件，第9层有100个叶结点，那么第8层就有200个结点。由于该完全二叉树是满的，所以可以推断出8层共有2^7-1=127个结点，即127-200=-73个下层结点是不存在的。即第8层的后73个结点是不存在的。同理，可以推算出第7层的下层结点也不存在，以此类推，直到第2层的下层结点不存在。最终，我们得到的是一棵以第9层为叶子结点，第2层为根节点的完全二叉树，共8层。

根据完全二叉树的性质，第1层至第8层的结点共有2^8-1=255个。而第9层有100个叶子结点，则第9层共有100*2=200个结点。综上所述，该完全二叉树的结点个数最多为255+200=455个。

因此，我们可以得出结论：已知一棵完全二叉树的第9层有100个叶结点，则该完全二叉树的结点个数最多为455个。

### 回答3：
因为完全二叉树每一层都是满的，所以第9层的100个叶子节点，其上一层必然有50个节点。同理，第8层有25个节点，第7层有12个，一直到第1层只有1个。

那么我们可以来尝试构造一棵符合条件的完全二叉树：

1
/ \
2 3
/ \ / \
4 5 6 7
......
50
/ \
51 ... 100

从上述结构我们可以看出，该完全二叉树的第1层到第8层都是满的，而第9层有100个叶子节点。所以，该完全二叉树的结点个数的下限是：$1+2+2^2+...+2^8=2^9-1=511$。

接下来考虑如何在保证有100个叶子节点的前提下，让结点个数最大。

我们可以把第1层到第8层的节点数求和，得到$1+2+2^2+...+2^7=2^8-1=255$。因为第9层有100个叶子节点，所以第1层到第9层的节点数之和为$511+100=611$。

然后我们考虑构造完全二叉树的过程中，如何使得结点个数最大。我们发现，在第1层到第8层的节点总数已经确定的情况下，我们要让第9层尽可能地满。这就意味着，除了最后一层，每一层的节点数都应该是上一层节点数的二倍，而最后一层的节点数应该是剩余节点数的二倍。

在具体构造过程中，我们可以先把前8层填充完，然后用剩下的153个节点来填充第9层，即可得到一个结点个数为$511+153=664$的完全二叉树。

因此，该完全二叉树的结点个数最多为664。

已知一棵完全二叉树的第5层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是

253个。

解析：

首先，这是一棵完全二叉树，因此第1层只有根结点，第2层有2个结点，第3层有4个结点，第4层有8个结点，第5层有16个结点。

又已知第5层有8个叶结点，因此第5层所有结点都是叶结点，第6层没有结点。

设该二叉树共有n个结点，则有：

n = 1 + 2 + 4 + 8 + 16 = 31

但是根据题目所给信息，第5层有8个叶结点，即该二叉树的叶结点数为8，则该二叉树的高度为5，而根据完全二叉树的性质，高度为h的完全二叉树的结点数最多为2^(h+1)-1。因此，该完全二叉树的结点个数最多为：

2^(5+1)-1=63

又因为该二叉树只有8个叶结点，因此结点数不会达到63。因此，该完全二叉树的结点个数最多是253个。