Python-検索ツリー
二分探索木(BST)は、すべてのノードが以下のプロパティに従うツリーです。ノードの左側のサブツリーには、親ノードのキー以下のキーがあります。ノードの右側のサブツリーには、その親ノードのキーよりも大きいキーがあります。したがって、BSTはすべてのサブツリーを2つのセグメントに分割します。左側のサブツリーと右側のサブツリーは、次のように定義できます–
left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)
Bツリーで値を検索する
ツリー内の値を検索するには、入力値と終了ノードの値を比較する必要があります。ここでも、ノードを左から右にトラバースし、最後に親とトラバースします。検索された値がどのexitign値とも一致しない場合は、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