２分木探索（通りがけ順）をPythonで表現してみる

木構造の表現方法

木構造を２次元配列で表現しています。
Nodes[Node[Left, Right, Data]]

• Left , Right : 連結するNodeのインデックス
• Data : Nodeに含まれるデータ

node_data = [
    [1,    2,    10],
    [3,    4,     5],
    [5,    None, 12],
    [None, None,  2],
    [6,    7,     8],
    [None, None, 11],
    [None, None,  6],
    [None, None,  9]
]

木構造のイラスト

[インデックス　：　データ]

プログラム

NodeClass

from typing import Any, List, Optional

class Node:
    """二分木のノードを表現するクラス"""
    
    def __init__(self, left: Optional[int] = None, right: Optional[int] = None, data: Any = None):
        self.left = left
        self.right = right
        self.data = data

BinaryTreeClass

class BinaryTree:
    """二分木を表現するクラス"""
    
    def __init__(self, nodes_data: List[List[Any]]):
        self.nodes = [Node(*node_data) for node_data in nodes_data]

    def in_order_traversal(self, index: int = 0) -> None:
        """
        二分木を通りがけ順（左、ルート、右）で巡回する。
        
        :param index: 巡回中の現在のノードのインデックス。
        """
        if index is not None:
            node = self.nodes[index]
            self.in_order_traversal(node.left)
            print(node.data)
            self.in_order_traversal(node.right)

実行ファイル

# 与えられたデータで二分木を初期化
node_data = [
    [1,    2,    10],
    [3,    4,     5],
    [5,    None, 12],
    [None, None,  2],
    [6,    7,     8],
    [None, None, 11],
    [None, None,  6],
    [None, None,  9]
]

# BinaryTreeオブジェクトを作成し、通りがけ順で巡回する
binary_tree = BinaryTree(node_data)
binary_tree.in_order_traversal()

実行結果のトレース表

このプログラムの実行結果のトレース表は以下のとおりです。

ステップ	関数/メソッド	インデックス	ノードデータ	操作内容
1	in_order_traversal	0	10	左子ノードへ移動
2	in_order_traversal	1	5	左子ノードへ移動
3	in_order_traversal	3	2	左子ノードへ移動（None）
4	in_order_traversal	3	2	データを表示（2）
5	in_order_traversal	3	2	右子ノードへ移動（None）
6	in_order_traversal	1	5	データを表示（5）
7	in_order_traversal	1	5	右子ノードへ移動
8	in_order_traversal	4	8	左子ノードへ移動
9	in_order_traversal	6	6	左子ノードへ移動（None）
10	in_order_traversal	6	6	データを表示（6）
11	in_order_traversal	6	6	右子ノードへ移動（None）
12	in_order_traversal	4	8	データを表示（8）
13	in_order_traversal	4	8	右子ノードへ移動
14	in_order_traversal	7	9	左子ノードへ移動（None）
15	in_order_traversal	7	9	データを表示（9）
16	in_order_traversal	7	9	右子ノードへ移動（None）
17	in_order_traversal	0	10	データを表示（10）
18	in_order_traversal	0	10	右子ノードへ移動
19	in_order_traversal	2	12	左子ノードへ移動
20	in_order_traversal	5	11	左子ノードへ移動（None）
21	in_order_traversal	5	11	データを表示（11）
22	in_order_traversal	5	11	右子ノードへ移動（None）
23	in_order_traversal	2	12	データを表示（12）
24	in_order_traversal	2	12	右子ノードへ移動（None）

プログラム全体の実行結果は以下のようになります。

実行結果

二分探索木を通りがけ順に巡回
2
5
6
8
9
10
11
12