チャレンジ課題 C2 木構造の探索

名前付きノードからなる木構造を表すクラスTreeを作り、以下の木構造を再現せよ。

また、この木を深さ優先探索(DFS: depth first search)、幅優先探索(BFS: breadth first search)で探索し、見つかった順に画面にノード名を表示するプログラムを書け。

A B C D E F G H

A B G C E F H D

木構造は、２分木を使うと簡単に表現できる。また、DFS, BFSも再帰を使うと綺麗に書ける。

２分木とは、各ノードは高々２つの子ノードしか持たないデータ構造である。

2分木の構造は、一般の木構造（任意の数の子ノードを持つ）を表現するのにも使える。2分木のノードの左の子をfirstChild, 右の子をnextSiblingと考えると、一般の木は2分木で以下の図のように表現できる。