まず、え〜と、私についてですが、こちらをご覧ください。
本題に入りましょう。
1次元配列で、木構造を表わす方法を考えて見ましょう。
その前に、木構造とはどういうものだったかを確認しましょう:
この木構造では、1つの要素を、1つの要素だけとして描いていますが、配列で木構造を表わそうとする場合、そうはいきません。というのも、その要素が持つ値を保持する部分が必要ですし、その要素の子となる要素を示すための部分も必要です。
先の「配列、リスト、木構造」では、一番上の要素から、そのすぐ下の要素へはいくつもの親子関係がありました。ですが、ここでは、1つの親は、2つ以下の子しか持てないとします。すると、1つの要素として描かれていたものが実際にはどういうものである必要があるかがわかり、それは次のようになります:
もっとも、ここでは1次元の配列を考えていますから、実際には1次元の配列の中に、次のように3つ組で並んでいるとしましょう:
さて、これでどうやって木構造を表わすかというと、次のようになります (読み易いように、適宜スペースを開けたり、改行しています):
[ ROOT, 3,6,
"あ", 9, 12, "い", 15, 18,
"う", φ, φ, "え", φ, φ,
"お", φ, φ, "か", φ, φ]
ここでの“ROOT”は木の起点であることを示す記号であり、“φ”はそこにはどんな値も入っていないことを示す記号とします。 “ROOT” は、他のなにかであっても−−たとえば “ん” というデータでも−−かまいません。また、基本的に配列では、一つの型の要素しか取れず、この例のように “あ” というような文字、あるいは文字列と、9というような数値が混在することはありません。ですが、ここではそれを無視することとします。もっとも、レコードを要素にした配列 (レコードの配列)という方法もあります。
このように1次元配列の形として書いただけではわかりにくいかもしれないので、これを図示しましょう:
この図は、たとえば「0: ROOT」というような書き方がされていますが、この「0:」にあたる部分は、上の配列での要素の番号です。
このように、一次元配列でも木構造は描けることがわかります。
取り得る木構造の形が決まっているなら−−つまり子は常に2個以下など−−、これでも案外不便はありません。慣れは必要かもしれませんが。
なお、この木構造の場合、親から子へは記録されている値から辿れますが、子から親へは辿れません。子から親へも直接辿れるようにするには、現在3つ組であるところにもう一つ要素を付け加え、そこに親の要素の番号を記録すれば、それも可能になります。このあたりは再帰やバックトラックなどの方法の方がいいということもあるので、必ずしも4つ組にする必要はありません。
このような木構造を、本企画で行なう講習に参加していただく児童・生徒に要求するかというと、別段要求はしません。児童・生徒がこのようなものを組み上げられるならそれでかまいませんし、別の方法があるならそれでもかまいません。たとえば、1次元配列を3つ使い、同様の木構造を表わすこともできるでしょう。あるいは、課題を解くのに用いるデータ構造が、そもそも木構造でなくてもかまいません。
追記 (Aug 07, 2017, 15:45JST):
Gigazineにですが、「6歳の子ども向け「プログラミング教室」を実際にやってわかった成功させる方法」という記事がアップされています。
6歳児ですから、本企画の対象とする児童よりも低学年ではあります。ですが、この知見も参考にしていきたいと思います。