我没有隐瞒这是我作业的一部分,但在发布之前我已经尝试过了.
所以...
我需要证明一个二叉树,节点k的左子节点在2k上,右子节点在2k + 1位置.我用感应证明了这一点.
现在我需要证明一个二叉树,节点k的父节点(floor)(k/2)位置.我拿了两个案子.
也用感应试了一下.对于3个节点的树来说确实如此.
如果对于节点k是真的,我将证明节点k + 1.
我正在尝试制作一般的二叉树,但这些类型不会帮助我使用归纳假设.我想也许我将不得不使用我之前证明的孩子的位置.
有帮助吗？
所以你已经证明了第k个节点有2k和2k + 1的子节点.那么让我们把孩子分成两个案例,偶数和奇数.
对于偶数孩子,他们位于i = 2k的某些k.您可以看到这意味着它的父级位于k,或i/2或floor(i/2).
对于奇数孩子,对于某些k,他们位于i = 2k + 1.你可以看到这意味着它的父亲在k.在这种情况下,floor(i/2)等于floor(k + 1/2),其等于floor(k)= k,因为k是整数,所以这里父节点也在floor(i/2).
由于所有奇数和偶数孩子的组合构成所有孩子,所以第i个孩子的父母是地板(i/2)
QED？对不起,如果这不够严谨或正式..