HOWTO · Python
Python で木データ構造を実装する
この記事では、Python で木データ構造を実装する方法を説明します。
木はデータ構造の 1つです。データ構造は、メモリ内のデータを整理する方法に他なりません。ツリーは、ノード（頂点とも呼ばれます）とエッジの組み合わせです。ツリーには、ノードとエッジをいくつでも含めることができます。ノードはデータを保存する場所であり、エッジは 2 ノード間のパスです。二分木、三分木、二分探索木、AVL 木など、さまざまな種類のツリーが利用可能です。
木内のノードのタイプ：
- 親ノード：1つ以上の子を持つノード。
- 子ノード：親ノードを持つノード。
- リーフノード：子を持たないノード。
この記事では、最初にライブラリを使用せずにツリーを最初から実装する方法を見てみましょう。その後、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 メソッドは、出力に示されているようにツリー全体を出力するのに役立ちます。
