二分木の in-order 走査
連結リストは 1 本道でした。ここからは、各ノードが左と右の 2 つの行き先を持つ二分木を扱います。分かれ道が 1 つ増えただけで、変数を 1 つ進めていく書き方が通用しなくなります。
分かれ道に来るたび、片方を待たせることになる
左へ行けば右が残り、その右へ行けばまた分かれ道が待っています。「あとで戻ってくる場所」が次々に積み上がるので、今どこにいるかを指す変数を 1 つ持つだけでは足りません。
そこで再帰を使います。再帰は 2 つの部品でできています。1 つは、これ以上潜らないと決める行き止まりの条件。もう 1 つは、自分より小さい同じ形の問題を子に投げ、返ってきたものを組み立てる本体です。行き止まりを書き忘れると、無いノードにさらに潜って落ちます。この 2 つがそろっているかを、書くたびに確かめてください。
このコースでは木を、上の段から左詰めで並べた配列として受け取ります。番号 i のノードの子は、次の場所にいます。
Python
left = 2 * i + 1
right = 2 * i + 2たとえば [1, 2, 3, None, 4] なら、1 が根、2 と 3 がその子、2 の左は空で右が 4 です。番号 3 の場所が空いているのは、位置で木の形を決めているからで、片側だけ伸びた木ほど配列に穴が増えます。
配列の外にはみ出したか、その場所が空なら、そこが行き止まりです。判定は「空かどうか」で書いてください。真偽で書くと、値が 0 のノードまで空として捨ててしまいます。
左を片付けてから、自分を出す
左、自分、右。この順で見るのが in-order です。数式を木にしたものを人が読む式へ戻す処理が、ちょうどこの順になります。
Python
def to_infix(node):
if node is None:
return ""
if node.left is None and node.right is None:
return str(node.value)
return "(" + to_infix(node.left) + node.value + to_infix(node.right) + ")"演算子を持つノードは、左の式を出し、自分の記号を挟み、右の式を出します。掛け算と足し算が混ざった木から (a * (b + c)) のような見慣れた形が戻ってきます。自分を左と右の間に置く、という順序がそのまま文字列の並びになっているのが分かります。
探索木なら、勝手に昇順で出てくる
in-order がよく使われる理由は別のところにあります。左の子には自分より小さい値、右の子には大きい値だけを置く、という決まりを守った木があります。その木を左、自分、右の順に見ると、出てくる値は必ず小さい順に並びます。
理由は単純です。自分を出す時点で、自分より小さいものは左側で出し終えています。そしてまだ出していないものは、全部自分より大きい。だから並べ替えを 1 回もせずに、歩くだけで整列した列が手に入ります。この性質のおかげで、そういう木は「並べ替え済みの入れ物」として使えます。
要件
- tree は BFS 順の配列で、null (Python では None) は欠損ノードを表す
- 再帰または反復で left -> root -> right の順に訪問する
- 戻り値は訪問順の値の配列 (List)。null は結果に含めない
入出力例
inorder([1,2,3,null,4]) → [2,4,1,3]
inorder([1]) → [1]
inorder([1,2,3]) → [2,1,3]
inorder([1,null,2,null,null,null,3]) → [1,2,3]
inorder([1,2,3,4,5,6,7]) → [4,2,5,1,6,3,7]
inorder([5,3,8,1,4,null,9]) → [1,3,4,5,8,9]ヒント
