python - 在适当的二叉树中将内部节点与外部节点相关联

Question

我正在使用“Python 中的数据结构和算法”学习二叉树

当作者统计“在适当的二叉树中将内部节点与外部节点相关联”时，它显示为

命题 8.9：在一个非空真二叉树 T 中，有nE外部节点和 n I 个内部节点，我们有n E= n I+1。

（``n E ,n I`和h表示节点数，外部节点数，内部节点数，）

作者继续说：

证明：我们通过从 T 中删除节点并将它们分成两个“堆”来证明这个命题，一个内部节点堆和一个外部节点堆，直到 T 变为空。这些桩最初是空的。最后，我们将证明外部节点堆比内部节点堆多一个节点。我们考虑两种情况：

• 情况 1：如果 T 只有一个节点 v，我们删除 v 并将其放在外部节点堆上。因此，外部节点堆有一个节点，内部节点堆是空的。
• 情况 2：否则（T 有多个节点），我们从 T 中删除一个（任意）外部节点 w 及其父节点 v，它是一个内部节点。我们将 w 放在外部节点堆上，将 v 放在内部节点堆上。如果 v 有一个父 u，那么我们将 u 与 w 的前兄弟 z 重新连接，如图 8.10 所示。此操作删除一个内部节点和一个外部节点，并使树成为一棵适当的二叉树。重复这个操作，我们最终得到一棵由单个节点组成的最终树。请注意，相同数量的外部和内部节点已通过导致这棵最终树的操作顺序被删除并放置在它们各自的堆上。现在，我们删除最后一棵树的节点并将其放在外部节点堆上。因此，外部节点堆比内部节点堆多一个节点。

我刚开始学习算法，但发现知名作者很可笑，他费力地绕了这么一条弯路来提高 n E =n I` +1，是的，当然，叶子（外部）是来自内部节点的原始节点更多的。我认为证明“1 + 1 = 2”或“这是地球，外星人”是非常愚蠢的

我错过了一些观点吗？

标签： pythonalgorithmtree

Answer 1

是的，当然，叶子（外部）又来自内部节点。我认为证明'1 + 1 = 2'是非常愚蠢的

不确定我是否遵循你的证明。考虑以下：

1. 实际上，每个外部节点都有一个父（内部）节点，除非树由一个节点组成，但是
2. 两个外部节点共享同一个父（内部）节点，因此上述情况会导致重复计算，并且
3. 可以有多个内部节点没有外部节点作为直接子节点。

然后证明第 2 点中提到的内部节点的不足可以通过第 3 点中提到的内部节点的过剩来弥补。

当然，这可以通过多种方式证明，但在我看来，将其与 1+1=2 进行比较过于简单化了。

另一方面，我同意这两堆的故事有点矫枉过正，但它可以帮助形象化事物。只要说内部节点和外部节点的数量之间的差异在移除操作中保持不变就足够了。

替代证明

另一种证明将作为第二个（递归）步骤删除两个兄弟外部节点。首先我们必须证明当树不只是一个节点时可以找到这样的一对：

让我们取一片到根的距离最长的叶子。因为二叉树是正确的，所以这个节点有一个兄弟节点。我们也知道这个兄弟姐妹没有孩子，否则我们选择的叶子不是离根最远的叶子。所以我们得出结论，确实我们总能找到一对外部兄弟节点。

兄弟对的删除会将它们共享的父节点变成外部节点。我们注意到我们保持了“正确的二叉树”属性。因此，我们移除 2 个外部节点，并将 1 个内部节点转换为外部节点。因此，我们最终会减少一个外部节点和一个内部节点。保持不变性。我们注意到，我们总是可以重复这个操作，直到只剩下一个节点，这就是一个外部节点。

这不像 1 + 1 = 2 那样微不足道，尽管如果您有自己的喜好，我会理解的。