二叉樹的數學證明

Question

我並沒有隱藏這是我功課的一部分，但我已經嘗試過，然後發佈在這裏。

所以...
我需要證明一個二叉樹，節點k有2k + 1位置上的2k和右子節點。我通過歸納證明了這一點。

現在我需要證明一個二叉樹，一個節點k在(floor)(k/2)的位置上有其父。我拿了兩個案子。
試用誘導也是如此。對於3個節點的樹是真的。
如果它是節點k真正的我會證明爲節點k + 1

1. 如果節點k + 1股的父與節點k這顯然是正確的。
2. 如果節點k + 1與節點k區別父....

我想做一個普通的二叉樹，但類型不會幫我用歸納假設。我想也許我必須使用我之前爲孩子的位置所證明的。

任何幫助？

Answer 1

所以你已經證明第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），因爲k是整數，所以floor（k）= k，所以這裏父節點也在floor（i/2）處。

由於集中的所有奇數和偶數兒童佔所有兒童，第i個孩子的父母是地板（I/2）

QED？對不起，如果這不是嚴格或正式的..