如何在二叉搜索树（Binary Search Tree）中查找最小节点

你的find_min方法存在两处关键错误，导致无法正常工作：

• 传入的root参数未被正确使用，循环中错误引用self.left而非当前遍历节点的左子节点，逻辑完全混乱。
• 循环条件错误，直接将root替换为self.left会导致无法逐层遍历左子树，要么陷入死循环，要么直接返回空值。

修复后的代码（迭代版本） #

我们可以调整方法逻辑，从当前节点开始，一直遍历左子节点直到尽头，这就是二叉搜索树的最小节点：

class BinarySearchTree:

    def __init__(self, root):
        self.root = root
        self.left = None
        self.right = None

    def insert(self, node):
        if node == self.root:  
            return
        elif node < self.root:  
            if self.left:
                self.left.insert(node)
            else:
                self.left = BinarySearchTree(node)
        else: 
            if self.right:
                self.right.insert(node)
            else:
                self.right = BinarySearchTree(node)


    def search(self, target):
        if target == self.root:
            return True
        else:
            if target < self.root:
                if self.left:
                    return self.left.search(target)
                return False

            if target > self.root:
                if self.right:
                    return self.right.search(target)
                return False

    
    def find_min(self):
        current = self
        # 持续遍历左子树，直到没有左子节点
        while current.left is not None:
            current = current.left
        return current.root  # 返回最小节点的值，若需返回节点对象则返回current

可选：递归版本实现 #

如果你更倾向递归写法，逻辑会更简洁：

def find_min(self):
    # 没有左子节点时，当前节点就是最小值
    if self.left is None:
        return self.root
    # 递归查找左子树的最小值
    return self.left.find_min()

测试验证 #

# 创建测试树
bst = BinarySearchTree(10)
bst.insert(5)
bst.insert(15)
bst.insert(3)
bst.insert(7)

print(bst.find_min())  # 输出：3，符合预期

内容的提问来源于stack exchange，提问作者Infernalissss