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

1. Python でゼロからツリーを実装する
2. Python でバイナリツリーをトラバースする
3. Python ライブラリを使用してツリーを実装する

木はデータ構造の 1つです。データ構造は、メモリ内のデータを整理する方法に他なりません。ツリーは、ノード（頂点とも呼ばれます）とエッジの組み合わせです。ツリーには、ノードとエッジをいくつでも含めることができます。ノードはデータを保存する場所であり、エッジは 2 ノード間のパスです。二分木、三分木、二分探索木、AVL 木など、さまざまな種類のツリーが利用可能です。

木内のノードのタイプ：

1. 親ノード：1つ以上の子を持つノード。
2. 子ノード：親ノードを持つノード。
3. リーフノード：子を持たないノード。

この記事では、最初にライブラリを使用せずにツリーを最初から実装する方法を見てみましょう。その後、Python ライブラリを使用してツリーを実装する方法を説明します。

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

Python でツリーを作成するには、最初に、単一のノードを表す Node クラスを作成する必要があります。この Node クラスには 3つの変数が含まれます。1つ目は左の子を指す left、2つ目の変数はそのノードの値を含む data、右の子を指す right 変数です。

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

ツリーを初期化しましょう。

root = Node(10)

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

木は下のようになります。

          10
        /    \
       34      89
     /    \ 
    45    50 

クラス Node のオブジェクトを作成するたびに、__init__ コンストラクターが呼び出され、そのコンストラクター内のすべての変数が初期化されます。root には、値が 10 のツリーのルートノードと、値 34 の左の子と右の子を挿入する root.left と root.right が含まれます。値 89 のルートノードの子。バイナリツリーであるため、すべてのノードには最大 2つのノードが含まれます。

最後に、ノード 34 の子として、さらに 2つのノード、つまり 45 と 50 をツリーに挿入します。作成するツリーのタイプに応じて、ツリー内に必要な数のノードを挿入できます。

Python でバイナリツリーをトラバースする

これでツリーが作成されたので、ツリーをトラバースしてツリー要素を出力しましょう。トラバースは、ツリー内のすべてのノードにアクセスします。ツリー内のすべてのノードは、トラバーサルで 3 回訪問されます。ツリーをトラバースする方法は、上から下、左から右です。

先行順

ツリーをトラバースしているときに、ノードを初めて表示するたびに、そのノードを出力してから、左側のノードで再帰を実行してから、右側のノードで再帰を実行します。

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

出力：

10 
34 
45 
50 
89

中間順

インオーダートラバーサルを実行している間、最初に左側のノードで再帰を実行し、次に同じノードに 2 回目にアクセスすると、そのノードを出力します。次に、右側のノードで再帰を実行します。

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

出力：

45 
34 
50 
10 
89

後行順

ポストオーダートラバーサルの場合、左側のノードと右側のノードで再帰を実行し、同じノードに 3 回アクセスすると、そのノードを出力します。

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

出力：

45
50
34
89
10

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

これまで見てきたように、ツリーを最初から実装するには時間がかかり、多くのコードが必要です。Python でツリーを実装する簡単な方法は、anytree というライブラリを使用することです。anytree ライブラリを使用すると、大量のコードを記述せずにツリーを作成できます。

anytree ライブラリを使用するには、最初に以下のコマンドの助けを借りてライブラリをインストールする必要があります。

pip install anytree

ここでも、以前に作成したものと同じツリーを作成しています。これで、anytree ライブラリから Node と RenderTree をインポートできます。

from anytree import Node, RenderTree

root = Node(10)

level_1_child_1 = Node(34, parent=root)
level_1_child_2 = Node(89, parent=root)
level_2_child_1 = Node(45, parent=level_1_child_1)
level_2_child_2 = Node(50, parent=level_1_child_2)

for pre, fill, node in RenderTree(root):
    print("%s%s" % (pre, node.name))

# Tree Structure
#          10
#        /    \
#       34      89
#     /    \
#    45    50

出力：

10
├── 34
│   └── 45
└── 89
    └── 50

ここで、Node は 2つのパラメータをとるノードを作成します。1つ目はノードの値で、2つ目は親ノードの名前です（これはオプションのパラメーターです）。ツリーでは、root ノードが親を持たない唯一のノードであるため、root ノードの作成時に、最初のパラメーターのみを渡します。ノードの値であり、2 番目のパラメーターは渡しません。RenderTree メソッドは、出力に示されているようにツリー全体を出力するのに役立ちます。