Python - 搜索树

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

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

在 B 树中搜索某个值

在树中搜索某个值包括将传入的值与已退出节点中的值进行比较。同样，此处我们从左到右遍历节点，然后最终再与父节点进行比较。如果要搜索的值与任何已退出值不匹配，那么我们返回找不到消息；否则返回找到消息。

示例

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