3 阶 B 树的叶子数
the number of leaves of B tree of order 3
我是数据结构的新手，
我想知道一棵高度为 h 的 3 阶 B 树有多少叶子？
假设根的高度为1。
我的看法：
当高度为1时，叶子最少的为2（根据定义），叶子的最大值为3.
那么当它长到2的时候，叶子的最大数量就变成了6，
然后长到3，最大叶子数变成9，
之后叶子的数量总是 9
有人可以帮我解决这个问题吗？
谢谢
我假设您使用 Knuth 的叶子定义，即它们是不携带任何信息的 NIL 节点，以及 Knuth 的顺序定义，即一个内部节点可以具有的最大 children 个数。
my opinion: when height is 1, the[n] least of leaves are 2 (according to the definition), and the maximum of it is 3.
正确。
Then when it grows to 2, the maximum number of leaves becomes 6
...仅当根有两个 children 时，但这不是最大值。根可以有 3 个 children，每个 children 可以有 3 个叶子，所以我们有 3 x 3 = 9
then grows to 3, the maximum number of leaves becomes 9, and after that the number of leaves is always 9
在这里我失去了你的逻辑......高度为 2 的树的 9 个叶子中的每一个都可以变成一个具有三个新叶子的内部节点，所以我们得到 9 x 3 = 27 个叶子
叶子的数量通过乘以你拥有的叶子数量减少一个高度来最大化。
所以公式是：max(#leaves) = 3h
我是数据结构的新手， 我想知道一棵高度为 h 的 3 阶 B 树有多少叶子？
假设根的高度为1。
我的看法： 当高度为1时，叶子最少的为2（根据定义），叶子的最大值为3.
那么当它长到2的时候，叶子的最大数量就变成了6， 然后长到3，最大叶子数变成9， 之后叶子的数量总是 9
有人可以帮我解决这个问题吗？ 谢谢
我假设您使用 Knuth 的叶子定义，即它们是不携带任何信息的 NIL 节点，以及 Knuth 的顺序定义，即一个内部节点可以具有的最大 children 个数。
my opinion: when height is 1, the[n] least of leaves are 2 (according to the definition), and the maximum of it is 3.
正确。
Then when it grows to 2, the maximum number of leaves becomes 6
...仅当根有两个 children 时，但这不是最大值。根可以有 3 个 children，每个 children 可以有 3 个叶子，所以我们有 3 x 3 = 9
then grows to 3, the maximum number of leaves becomes 9, and after that the number of leaves is always 9
在这里我失去了你的逻辑......高度为 2 的树的 9 个叶子中的每一个都可以变成一个具有三个新叶子的内部节点，所以我们得到 9 x 3 = 27 个叶子
叶子的数量通过乘以你拥有的叶子数量减少一个高度来最大化。
所以公式是：max(#leaves) = 3h