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

Sahil Bhosale 2023年1月30日 2021年3月24日 Python Python Data Structure
  1. Python でゼロからツリーを実装する
  2. Python でバイナリツリーをトラバースする
  3. Python ライブラリを使用してツリーを実装する
Python で木データ構造を実装する

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

Python のツリー

木内のノードのタイプ:

  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.leftroot.right が含まれます。値 89 のルートノードの子。バイナリツリーであるため、すべてのノードには最大 2つのノードが含まれます。

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

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 ライブラリから NodeRenderTree をインポートできます。

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 メソッドは、出力に示されているようにツリー全体を出力するのに役立ちます。

Sahil Bhosale avatar Sahil Bhosale avatar

Sahil is a full-stack developer who loves to build software. He likes to share his knowledge by writing technical articles and helping clients by working with them as freelance software engineer and technical writer on Upwork.

LinkedIn

関連記事 - Python Data Structure

  • Python のリンクリスト