二分木の pre-order 走査
二分木の pre-order 走査
このレッスンで分かること
- 同じ木を 3 種類の走査で回すと違う順が出る
- pre-order は実用上、次のような場面で重宝します
- In-order は BST で昇順に出すのに使い、pre-order は 構造のコピー に強い、というのが大まかな住み分けです
二分木の pre-order 走査 とは
二分木を配列表現で受け取り、pre-order (根 → 左 → 右) で訪問した値の配列を返す関数を実装する。
前のレッスンで in-order (左 → 根 → 右) を実装しました。今度は pre-order (根 → 左 → 右) を扱います。違いは「根を訪問するタイミング」だけです。木の構造を理解する上で、3 つの走査の違いを体で覚えるのが重要です。
pre-order = 根 → 左 → 右。根を最初に出す ので、木のコピーやシリアライズに向いている。
pre-order の使いどころ
pre-order は実用上、次のような場面で重宝します。
- 木の コピー (新しいノードを上から作る必要があるので、根を先に処理したい)
- 木の シリアライズ (
[1, 2, null, null, 3]のような形式で書き出す) - 数式の 前置記法 (
+ a bのような表記) - ファイルシステムの ディレクトリ出力 (親フォルダ名 → 子フォルダ名 の順)
In-order は BST で昇順に出すのに使い、pre-order は 構造のコピー に強い、というのが大まかな住み分けです。
例で理解する
[1, 2, 3, null, 4] の木を pre-order で走査するとどうなるでしょうか。
手順は次のとおりです。
- 根
1を訪問 - 左部分木へ降りる → 根
2を訪問 → 左null(skip) → 右4を訪問 - 右部分木へ降りる → 根
3を訪問 (子なし)
結果は [1, 2, 4, 3] となります。1 が最初に出ているのが in-order との大きな違いです。
同じ木を 3 種類の走査で回すと違う順が出る。順を見るだけで「どの走査か」判別できるようになると一人前。
Python での実装
Python
def preorder(tree):
result = []
def visit(i):
if i >= len(tree) or tree[i] is None:
return
result.append(tree[i])
visit(2 * i + 1)
visit(2 * i + 2)
visit(0)
return resultin-order との違いは result.append の位置 だけです。最初に呼ぶと pre-order、左の後に呼ぶと in-order、右の後に呼ぶと post-order になります。再帰呼び出しの「外側で根を処理」しているので 再帰下降パーサー の parse_expression のような構造とも相性が良いです。
JavaScript での実装
JavaScript
function preorder(tree) {
const result = [];
const visit = (i) => {
if (i >= tree.length || tree[i] === null) return;
result.push(tree[i]);
visit(2 * i + 1);
visit(2 * i + 2);
};
visit(0);
return result;
}反復版もある
再帰の深さを避けたい場合は スタックを使った反復版 がよく出てきます。in-order よりも実装がシンプルです。
Python
def preorder_iter(tree):
if not tree or tree[0] is None:
return []
result, stack = [], [0]
while stack:
i = stack.pop()
if i >= len(tree) or tree[i] is None:
continue
result.append(tree[i])
# 右を先に push (LIFO なので最後に右が処理される)
stack.append(2 * i + 2)
stack.append(2 * i + 1)
return resultstack.pop() は LIFO なので 右を先に push して 左を後に push することで、左が先に取り出されます。これは面接でもよく聞かれる定番テクニックです。
よくある間違い
1 つ目は 走査順を間違える。visit(2*i+1) (左) の前に result.append を置かないと、それは in-order や post-order になってしまいます。2 つ目は 反復版の左右の push 順を逆にする こと。stack は LIFO なので「最後に取り出したい方を先に push」が鉄則です。3 つ目は null を結果に入れてしまう。null は出力しないのが pre-order の暗黙の約束です。
やってみよう
[1, 2, 3]を pre-order で走査して、結果が[1, 2, 3]になることを確認する (たまたま BFS 順と一致する)。[1, null, 2, null, null, null, 3](右に偏った木) を pre-order すると[1, 2, 3]になる。- 反復版の解答も書いてみて、再帰版と結果が一致することを確認する。
3 種類の走査は 根を出すタイミングが違うだけ。これに気づくと木の問題が一気に楽になる。
よくある質問
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> のように出現数を値に持たせる方が探索効率が上がります。
次のレッスン
次は 二分木の post-order 走査 で、二分木を配列表現で受け取り、post-order (左 → 右 → 根) で訪問した値の配列を返す関数を実装することを学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- pre-order 走査 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. pre-order 走査 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- tree は BFS 順の配列で、null (Python では None) は欠損ノードを表す
- 再帰または反復で root -> left -> right の順に訪問する
- 戻り値は訪問順の値の配列。null は結果に含めない
入出力例
test-cases.txt
preorder([1,2,3,null,4]) → [1,2,4,3]
preorder([1]) → [1]
preorder([1,2,3]) → [1,2,3]
preorder([1,null,2,null,null,null,3]) → [1,2,3]
preorder([1,2,3,4,5,6,7]) → [1,2,4,5,3,6,7]
preorder([5,3,8,1,4,null,9]) → [5,3,1,4,8,9]