Python实现二叉搜索树BST：核心算法与完整代码示例

桃夭

发布时间：2026-10-13 | 2人浏览过

原创

本文详细解析如何使用Python实现二叉搜索树（BST）。内容涵盖BST的定义与性质，并提供求树深度、中序遍历输出节点值、查找指定关键字节点等核心功能的代码实现。重点展示了递归与迭代两种查找方式的时间复杂度为O(h)，并附带完整的Node类定义及测试用例，帮助开发者掌握BST的基础操作与Python编程技巧。

二叉搜索树（BST）定义与性质

二叉排序树，也被称为二叉查找树或二叉搜索树，是一种重要的数据结构。

二叉排序树（Binary Sort Tree）的定义如下：它要么是一棵空树，要么满足以下特定性质的二叉树。

具体性质包括：1. 若左子树非空，则左子树上所有节点的值均严格小于根节点的值；2. 若右子树非空，则右子树上所有节点的值均严格大于根节点的值；3. 其左、右子树也必须分别为二叉排序树。

计算树的深度
按顺序输出节点值（采用中序遍历方式）
在二叉搜索树中查询具有给定关键字的节点，并返回该节点的位置。该操作的时间复杂度为O(h)，其中h代表树的高度。
通过递归或迭代方式求解最大关键字元素
通过递归或迭代方式求解最小关键字元素

Python实现核心算法与代码


# -*- coding:utf-8 -*-
'''
用Python实现二叉搜索树。
'''


class Node():
  def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None

#求树的深度
def depth(root):
    if root is None:
      return 0
    else:
      return 1 + max(depth(root.left), depth(root.right))


#按序输出结点值（中序遍历）
def input_in_order(root):
  if root is None:
    return
  input_in_order(root.left)
  print(root.val)
  input_in_order(root.right)



#（递归实现 、迭代实现）查询二叉搜索树中一个具有给点关键字的结点，返回该节点的位置。时间复杂度是O(h),h是树的高度。
#递归实现
def search1(root, value):
  if root is None or root.val == value:
    return root
  if root.val > value:
    return search1(root.left, value)
  if root.val < value:
    return search1(root.right, value)


#迭代实现
def search2(root, value):
  while root != None and root.val != value:
    if root.val > value:
      root = root.left
    elif root.val < value:
      root = root.right
  return root


#求最大关键字元素
#迭代实现
def max_value1(root):
  while root != None and root.left != None:
    root = root.right
  if root is None:
    return root
  else:
    return root.val

#递归实现
def max_value2(root):
  if root == None:
    return root
  elif root.right == None:
    return root.val
  else:
    return max_value2(root.right)


#求最小关键字元素
#递归实现
def min_value1(root):
  if root is None:
    return root
  elif root.left is None:
    return root.val
  else:
    return min_value1(root.left)


#迭代实现
def min_value2(root):
  if root is None:
    return root
  while root.left !=None:
    root = root.left
  return root.val


if __name__ == '__main__':
  a = Node(15)
  b = Node(6)
  c = Node(18)
  d = Node(4)
  e = Node(8)
  f = Node(17)
  g = Node(20)
  h = Node(13)
  i = Node(9)
  a.left = b
  a.right = c
  b.left = d
  b.right = e
  c.left = f
  c.right = g
  e.right = h
  h.left = i
  print(search1(a, 13))
  print(search2(a,13))
  print(max_value1(a))
  print(max_value2(a))
  print(min_value1(a))
  print(min_value2(a))