二分木(Binary Tree)

各ノードの子供の数が2以下である木構造のこと。 また、各ノードが「葉であるか、次数が2（子供が2つ）」である木を全二分木(full binary tree), すべての葉が同じ深さである二分木を完全二分木(perfect binary tree) という。

図1. 二分木の例（全二分木でも完全二分木でもない普通の二分木）

走査法(tree traversal)

1.深さ優先探索(depth-first search, DFS)

根から始まり、葉に行きつくまで掘り下げて探索する。葉に行きつくと、最も近くの探索の終わっていないノードまでバックトラックする。バックトラック後は、そのノードに再帰的に深さ優先探索を行う。

DFSには次の3つがある。

1.1 前順、行きがけ順（preorder）

　根 → 左の部分木 → 右の部分木　の順で走査する。
　図1の例では、A, B, D, H, E, I, J, C, F, G, K

1.2 間順、通りがけ順（inorder）

　左の部分木 → 根 → 右の部分木　の順で走査する。
　図1の例では、H, D, B I, E, J, A, F, C, K, G

1.3 後順、帰りがけ順（postorder)

　左の部分木 → 右の部分木 → 根　の順で走査する。
　図1の例では、H, D, I, J, E, B, F, K, G, C, A

2. 幅優先探索(breadth-first search, BFS)

「深さ」のレベルが同じノードを浅い方から順に走査する。