c++中如何找到二叉树的最小值_c++二叉树最小值查找方法-C++-PHP中文网

c++中如何找到二叉树的最小值_c++二叉树最小值查找方法

冰火之心

发布： 2025-09-29 12:06:02

原创

966人浏览过

在BST中最小值位于最左叶节点，递归和迭代法均可实现，时间复杂度O(h)；非BST需遍历全树比较，推荐迭代法处理BST。

c++中如何找到二叉树的最小值_c++二叉树最小值查找方法

在C++中查找二叉树的最小值，关键在于理解二叉搜索树（BST）的性质：对于任意节点，其左子树的所有节点值都小于它，右子树的所有节点值都大于它。因此，最小值一定位于最左侧的叶子节点。

递归方法查找最小值

通过递归不断深入左子树，直到遇到空节点为止。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
<p>int findMin(TreeNode* root) {
if (root == nullptr) {
<strong>// 防止空树访问错误</strong>
throw std::invalid_argument("树为空");
}
if (root->left == nullptr) {
return root->val;  <strong>// 最左节点即为最小值</strong>
}
return findMin(root->left);
}</p>

登录后复制

迭代方法查找最小值

使用循环代替递归，从根节点开始一直向左走。

int findMinIterative(TreeNode* root) {
    if (root == nullptr) {
        throw std::invalid_argument("树为空");
    }
    while (root->left != nullptr) {
        root = root->left;
    }
    return root->val;
}

登录后复制

非二叉搜索树的情况处理

如果树不是二叉搜索树，无法利用有序性，则需要遍历整棵树比较所有节点。

宣小二

宣小二：媒体发稿平台，自媒体发稿平台，短视频矩阵发布平台，基于AI驱动的企业自助式投放平台。

查看详情

立即学习“C++免费学习笔记（深入）”；

void traverseAndCompare(TreeNode* root, int& minVal) {
    if (root == nullptr) return;
    if (root->val < minVal) minVal = root->val;
    traverseAndCompare(root->left, minVal);
    traverseAndCompare(root->right, minVal);
}
<p>int findMinInGeneralTree(TreeNode* root) {
if (root == nullptr) {
throw std::invalid_argument("树为空");
}
int minVal = root->val;
traverseAndCompare(root, minVal);
return minVal;
}</p>

登录后复制

如果是二叉搜索树，推荐使用迭代法找最左节点，时间复杂度O(h)，h为树的高度；普通二叉树则必须完整遍历。基本上就这些，逻辑清晰且容易实现。

以上就是c++++中如何找到二叉树的最小值_c++二叉树最小值查找方法的详细内容，更多请关注php中文网其它相关文章！