Python 制搜索树
Python 二进制搜索树详细操作教程
二进制搜索树(BST)是其中所有节点都遵循下述属性的树-节点的左子树的键小于或等于其父节点的键。节点的右子树的密钥大于其父节点的密钥。因此,BST将其所有子树分为两个部分:左子树和右子树,可以定义为–
# Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)
在B树中搜索值
在树中搜索值涉及将输入值与值退出节点进行比较。在这里,我们也从左到右遍历节点,最后与父节点遍历。如果搜索到的值与任何退出值都不匹配,则返回“未找到”消息,否则返回找到的消息。
# Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
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))
运行结果如下: