Python-data-structure-python-binary-tree
提供:Dev Guides
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()
上記のコードが実行されると、次の結果が生成されます-
10
ツリーへの挿入
ツリーに挿入するには、上記で作成した同じノードクラスを使用し、挿入クラスを追加します。 挿入クラスは、ノードの値を親ノードと比較し、それを左ノードまたは右ノードとして追加することを決定します。 最後に、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
木を横断する
各ノードを訪問するシーケンスを決定することにより、ツリーを走査できます。 明確にわかるように、ノードから開始し、次に左のサブツリーにアクセスし、次に右のサブツリーにアクセスできます。 または、最初に右のサブツリーにアクセスし、次に左のサブツリーにアクセスすることもできます。 したがって、これらのツリートラバーサルメソッドには異なる名前があります。 ここでは、ツリートラバーサルアルゴリズムの実装の章で詳細に検討します。 リンク:/python_data_structure/python_tree_traversal_algorithms [ツリートラバーサルアルゴリズム]