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