木走査の擬似言語

科目B頻出の木構造の走査。前順・中順・後順の3種の走査と、二分探索木の検索を擬似言語で理解します。

日野 こむぎ

木の走査って、どういう順番で見るの?

藤森 さやか 先生

3種類あるの。
前順走査?
(preorder: 親→左→右)、中順走査?
(inorder: 左→親→右)、後順走査?
(postorder: 左→右→親)。

青木 澪

中順走査 (inorder) は二分探索木に対して使うとソート済みの順序で要素が取れる便利な性質があるの。

/* 中順走査 (inorder) - 左→親→右 */
○ 手続: inorder(ノード型: node)
  if (node ≠ null)
    inorder(node.left)
    print(node.value)
    inorder(node.right)
  endif

桃井 すみれ

再帰呼び出しがきれいですぅ♪

青木 澪

そう、木の走査は再帰で書くのが最も自然。
前順は print の位置を最初に、後順は最後に持ってくるだけ。

藤森 さやか 先生

二分探索木 (BST) の検索は中順走査と関連する応用例:

○ 手続: searchBST(ノード型: node, 整数型: key)
  if (node = null)
    return null
  endif
  if (key = node.value)
    return node
  elseif (key < node.value)
    return searchBST(node.left, key)
  else
    return searchBST(node.right, key)
  endif

青木 澪

BSTの検索は再帰で書くととてもシンプル。
「key より小なら左、大なら右」というルールに従って降りていくだけ。
計算量は平衡木なら O(log n)。

日野 こむぎ

次の例題、見てみたいな!

青木 澪

中順走査の出力順序を問う問題が頻出なの。
下の木を中順走査するとどんな順序になるかしら?

藤森 さやか 先生

下の木構造を考えてみて: 根=4、左の子=2 (その左の子=1, 右の子=3)、右の子=6 (左の子=5, 右の子=7)。
中順走査の出力順は?

日野 こむぎ

左→親→右の順だから……1 → 2 → 3 → 4 → 5 → 6 → 7、ソート順になるね!

藤森 さやか 先生

正解!
これが二分探索木に対する中順走査の大事な特徴ね。