二分木の in-order 走査
二分木の in-order 走査
このレッスンで分かること
- 二分木 (binary tree) は、各ノードが最大 2 つの子 (左と右) を持つ階層構造です
- この章ではまず 走査 (traversal) を扱います
- 本コースでは、ツリーを「BFS (幅優先) 順に並べた配列」で扱います
二分木の in-order 走査 とは
二分木を配列表現で受け取り、in-order (左 → 根 → 右) で訪問した値の配列を返す関数を実装する。
二分木 (binary tree) は、各ノードが最大 2 つの子 (左と右) を持つ階層構造です。連結リストが「一直線」だったのに対し、二分木は「枝分かれするデータ構造」と思ってください。コンパイラの構文木、ファイルシステム、データベースのインデックスなど、現実のシステム設計では至るところに現れます。
この章ではまず 走査 (traversal) を扱います。走査とは「木のすべてのノードを 1 度ずつ訪問して値を順番に取り出す」操作のことです。for や while で配列を回す感覚を、ツリーに拡張したものと思えば OK です。
二分木の走査は、配列の for ループ を 再帰 に置き換えた版だと考えると馴染みやすい。
配列で二分木を表現する
本コースでは、ツリーを「BFS (幅優先) 順に並べた配列」で扱います。欠損ノードは null (Python では None) で穴埋めします。例えば [1, 2, 3, null, 4] は次の木に対応します。
- index
0の1が root - index
1の2は root の 左の子、index2の3は 右の子 - index
3は 欠損、index4の4は2の右の子
インデックス i のノードに対し、左の子は 2 * i + 1、右の子は 2 * i + 2 という対応で、配列要素が null または範囲外なら子は存在しません。これは 完全二分木の配列表現 と呼ばれる古典的な手法で、heap (ヒープ) でも使われています。
配列で表現すると、ポインタを書かずに木を扱える。ただし疎な木では配列がスカスカになる弱点もある。
in-order とは
走査には主に 3 種類あります。
- in-order 左 → 根 → 右
- pre-order 根 → 左 → 右
- post-order 左 → 右 → 根
このレッスンでは in-order を扱います。[1, 2, 3, null, 4] の場合、左部分木 (2 を根とする) を in-order で回ると [2, 4]、続いて根の 1、最後に右部分木の 3。結果は [2, 4, 1, 3] です。
in-order が便利なのは、二分探索木 (BST) を in-order で走査すると値が昇順に並ぶ という性質があるからです。第 3 章の BST で再登場するので、ここで体で覚えておきましょう。
in-order = 左 → 根 → 右。BST では昇順 に出てくる性質をぜひ覚えておこう。
Python での実装例
Python
def inorder(tree):
result = []
def visit(i):
if i >= len(tree) or tree[i] is None:
return
visit(2 * i + 1)
result.append(tree[i])
visit(2 * i + 2)
visit(0)
return resultvisit(i) は「index i のノードを根とする部分木を in-order で走査して result に追加する」関数です。visit(2*i+1) で左部分木へ、result.append で根を訪問、最後に visit(2*i+2) で右部分木へ。再帰の 基底ケース は「範囲外」または「None」のときです。
JavaScript での実装例
JavaScript
function inorder(tree) {
const result = [];
const visit = (i) => {
if (i >= tree.length || tree[i] === null) return;
visit(2 * i + 1);
result.push(tree[i]);
visit(2 * i + 2);
};
visit(0);
return result;
}ロジックはまったく同じです。null 判定だけ気をつけてください。JS では tree[i] == null と書くと undefined も拾えますが、明示的に === null の方が事故が減ります。
よくある間違い
1 つ目は 範囲外チェック忘れ。i >= tree.length を入れないと、葉のさらに先で IndexError が出ます。2 つ目は null と 0 の取り違え。if not tree[i]: と書くと値 0 のノードを欠損扱いしてしまいます。3 つ目は 左と右の順序を逆にしてしまう。in-order は 左 → 根 → 右、テスト結果が逆順 (右 → 根 → 左) になっていたら左右逆です。
やってみよう
[1, null, 2, null, null, 3](root に右の子だけがある) を手で in-order してみる。[1, 3, 2]になる。- 完全二分木
[1, 2, 3, 4, 5, 6, 7]を in-order すると[4, 2, 5, 1, 6, 3, 7]。 - 反復版 (stack で
iterative inorder) の書き方を調べてみる。再帰の深さ制限を回避できます。
よくある質問
Q. BST はなぜ高速ですか？
A. 平衡している場合、検索・挿入・削除がいずれも O(log n) です。各ノードで「左<自分<右」を満たすため、半分ずつ探索範囲が絞れます。ただし偏ると O(n) に劣化するため、実用では赤黒木・AVL 木のような自動平衡化された実装を使います。
Q. in-order 走査で何が得られますか？
A. BST を in-order で巡回するとソート済みの順序で要素が得られます。これが BST と他のツリーの大きな違いで、ソート済みデータの逐次処理に向いています。範囲検索（lo 以上 hi 以下）も簡潔に書けます。
Q. BST に重複値を入れるとどうなりますか？
A. 実装次第ですが、通常は「等しい場合は右に入れる」「カウントを持って同じノードに記録する」のいずれかです。重複が多いユースケースなら TreeMap<Key, Integer> のように出現数を値に持たせる方が探索効率が上がります。
次のレッスン
次は 二分木の pre-order 走査 で、二分木を配列表現で受け取り、pre-order (根 → 左 → 右) で訪問した値の配列を返す関数を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- in-order 走査 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. in-order 走査 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- tree は BFS 順の配列で、null (Python では None) は欠損ノードを表す
- 再帰または反復で left -> root -> right の順に訪問する
- 戻り値は訪問順の値の配列 (List)。null は結果に含めない
入出力例
test-cases.txt
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]