二进制搜索树(BST)是一棵树,其中所有节点都遵循下述属性 - 节点的左子树的键小于或等于其父节点的键,右子树的键大于其父节点的键。 因此,BST将其所有子树分为两个部分:左子树和右子树,可以定义为–
left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)
在树中搜索值涉及将输入值与退出节点值进行比较,在这里,无涯教程也从左到右遍历节点,最后与父节点遍历,如果搜索到的值与任何退出值都不匹配,则返回“Not Found”消息,否则返回找到的消息。
class Node: def __init__(self, data): self.left=None self.right=None self.data=data # 插入方法创建节点 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 方法将值与节点进行比较 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') # 打印树 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
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)