C++如何实现二叉搜索树的最大值与最小值查询-C++-PHP中文网

bst中最小值位于最左节点，从根开始沿left指针迭代至空；最大值同理在最右节点；中序遍历找极值是低效误用，时间复杂度升至o(n)。

c++如何实现二叉搜索树的最大值与最小值查询

如何在BST中找到最小值——只需一直往左走

二叉搜索树（BST）的性质决定了最左节点就是最小值。不需要遍历整棵树，也不用递归回溯，直接从根开始沿 left 指针一路向下，直到遇到 nullptr 为止。

常见错误是忘记判空：如果树为空，root 是 nullptr，直接访问 root->left 会崩溃。

迭代写法更安全、空间复杂度 O(1)，推荐优先使用
递归写法虽简洁，但深度过大时有栈溢出风险（比如退化成链表的 BST）
若节点定义含 parent 指针，不能靠它找最小值——BST 中最小值只和左子树有关

int findMin(Node* root) {
    if (!root) throw std::runtime_error("BST is empty");
    while (root->left) root = root->left;
    return root->val;
}

如何在BST中找到最大值——只需一直往右走

同理，BST 最大值一定在最右节点。逻辑和找最小值完全对称，只是把 left 换成 right。

注意：不要混淆“最大值”和“后继节点”。例如在 findMax(root->left) 是找左子树最大值（即前驱），不是整棵树最大值。

和 findMin 一样，空树必须提前检查，否则解引用空指针
某些实现会把 findMax 写成递归形式 return root->right ? findMax(root->right) : root->val，可读性尚可，但无实质优势
若 BST 支持重复值且允许插入到右子树，则最大值仍满足该性质（BST 定义中“右子树 ≥ 根”不影响最右节点为最大）

int findMax(Node* root) {
    if (!root) throw std::runtime_error("BST is empty");
    while (root->right) root = root->right;
    return root->val;
}