tree - 树的行数公式

Question

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

例如，高度为 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 的序列无济于事。

标签： treeformula

Answer 1

我假设这种编码是关于完美二叉树的，即所有内部节点都恰好有 2 个子节点，并且树的叶子都在相同的级别/深度上。

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

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

2 出现的次数是 1 的两倍，而 3 的出现次数是 2 的两倍，……等等。

这里的公式是^⌈log ₂ ⌉</ sup>，其中是从一开始的行号。</sup>

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

      星号() = − ^⌈log ₂ (+1) ⌉</ sup></sup>