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

输出

当上述代码被执行时，它产生了以下结果 –