Python实现二叉查找树：定义、递归操作与完整代码解析

Chloe

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

原创

本文详细解析Python中二叉查找树的实现原理。涵盖BST定义、最值查找逻辑，重点讲解基于递归的插入、查询及复杂删除操作（含后继节点处理）。附带完整TreeNode类定义与测试代码，帮助开发者掌握核心数据结构实现。

本文主要探讨如何利用Python语言实现二叉查找树，并提供了具体的原理介绍与代码实现方案。

1. 二叉查找树的基本定义：

若左子树非空，则其所有节点的值均小于根节点的值；若右子树非空，则其所有节点的值均大于根节点的值。此外，左右子树本身也必须分别满足二叉查找树的性质。

2. 最值查找与节点删除逻辑：二叉查找树中最左侧的节点即为最小值，只需沿左子树不断遍历至空节点即可找到；同理，最右侧节点为最大值，沿右子树遍历至空节点即可。插入、查找及删除操作均通过递归方式实现。在删除节点S时，若其左右子树均非空，则并非直接删除S，而是找到其右子树中的后继节点，将后继节点的值赋给S，随后删除该后继节点；若S的左子树或右子树为空，则可直接删除S节点。

3. 二叉查找树的Python代码实现：

class TreeNode: 
  def __init__(self,val): 
    self.val=val; 
    self.left=None; 
    self.right=None; 
def insert(root,val): 
  if root is None: 
    root=TreeNode(val); 
  else: 
    if val<root.val: 
      root.left=insert(root.left,val);  #递归地插入元素 
    elif val>root.val: 
      root.right=insert(root.right,val);  
  return root; 
 
def query(root,val): 
  if root is None: 
    return ; 
  if root.val is val: 
    return 1; 
  if root.val <val: 
    return query(root.right,val); #递归地查询 
  else:  
    return query(root.left,val); 
def findmin(root): 
  if root.left: 
    return findmin(root.left); 
  else: 
    return root; 
   
def delnum(root,val): 
  if root is None: 
    return ; 
  if val<root.val: 
    return delnum(root.left,val); 
  elif val>root.val: 
    return delnum(root.right,val); 
  else:                       # 删除要区分左右孩子是否为空的情况 
    if(root.left and root.right): 
       
      tmp=finmin(root.right);       #找到后继结点 
      root.val=tmp.val; 
      root.right=delnum(root.right,val);  #实际删除的是这个后继结点 
       
    else: 
      if root.left is None: 
        root=root.right; 
      elif root.right is None: 
        root=root.left; 
  return root; 
         
         
#测试代码       
root=TreeNode(3); 
root=insert(root,2); 
root=insert(root,1); 
root=insert(root,4); 
 
#print query(root,3); 
print query(root,1); 
root=delnum(root,1); 
print query(root,1);

运行结果如下：