これが宿題の一部であることを隠しているわけではありませんが、ここに投稿する前に十分に試しました.
だから...
ノードkの左の子が2kにあり、右の子が2k + 1の位置にあることをバイナリツリーで証明する必要があります。これを帰納法で証明しました。
ここで、ノード k の親がその(floor)(k/2)位置にあることを二分木で証明する必要があります。私は2つのケースを取りました。
インダクションでもやってみました。これは、3 つのノードのツリーに当てはまります。
ノード k について真であれば、ノード k + 1 について証明します。
- ノード k+1 がノード k と親を共有している場合、それは明らかに真です。
- ノード k+1 がノード k と異なる親を持つ場合....
私は一般的な二分木を作ろうとしていますが、型は帰納法の仮定を使用するのに役立ちません。子供の位置については、以前に証明したことを使用する必要があると思います。
何か助けはありますか？