質問: '\0' ) return; postorder(heap,2i+1); printf("%c ",heap[i]); return; } ```
回答: 多分用語がわかっていないと思うので、まずそこを抑えてください。 完全2分木とは > > 1.すべての枝分かれが2つ > > 2.すべての枝分かれの先っぽが最初の地点から同じ距離 > > > わかった気になるだけの説明の多いサイトですが、この説明に関しては本当にわかりやすいです。 二分木の中でも、途中で欠けた枝のない完全なものが完全二分木です。 まずここを抑えてください。 この問題は、完全二分木でなくても解けます。 完全二分木にわざわざ限定しているのは、解答の難易度を下げるためだけと思われます。 次にヒープです。 ヒープ > > 「子要素は親要素より常に大きいか等しい(または常に小さいか等しい)」という制約を持つ木構造の事。 > > > ソースの中で heap なる用語が使われていますが、これはヒープが二分木を使って実装されることが多いためと思われます。 しかし、この問題ではヒープは使われません。 ヒープを実装する前段階のようなものです。 学習が進むとヒープを実装せよという問題が出てくると思いますので、その基礎となるこの問題は他人の回答をコピペするだけでなく、しっかりと理解してください。 基礎の段階でとりこぼすと授業がわからなくなって長時間つらい思いをするはめになります。 通常、木構造を表現するには、ノードクラスを作ってそれをつなぎます。 しかし、二分木に関しては「枝の数は必ず 0~2」という制約があるので、もっと簡単な構造で表現できます。完全二分木に至っては「枝の数は必ず 0 か 2」と制約が強まるので、さらに簡単になります。 葉には子要素が無く、子要素がある場合は必ず子の数は 2 です。 まず 15 個の要素から成る配列を用意します。 要素 0 がルートで、ここから枝分かれしていきます。 ルートの左の子要素は、要素 1 です。 ルートの右の子要素は、要素 2 です。 | 0 | 1 | 2 | | --- | --- | --- | | ルート | ルートの左の子 | ルートの右の子 | このようなルールで並べます。 ノード同士をつながなくても、位置関係だけで親子関係を計算するのです。 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | | --- | --- | --- | --- | --- | --- | --- | | ルート | 0 の左の子 | 0 の右の子 | 1 の左の子 | 1 の右の子 | 2 の左の子 | 2 の右の子 | | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | | --- | --- | --- | --- | --- | --- | --- | --- | | 3 の左の子 | 3 の右の子 | 4 の左の子 | 4 の右の子 | 5 の左の子 | 5 の右の子 | 6 の左の子 | 6 の右の子 | 0 の左の子は 1 1 の左の子は 3 2 の左の子は 5 3 の左の子は 7 4 の左の子は 9 わかりますか? 親要素の要素数を 2 倍して 1 を足したものが左の子の要素数です。 同じくそれに 1 を足したものが右の子になります。 ということは、要素数が奇数の場合は 1 を引いて 2 で割ったものが親の要素数になります。偶数の場合は 2 を引いて 2 で割ったものです。 ルートから左の子に移動し、次に移動先の右の子に移動するには、 0 * 2 + 1 = 1 1 * 2 + 2 = 4 なので、0 → 1 → 4 という動きになります。 このように計算して探索してください。