読者です 読者をやめる 読者になる 読者になる

A little bit of everything

情報系大学院生の備忘録

二分木(Binary Tree)

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

f:id:yuukiyg:20160116201434p:plain 図1. 二分木の例(全二分木でも完全二分木でもない普通の二分木)

走査法(tree traversal)

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

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

f:id:yuukiyg:20160116201619j:plain
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)

「深さ」のレベルが同じノードを浅い方から順に走査する。
f:id:yuukiyg:20160116201858j:plain