Python - 搜索树

二叉搜索树 (BST) 是一棵树，其中所有节点都遵循以下属性。节点的left_subtree(左子树)的键小于或等于其父节点的键。一个节点的right_subtree(右子树)的键值大于其父节点的键值。因此，BST 将其所有子树分为两段； left_subtree(左子树)和right_subtree(右子树)

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

在 B-tree 中搜索一个值

在树中搜索值涉及将传入值与退出节点的值进行比较。 在这里，我们也从左到右遍历节点，最后遍历父节点。 如果搜索到的值与任何现有值都不匹配，那么我们将返回未找到的消息，否则返回找到的消息。

示例

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))

输出

当上面的代码执行时，会产生如下结果 −

7 Not Found
14 is found