3

我并没有隐瞒这是我家庭作业的一部分，但在发布到这里之前我已经尝试了很多。

所以...
我需要证明一个二叉树节点 k 的左子节点位于 2k 位置，右子节点位于 2k + 1 位置。我已经用归纳法证明了这一点。

现在我需要为二叉树证明节点 k 的父节点在(floor)(k/2)位置上。我拿了两个案子。
也尝试过感应。对于 3 个节点的树来说确实如此。
如果节点 k 为真，我将证明节点 k + 1。

  1. 如果节点 k+1 与节点 k 共享父节点，这显然是正确的。
  2. 如果节点 k+1 与节点 k 有不同的父节点......

我正在尝试制作一个通用的二叉树，但这些类型不会帮助我使用归纳假设。我想也许我将不得不使用我之前证明的孩子的立场。

有什么帮助吗？

4

1 回答 1

6

因此，您已经证明第 k 个节点在 2k 和 2k+1 处有子节点。那么让我们把孩子们分成两种情况，偶数和奇数。

即使对于孩子来说，他们也位于 i=2k 处一些 k。您可以看到，这意味着它的父节点位于 k、i/2 或 floor(i/2)。

对于奇数的孩子，他们位于 i=2k+1 的一些 k。你可以看到这意味着它的父节点在 k。floor(i/2) 在这种情况下等于 floor(k+1/2)，它等于 floor(k) = k，因为 k 是一个整数，所以这里的父节点也在 floor(i/2) 处。

由于所有奇偶孩子的集合构成了所有孩子，因此第 i 个孩子的父母是 floor(i/2)

QED？对不起，如果这不够严格或不够正式..

于 2013-05-14T01:31:22.397 回答