木構造｜根・葉・親子と、2分木を配列で表す方法【基本情報技術者試験科目B】

木構造は、データを親と子の関係でつないだ形です。図では丸と線で描かれますが、プログラムの中では配列になっています。図の言葉と、その配列の読み方を、丸が6つの小さな木で確かめます。

期間限定クーポンPR｜Udemy の講座科目B オリジナル模試 3回分・60問42%OFF 1,500円~~2,600円~~中身を見る ›

この回の内容を動画で見る

講義の実際の画面公開記念・いまだけ先着100名0円~~通常 2,600円~~有料講座「科目B 基礎講義」プログラムを1行ずつたどり、値がどう変わるかを動画で見せます。この回の講義もこの講座に入っています。講義の目次と無料の1本を見るUdemy・12月3日まで・100名に達したら通常価格に戻ります

次のページで講義の目次と無料の講義を見られます。受講ボタンとクーポンコードもそこにあります。

木構造とは ── 親と子を、線でつないだ形
2分木 ── 子は2つまで。左と右を区別する
2分木を配列で表す ── tree[n] は、節 n の子の番号
配列だけを見て、根から葉まで降りる
次に読む

木構造とは ── 親と子を、線でつないだ形

木構造は、節（せつ）と、節どうしを結ぶ線＝枝でできています。図では節を丸で描くのがふつうです。下の図では箱で描き、節を区別するために 1 から 6 の番号（節番号）を付けました。

6つの節でできた木

箱1つ＝節。太い数字＝節番号　／　箱と箱を結ぶ線＝枝（線の上側が親。矢じりは親の側に付けてあります）　／　点線の箱＝葉（子のない節）　／　色の付いた箱＝子のある節

上が親、下が子

根深さ 01子は 2 と 3

根でも葉でもない深さ 12親は 1
子は 4 と 5

葉深さ 24親は 2
子はいない

葉深さ 25親は 2
子はいない

根でも葉でもない深さ 13親は 1
子は 6 だけ

葉深さ 26親は 3
子はいない

枝で結ばれた2つの節のうち、上を親、下を子と呼びます。節2 は、節1 から見れば子で、節4 から見れば親です。木の言葉は、あと3つです。

言葉	意味
根（ね）	親のない節。いちばん上に1つだけあります。図では節1
葉（は）	子のない節。図では節4・節5・節6
深さ	根からその節まで、枝を何本たどるか。節1 は 0、節2 と節3 は 1、節4〜節6 は 2

2分木 ── 子は2つまで。左と右を区別する

どの節も子が2つ以下の木を、2分木といいます。上の木は、節1 と節2 の子が2つ、節3 の子が1つ、節4〜節6 の子が0なので、2分木です。

2分木では、2つの子を左の子・右の子と呼び分けます。節1 なら、左の子が節2、右の子が節3 です。子が1つだけの節では、その子を左右どちらとするかを出題が決めます。上の木では、節3 のただ1つの子（節6）を左の子としました。

本物もこう書かれる

（基本情報技術者試験科目B サンプル問題問9 の図の注記）

注記2　子の節が一つの場合は，左の子の節とする。

2分木を配列で表す ── tree[n] は、節 n の子の番号

丸と線の図は、そのままではプログラムで扱えません。そこで、節ごとに「子の節番号」を書き並べて配列にします。上の木なら、こうなります。

大域: 整数型配列の配列: tree ← {{2, 3}, {4, 5}, {6}, {}, {}, {}}

tree は、要素の1つ1つが配列になっている配列です。tree の n 番目の要素 tree[n] に、節 n の子の節番号が、左の子・右の子の順に入っています。子のない節のところは {}（要素数0の配列）です。大域: は、どの手続からもこの配列を使える、という印です。

配列 tree と、図の木は同じもの

点線の箱＝中身が {}（要素数0の配列）＝葉　／　色の付いた箱＝子の番号が入っている

プログラムの中 ── 配列 tree（要素が6つ）

1{2, 3}

2{4, 5}

3{6}

4{}

5{}

6{}

枡の上の数字が要素番号で、そのまま節番号です。3番目の枡 {6} は「節3 の子は節6 の1つ」、4番目の枡 {} は「節4 に子はいない」。

図に戻すと ── 箱の太字が、その節の tree[n]

節1tree[1]{2, 3}左の子は 2
右の子は 3

節2tree[2]{4, 5}左の子は 4
右の子は 5

節4tree[4]{}子はいない

節5tree[5]{}子はいない

節3tree[3]{6}左の子は 6
右の子はいない

節6tree[6]{}子はいない

木を扱うプログラムは、この配列から次の3つを読み取ります。

書き方	読み取れること
`tree[n]の要素数`	節 n の子の数。0 なら、節 n は葉です。`tree[3]の要素数` は 1、`tree[4]の要素数` は 0
`tree[n][1]`	節 n の左の子の節番号。`tree[1][1]` は 2
`tree[n][2]`	節 n の右の子の節番号。`tree[1][2]` は 3。子が2つの節にだけあります（`tree[3]` は {6} で要素が1つなので、`tree[3][2]` はありません）

tree[1][2] のように [ ] が2つ続くときは、左から順に読みます。tree[1] が {2, 3}、その2番目なので 3 です。

本物もこう書かれる

（基本情報技術者試験科目B サンプル問題問9）

配列tree の要素は，対応する節の子の節番号を，左の子，右の子の順に格納した配列である。

14個の節をもつ2分木を、上と同じ持ち方で配列 tree にした出題です（サンプル問題問9の解説）。

配列だけを見て、根から葉まで降りる

図を見ずに、配列 tree だけで木の上を親から子へ移ってみます。次の手続 goLeft は、根から始めて左の子へ、また左の子へと降りていき、通った節の番号を順に出力します。根の節番号 1 は、n ← 1 とプログラムに直接書いてあります。

大域: 整数型配列の配列: tree ← {{2, 3}, {4, 5}, {6}, {}, {}, {}}

○goLeft()
  整数型: n ← 1
  while (tree[n]の要素数 が 0 と等しくない)
    nを出力
    n ← tree[n][1]
  endwhile
  nを出力

当サイトで作った例です。

goLeft を呼び出すと、1，2，4 の順に出力されます。

n は、いまいる節の番号です。while の条件は「節 n に子がいるあいだ」。子がいれば、自分の番号を出力してから n ← tree[n][1] で n を左の子の番号に書き換えます。「子へ1つ降りる」は、プログラムでは「n に子の節番号を入れる」と書かれます。

子が1つだけの節でも、その子は tree[n] の1番目に入っています。だから、子がいるかぎり tree[n][1] で必ず降りられます。

goLeft を1行ずつ動かす

当サイトオリジナルの例題

ループ開始前

大域の配列 tree（n 番目が、節 n の子の番号）

▲ いま読んでいる▲ いま書いた

いま計算していること

まだ計算していません

変数の状態

トレース表（進めると1行ずつ積み上がります）

配列から子の数と子の番号の2つを読むだけで、根から葉まで降りられました。降りた回数は2回で、着いた節4 の深さ 2 と同じです。右の子 tree[n][2] も使って、すべての節を順にたどるのが A12 木の巡回です。

次に読む

A12	木の巡回 ─ 先行順・中間順・後行順
問9	サンプル問題問9の解説 ─ 配列 tree で持った2分木をたどる
問15	サンプル問題問15の解説 ─ 根・子・葉の言葉だけで読む木
目次	基本情報技術者試験科目B 攻略ガイド