7.2 二分木の走査¶
物理的構造の観点から見ると、木は連結リストに基づくデータ構造です。したがって、その走査方法はポインタを通してノードに一つずつアクセスすることを含みます。しかし、木は非線形データ構造であるため、木の走査は連結リストの走査よりも複雑で、検索アルゴリズムの支援が必要です。
二分木の一般的な走査方法には、レベル順走査、前順走査、中順走査、後順走査があります。
7.2.1 レベル順走査¶
下図に示すように、レベル順走査は二分木を上から下へ、層ごとに走査します。各レベル内では、左から右へノードを訪問します。
レベル順走査は本質的に幅優先走査の一種で、幅優先探索（BFS）とも呼ばれ、「周囲に向かって外向きに拡張する」層ごとの走査方法を体現しています。
図 7-9 二分木のレベル順走査
1. コード実装¶
幅優先走査は通常「キュー」の助けを借りて実装されます。キューは「先入れ先出し」の規則に従い、幅優先走査は「層ごとの進行」規則に従います。両者の基本的な考え方は一致しています。実装コードは以下の通りです：
binary_tree_bfs.py
def level_order(root: TreeNode | None) -> list[int]:
"""レベル順走査"""
# キューを初期化し、ルートノードを追加
queue: deque[TreeNode] = deque()
queue.append(root)
# 走査シーケンスを格納するリストを初期化
res = []
while queue:
node: TreeNode = queue.popleft() # キューからデキュー
res.append(node.val) # ノードの値を保存
if node.left is not None:
queue.append(node.left) # 左の子ノードをエンキュー
if node.right is not None:
queue.append(node.right) # 右の子ノードをエンキュー
return res
binary_tree_bfs.cpp
/* レベル順走査 */
vector<int> levelOrder(TreeNode *root) {
// キューを初期化、ルートノードを追加
queue<TreeNode *> queue;
queue.push(root);
// 走査順序を保存するリストを初期化
vector<int> vec;
while (!queue.empty()) {
TreeNode *node = queue.front();
queue.pop(); // キューからデキュー
vec.push_back(node->val); // ノード値を保存
if (node->left != nullptr)
queue.push(node->left); // 左の子ノードをエンキュー
if (node->right != nullptr)
queue.push(node->right); // 右の子ノードをエンキュー
}
return vec;
}
binary_tree_bfs.java
/* レベル順走査 */
List<Integer> levelOrder(TreeNode root) {
// キューを初期化し、根ノードを追加
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
// 走査順序を格納するリストを初期化
List<Integer> list = new ArrayList<>();
while (!queue.isEmpty()) {
TreeNode node = queue.poll(); // キューのデキュー
list.add(node.val); // ノードの値を保存
if (node.left != null)
queue.offer(node.left); // 左の子ノードをエンキュー
if (node.right != null)
queue.offer(node.right); // 右の子ノードをエンキュー
}
return list;
}
2. 計算量分析¶
- 時間計算量は\(O(n)\): すべてのノードが一度ずつ訪問され、\(O(n)\)の時間がかかります。ここで\(n\)はノード数です。
- 空間計算量は\(O(n)\): 最悪の場合、つまり完全二分木の場合、最下位レベルに走査する前に、キューは最大\((n + 1) / 2\)個のノードを同時に含むことができ、\(O(n)\)の空間を占有します。
7.2.2 前順、中順、後順走査¶
対応して、前順、中順、後順走査はすべて深度優先走査に属し、深度優先探索（DFS）とも呼ばれ、「まず最後まで進み、その後バックトラックして続行する」走査方法を体現しています。
下図は二分木に対して深度優先走査を実行する動作原理を示しています。深度優先走査は二分木全体を「歩き回る」ようなもので、各ノードで3つの位置に遭遇し、それらは前順、中順、後順走査に対応しています。
図 7-10 二分探索木の前順、中順、後順走査
1. コード実装¶
深度優先探索は通常再帰に基づいて実装されます：
binary_tree_dfs.py
def pre_order(root: TreeNode | None):
"""前順走査"""
if root is None:
return
# 訪問順序: ルートノード -> 左部分木 -> 右部分木
res.append(root.val)
pre_order(root=root.left)
pre_order(root=root.right)
def in_order(root: TreeNode | None):
"""中順走査"""
if root is None:
return
# 訪問順序: 左部分木 -> ルートノード -> 右部分木
in_order(root=root.left)
res.append(root.val)
in_order(root=root.right)
def post_order(root: TreeNode | None):
"""後順走査"""
if root is None:
return
# 訪問順序: 左部分木 -> 右部分木 -> ルートノード
post_order(root=root.left)
post_order(root=root.right)
res.append(root.val)
binary_tree_dfs.cpp
/* 前順走査 */
void preOrder(TreeNode *root) {
if (root == nullptr)
return;
// 訪問優先度：ルートノード -> 左部分木 -> 右部分木
vec.push_back(root->val);
preOrder(root->left);
preOrder(root->right);
}
/* 中順走査 */
void inOrder(TreeNode *root) {
if (root == nullptr)
return;
// 訪問優先度：左部分木 -> ルートノード -> 右部分木
inOrder(root->left);
vec.push_back(root->val);
inOrder(root->right);
}
/* 後順走査 */
void postOrder(TreeNode *root) {
if (root == nullptr)
return;
// 訪問優先度：左部分木 -> 右部分木 -> ルートノード
postOrder(root->left);
postOrder(root->right);
vec.push_back(root->val);
}
binary_tree_dfs.java
/* 前順走査 */
void preOrder(TreeNode root) {
if (root == null)
return;
// 訪問優先度: 根ノード -> 左部分木 -> 右部分木
list.add(root.val);
preOrder(root.left);
preOrder(root.right);
}
/* 中順走査 */
void inOrder(TreeNode root) {
if (root == null)
return;
// 訪問優先度: 左部分木 -> 根ノード -> 右部分木
inOrder(root.left);
list.add(root.val);
inOrder(root.right);
}
/* 後順走査 */
void postOrder(TreeNode root) {
if (root == null)
return;
// 訪問優先度: 左部分木 -> 右部分木 -> 根ノード
postOrder(root.left);
postOrder(root.right);
list.add(root.val);
}
Tip
深度優先探索は反復に基づいても実装できます。興味のある読者は自分で学習してください。
下図は二分木の前順走査の再帰プロセスを示しており、これは「再帰」と「復帰」という2つの反対の部分に分けることができます。
- 「再帰」は新しいメソッドを開始することを意味し、プログラムはこのプロセスで次のノードにアクセスします。
- 「復帰」は関数が戻ることを意味し、現在のノードが完全にアクセスされたことを示します。
図 7-11 前順走査の再帰プロセス
2. 計算量分析¶
- 時間計算量は\(O(n)\): すべてのノードが一度ずつ訪問され、\(O(n)\)の時間を使用します。
- 空間計算量は\(O(n)\): 最悪の場合、つまり木が連結リストに退化した場合、再帰の深さは\(n\)に達し、システムは\(O(n)\)のスタックフレーム空間を占有します。