Python で木データ構造を実装する

木構造では、辺でつながったノードとしてデータを整理します。各辺は親ノードと子ノードを結び、子ノードを持たないノードは葉と呼ばれます。木には二分木、三分木、二分探索木、AVL木などがあります。二分木では、各ノードが持てる子は最大2つです。このガイドでは、独自の Node クラスで小さな二分木を作り、深さ優先の3種類の順序で走査する方法と、ライブラリ anytree を使う方法を紹介します。

Pythonでツリー構造をゼロから実装する

シンプルな二分木のノードには、値を格納する場所と、2つの子ノードへの参照が必要です。以下の Node クラスでは、値を data に格納します。left と right は最初は None で、後から子ノードを参照できます。これらのオブジェクトをつなぐと木構造になります。

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


root = Node(10)
root.left = Node(34)
root.right = Node(89)
root.left.left = Node(45)
root.left.right = Node(50)

ここでは、root が 34 と 89 の親です。ノード 45 と 50 は 34 の子で、89、45、50 は葉です。各ノードが持つ子への参照は最大2つなので、この構造は二分木です。ほかの種類の木では、left と right のような固定属性ではなく、子ノードのコレクションを使うなど、別の表現が必要になる場合があります。

Pythonで二分木を走査する

走査では各ノードを1回ずつ処理します。再帰呼び出しに対してどの位置でノードを訪問するかによって、処理順序が決まります。先行順巡回では、現在のノードを左部分木、右部分木より先に訪問します。中間順巡回では、左部分木、現在のノード、右部分木の順に訪問します。後行順巡回では、両方の部分木を訪問してから現在のノードを訪問します。以下の完全な例では、同じ木を構築し、それぞれの順序で表示します。

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def preorder(node):
    if node:
        print(node.data)
        preorder(node.left)
        preorder(node.right)


def inorder(node):
    if node:
        inorder(node.left)
        print(node.data)
        inorder(node.right)


def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.data)


root = Node(10)
root.left = Node(34)
root.right = Node(89)
root.left.left = Node(45)
root.left.right = Node(50)

print("Pre-order:")
preorder(root)
print("In-order:")
inorder(root)
print("Post-order:")
postorder(root)

再帰呼び出しでは、最初のセクションで作成したものと同じ left および right の参照をたどります。別の木を走査する場合は、ノードの構築部分を置き換え、走査関数はそのまま使えます。どの位置でノードを訪問するかによって、値の並び順が決まります。

Pythonライブラリを使ってツリーを実装する

この小さな二分木の例よりノード数が多い木や、より多くの機能が必要な場合は、anytree を使うとノード間の関係を管理し、木を描画できます。プロジェクトの環境に pip install anytree でインストールしてください。このAPIでは、Node の位置引数にノード名を指定します。子を親に接続するには、キーワード引数として parent=root を渡します。RenderTree は階層をたどり、各レベルの表示に使う接頭辞を返します。

上記と同じ形の木を作るには、まず root = Node("10") とし、続けて Node("34", parent=root) と Node("89", parent=root) を作ります。Node("45", parent=left_child) と Node("50", parent=left_child) を作ると、どちらの葉も 34 の下に配置できます。その後、for pre, fill, node in RenderTree(root) で反復処理し、pre + node.name を表示します。この例はライブラリAPIの説明であり、実行を示す証拠は含まれていません。