Python-二分木

ツリーは、エッジで接続されたノードを表します。これは非線形のデータ構造です。以下の特性があります。

1つのノードがルートノードとしてマークされます。
ルート以外のすべてのノードは、1つの親ノードに関連付けられています。
各ノードは、任意の数のchidノードを持つことができます。

前に説明したosノードの概念を使用して、Pythonでツリーデータ構造を作成します。1つのノードをルートノードとして指定し、さらにノードを子ノードとして追加します。以下はルートノードを作成するプログラムです。

ルートを作成する

Nodeクラスを作成し、ノードに値を追加して割り当てます。これは、ルートノードのみを持つツリーになります。

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data


    def PrintTree(self):
        print(self.data)

root = Node(10)

root.PrintTree()

上記のコードを実行すると、次の結果が得られます。

ツリーに挿入する

ツリーに挿入するには、上記で作成したものと同じノードクラスを使用し、それにinsertメソッドを追加します。insertメソッドは、ノードの値を親ノードと比較し、それを左ノードまたは右ノードとして追加することを決定します。最後に、PrintTreeメソッドを使用してツリーを印刷します。

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data

    def insert(self, data):
# Compare the new value with the parent node
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

# Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)

root.PrintTree()

上記のコードを実行すると、次の結果が得られます。

3 6 12 14

木を横断する

各ノードにアクセスするシーケンスを決定することで、ツリーをトラバースできます。はっきりとわかるように、ノードから始めて、最初に左側のサブツリーにアクセスし、次に右側のサブツリーにアクセスします。または、最初に右側のサブツリーにアクセスし、次に左側のサブツリーにアクセスすることもできます。したがって、これらのツリー走査方法には異なる名前があります。ここでツリー走査アルゴリズムを実装する章でそれらを詳細に研究します。ツリートラバーサルアルゴリズム