Python - 二叉搜索树

---

---

二叉搜索树 （BST） 是一棵所有节点都遵循以下属性的树。节点的左侧子树的 key 小于或等于其父节点的 key。节点的右侧子树的 key 大于其父节点的 key。因此，BST 将其所有子树分为两段;左侧子树和右侧子树

left_subtree (keys) 	≤ 	node (key) 	≤ 	right_subtree (keys)

在 B 树中搜索值

在树中搜索值涉及将传入值与退出节点的值进行比较。在这里，我们还从左到右遍历节点，最后遍历父节点。如果 chosen for 值与任何现有值都不匹配，则返回 not found 消息，否则返回 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)
	 	 	 	 	 	 else 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)
	 	 	 	else if 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))

输出

执行上述代码时，它会产生以下结果 -