完全２分木のプログラムについて

完全２分木の表現の仕方についてです。
完全２分木の走査において
先行順
中間順
後行順
の３つを表現するプログラムをC++の配列を用いて表現したいです。
ポインタにおける、->left,->rightと同じようにやりたかったのですができませんでした。
どのようにすればそのように表現できるかを教えて欲しいです。
（コードは途中まで挑戦して挫折したものです。）
よろしくお願いします。

C++
1#include <stdio.h>
2#include <stdlib.h>
3
4#define MAX 15 /* 2分木の要素数の最大値 */
5
6void sennkoujyun(char heap[], int i);
7void tyuukannjyun(char heap[], int i);
8void koukoujyun(char heap[], int i);
9
10int main(){
11
12  /* 文字を要素とするヒープによる完全2分木 */
13  char heap[MAX] = { 'a', 'b', 'c', 'd', 'e',
14		     'f', 'g', 'h', 'i', 'j',
15		     '\0', '\0', '\0', '\0', '\0' };
16
17  preorder(heap, 0);
18  putchar('\n');
19  return 0;
20}
21
22/* 先行順の評価でノードのラベルを印字する関数 */
23void sennkoujyun(char heap[], int i){
24  if( i >= MAX || heap[i] == '\0' ) return;
25    preorder(heap,2i+1);
26    printf("%c ",heap[i]);
27    preorder(heap,2i+2);
28    return;
29}
30
31/* 中間順の評価でノードのラベルを印字する関数 */
32void tyuukannjyun(char heap[], int i){
33  if( i >= MAX || heap[i] == '\0' ) return;
34    inorder(heap,2i+1);
35    printf("%c ",heap[i]);
36    return;
37}
38
39/* 後行順で評価でノードのラベルを印字する関数 */
40void koukoujyun(char heap[], int i){
41  if( i >= MAX || heap[i] == '\0' ) return;
42    postorder(heap,2i+1);
43    printf("%c ",heap[i]);
44  return;
45}

退会済みユーザー

2018/10/27 08:08

なんだか課題のひな形っぽい気が…。とりあえず、できなかった ->left,->right ｶｸｶｸｼｶｼﾞｶという部分だけのプログラムを作って考えてみてはどうですか？

行動規範の内容に同意します

回答1件

ベストアンサー

多分用語がわかっていないと思うので、まずそこを抑えてください。

完全2分木とは

１．すべての枝分かれが2つ

２．すべての枝分かれの先っぽが最初の地点から同じ距離

わかった気になるだけの説明の多いサイトですが、この説明に関しては本当にわかりやすいです。
二分木の中でも、途中で欠けた枝のない完全なものが完全二分木です。
まずここを抑えてください。

この問題は、完全二分木でなくても解けます。
完全二分木にわざわざ限定しているのは、解答の難易度を下げるためだけと思われます。

次にヒープです。

ヒープ

「子要素は親要素より常に大きいか等しい（または常に小さいか等しい）」という制約を持つ木構造の事。

ソースの中で heap なる用語が使われていますが、これはヒープが二分木を使って実装されることが多いためと思われます。
しかし、この問題ではヒープは使われません。
ヒープを実装する前段階のようなものです。
学習が進むとヒープを実装せよという問題が出てくると思いますので、その基礎となるこの問題は他人の回答をコピペするだけでなく、しっかりと理解してください。
基礎の段階でとりこぼすと授業がわからなくなって長時間つらい思いをするはめになります。

通常、木構造を表現するには、ノードクラスを作ってそれをつなぎます。
しかし、二分木に関しては「枝の数は必ず 0～2」という制約があるので、もっと簡単な構造で表現できます。完全二分木に至っては「枝の数は必ず 0 か 2」と制約が強まるので、さらに簡単になります。
葉には子要素が無く、子要素がある場合は必ず子の数は 2 です。

まず 15 個の要素から成る配列を用意します。
要素 0 がルートで、ここから枝分かれしていきます。
ルートの左の子要素は、要素 1 です。
ルートの右の子要素は、要素 2 です。