木の登り方 [GRE CS]

GREサブジェクトテストCS分野問題第7問。2分木(binary tree)に関する問題。

まず、「木(tree)」とは何か、ってことから説明しようかな。あ、でも、その前に、どういうのが木なのか？ってのを実際に例示しといた方が話が早いか。つわけで、どん。

ま、これ見てもらえれば直感的に、「あ、なるほど」だとは思うんだけど、一応くだくだしく言うと、

1. 「根(root)」と呼ばれる点が1つある（この図だと、1が根）
2. ある点と点が結ばれているとき、根に近い方を「親(parent)」、遠い方を「子(child)」と呼ぶ（たとえば、上の図で1と7は1が親で7が子）。
3. 根は親を持たない。
4. 子は1つの親しか持たない。
5. 子のない点を「葉(leaf)」と呼ぶ（たとえば、2とか5とかが葉）。

って感じ。

で、2分木ってのは、上記の木の定義に「各点について、たかだか最大2つの子しか持たない」という制約を加えたもの。上の図は、もうまさに2分木。

さて、こうした2分木ってのは、その各点にデータが保持されていて、それを順々に取り出す、って使われ方をしたりするんだけど、そういう「順々に」各点を訪れるやり方ってのがまあ色々あって、ここでは「プレオーダ・トラヴァーサルpreorder traversal」、「インオーダ・トラヴァーサルinorder traversal」「ポストオーダ・トラヴァーサルpostorder traversal」というのを説明。

ほんじゃ、ちょっと次のコードを見てもらいましょ。

visit(node)

    /* preorder */
if node.left  != null then visit(node.left)
/* inorder */
if node.right != null then visit(node.right)
/* postorder */

で、このコードの/* preorder */の部分にprint node.valueを代入したものがプレオーダ・トラヴァーサルのアルゴリズム、/* inorder */の部分に……って感じなんだけど、うーん、これだけじゃよう分からんだろうから、上の図を例に、コードを追ってみよう。


プレオーダ・トラヴァーサルの場合

1. 最初のvisit(node)で根を訪れる。
2. 次に、/* preorder */にはprint node.value代入されているわけだから、その根の値、つまり1を出力(print)する。
3. 3行目ではまず、今いる点の左に子がいるかどうかを検査する(if node.left != null)。子がいる場合、その子を「根」として、再帰的にvisit(node)を実行する（上記の図の場合、根に子7がいるわけだから、visit(7)が実行される）。
4. visit(7)では、まず7が出力され、次に7の左に子がいるかどうか検査される。この場合、7には子2がいるから、visite(2)が実行される。
5. visit(2)では、まず2が出力され、2の左に子がいるかどうか検査されるが、この場合いないので、次のラインで2の右に子がいるかどうか検査される。2には右にも子がいないので、このvisit(2)ルーチンはここで終了。
6. さて、visit(2)は工程4のif node.left != null then visit(node.left)で呼び出されていたのだから、その次、つまりvisit(7)のif node.right != null then visit(node.right)に処理が戻る。つまり、7の右に子がいるかどうかが検査され、子がいる場合、その子を元にvisit(node)が呼び出される。上図の場合、7の右には子6がいるから、visit(6)が呼び出される。
7. ……

という具合に、結局上図の場合、このコードの出力は、「1,7,2,6,5,11,3,9,4」となる。

そして、インオーダの場合は「2,7,5,6,11,1,3,4,9」、ポストオーダの場合は「2,5,11,6,7,4,9,3,1」って具合。

まあ、話を聞いただけじゃ分かんないだろうから（って、お前の説明が下手くそなんじゃ！と言われれば、何とも言い返せないけど）、是非上記のコードの挙動を、紙に書き下ろしてみたりしてください。そうすりゃ、何となく分かってくる、と思います。