レベルオーダートラバーサル Python

レベルオーダートラバーサル (Level Order Traversal) は、二分木（Binary Tree）を幅優先で探索するアルゴリズムです。

このアルゴリズムでは、木の各レベル（深さ）ごとにノードを左から右へ訪問していきます。

[探索する二分木]

1
2
3
4
5
    1
   / \
  2   3
 / \   \
4   5   6

Pythonを使って、レベルオーダートラバーサルのサンプルコードを説明します。

以下は、二分木のノードを表すクラスとレベルオーダートラバーサルを実行するコードの例です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class TreeNode:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None

def level_order_traversal(root):
    if not root:
        return []
    
    result = []  # レベルオーダートラバーサルの結果を格納するリスト
    queue = [root]  # キューを使用してノードを管理
    
    while queue:
        current = queue.pop(0)  # キューの先頭からノードを取り出す
        result.append(current.val)  # ノードの値を結果に追加
        
        if current.left:
            queue.append(current.left)  # 左の子ノードをキューに追加
        
        if current.right:
            queue.append(current.right)  # 右の子ノードをキューに追加
    
    return result

# 二分木の例を作成
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

# レベルオーダートラバーサルを実行
result = level_order_traversal(root)

# 結果を表示
print("レベルオーダートラバーサル:", result)

このコードは、二分木をレベルオーダートラバーサルで探索する方法を示しています。

TreeNode クラスは、二分木のノードを表すために使用されます。

level_order_traversal 関数は、ルートノードから始めて幅優先でノードを訪問し、その値を result リストに追加します。

上記の例では、以下の二分木を作成し、そのレベルオーダートラバーサルの結果を表示します。

[実行結果]

1
レベルオーダートラバーサル: [1, 2, 3, 4, 5, 6]

このように、レベルオーダートラバーサルは、各レベルごとにノードを訪問するため、木の構造を保ちつつノードを効率的に探索するのに役立ちます。

ソースコード解説

このソースコードは、二分木（Binary Tree）を使って「レベルオーダートラバーサル」を行うPythonプログラムです。

レベルオーダートラバーサルは、二分木内のノードを幅優先で探索し、各レベルごとにノードの値を表示します。

以下に、ソースコードの詳細な説明を提供します。

1. TreeNode クラス:

  • このクラスは、二分木のノードを表すために使用されます。
    各ノードには値 (val)、左の子ノード (left)、右の子ノード (right) が含まれます。

2. level_order_traversal 関数:

  • この関数は、レベルオーダートラバーサルを実行するためのメイン関数です。
    引数としてルートノード (root) を受け取ります。
  • 最初に、ルートノードが存在しない場合、空のリストを返します。
  • result リストは、レベルオーダートラバーサルの結果を格納するためのリストです。
    初期化されています。
  • queue リストは、ノードを管理するためにキュー（FIFO）データ構造として使用されます。
    最初にルートノードをキューに追加します。
  • while ループを使用して、キューが空になるまでノードを処理します。
    • queue.pop(0) でキューの先頭からノードを取り出します。
    • 取り出したノードの値 (current.val) を result リストに追加します。
    • 左の子ノードが存在する場合、そのノードをキューに追加します。
    • 右の子ノードが存在する場合、そのノードもキューに追加します。
  • すべてのノードが処理された後、result リストを返します。

3. 二分木の例の作成:

  • サンプルの二分木を作成し、各ノードの値を設定しています。

4. レベルオーダートラバーサルの実行:

  • level_order_traversal 関数を呼び出し、サンプルの二分木を渡してレベルオーダートラバーサルを実行します。

5. 結果の表示:

  • レベルオーダートラバーサルの結果が result リストに格納されているので、それを表示します。

このプログラムは、与えられた二分木内のノードを幅優先で探索し、各レベルごとにノードの値を表示します。