树的行数公式

Question

这不是最好的标题，但更容易直观地解释。我想知道转置整理的二叉树矩阵（因为缺少更好的术语）的行数。通常一棵树的根在第一行，在这种情况下，它的根在最右边的列，叶子在最左边的列。我已经移动了每棵树的位置，不让 space 朝向顶行。

例如，高度为 4 的树（可以在公式中使用的已知值）将如下所示：

  0|1|2|3
0 *|*|*|*
1 *|*|*
2 *|*
3 *|*
4 *
5 *
6 *
7 *

树的连接方式示例：

(0,3)->{(0,2), (1,2)}
(3,1)->{(6,0),(7,0)}
(1,1)->{(2,0),(3,0)}

映射如下：

0->4
1->3
2->2
3->2
4->1
5->1
6->1
7->1

我已经尝试了一堆公式，甚至查看了 oeis 的序列都无济于事。

Answer 1

我假设这种编码是关于完美二叉树的，即所有内部节点都有 2 个子节点，并且树的叶子都在同一个 level/depth.

如果您查看右侧缺失个星号的数量，与第一行相比，您会得到以下序列：

0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5...等等。

2 的出现次数是 1 的两倍，3 的出现次数是 2 的两倍，...等等

这里的公式是^⌈log_₂^⌉，其中 one-based 行号。

要获取星号的数量而不是缺失的数量，您需要输入（在您的示例中 =4）。由于您的行编号从零而不是一开始，因此公式变为：

星号() = − ^⌈log_₂(+1)^⌉

Formula for the number of rows of a tree