Python-data-structure-python-binary-search-tree
提供:Dev Guides
Python-検索ツリー
バイナリ検索ツリー(BST)は、すべてのノードが以下のプロパティに従うツリーです。ノードの左のサブツリーには、親ノードのキー以下のキーがあります。 ノードの右サブツリーには、親ノードのキーよりも大きいキーがあります。 したがって、BSTはすべてのサブツリーを2つのセグメントに分割します。左のサブツリーと右のサブツリーは、次のように定義できます。
left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)
Bツリーで値を検索する
ツリー内の値を検索するには、入力値とノードを終了する値を比較する必要があります。 ここでも、ノードを左から右へ、そして最後に親をたどります。 検索された値が既存の値のいずれとも一致しない場合、not foundメッセージが返されます。それ以外の場合は、見つかったメッセージが返されます。
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert method to create nodes
def insert(self, data):
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
# findval method to compare the value with nodes
def findval(self, lkpval):
if lkpval < self.data:
if self.left is None:
return str(lkpval)+" Not Found"
return self.left.findval(lkpval)
elif lkpval > self.data:
if self.right is None:
return str(lkpval)+" Not Found"
return self.right.findval(lkpval)
else:
print(str(self.data) + ' is found')
# Print the tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
print(root.findval(7))
print(root.findval(14))
上記のコードが実行されると、次の結果が生成されます-
7 Not Found
14 is found