二叉搜索树extractMin函数异常：重复调用返回相同值求助

嘿，我一眼就瞅出你这问题的症结所在了！你的findMin函数只干了“找到最小值”这一件事，完全没修改树的结构——每次调用它，都会找到同一棵树里的最左节点（也就是当前的最小值节点），那返回值当然一模一样啊，因为那个节点还好好待在树里没动呢！

先看看你贴的这段代码：

double findMin(node * p) { 
    if(p == NULL) { 
        return -1; 
    } else { 
        temp = p; 
        while(temp->left != NULL) { 
            temp = temp->left; 
        } 
        return temp->data; 
    } 
}

这段逻辑就是单纯遍历到树的最左节点，把它的值返回，但从头到尾没碰过树的结构——既没把这个节点删掉，也没调整它的父节点或子节点的指向。所以哪怕你在主函数里连续调用两次，树还是原来那棵树，最小值节点也还在原位，结果自然不会变。

怎么搞定这个问题？ #

你需要让辅助函数（或者配合主函数）完成两个核心动作：找到最小值，并且把这个节点从树中移除，同时还要维护树的结构（比如如果这个最小节点有右子树，得把右子树接回正确的位置）。

方案1：修改函数，让它真正“提取”最小值 #

我给你调整一下函数逻辑，把它改成真正的extractMin（提取最小值）函数，假设你用的是二叉搜索树结构：

double extractMin(node **root) {
    if (*root == NULL) {
        return -1; // 空树返回错误标记
    }

    // 遍历找到最左的最小值节点，同时记录它的父节点
    node *parent = NULL;
    node *current = *root;
    while (current->left != NULL) {
        parent = current;
        current = current->left;
    }

    double minValue = current->data;

    // 删除这个节点，分情况处理：
    if (parent == NULL) {
        // 最小值是根节点，直接把根换成它的右子树
        *root = current->right;
    } else {
        // 把父节点的左指针指向当前节点的右子树
        parent->left = current->right;
    }

    free(current); // 别忘了释放内存，避免内存泄漏
    return minValue;
}

这里我把函数名改成了extractMin（更贴合“提取”的语义），还用了双重指针来修改根节点的指向（如果最小值刚好是根的话）。每次调用这个函数，都会真正把最小值节点从树中移除，下次调用就会找到新的最小值了。

方案2：保留原findMin，但调用后手动删除节点 #

如果你不想改findMin，也可以在主函数里先调用它拿到最小值，再调用一个专门的deleteNode函数把对应值的节点删掉。不过这种方式需要额外做一次节点查找，效率不如方案1高——毕竟要遍历两次树嘛。

总结一下 #

你的核心问题就是辅助函数只做了“查询”没做“删除”，树的状态根本没变化。只要在提取最小值的同时，把对应的节点从树里移除，就能解决两次返回相同值的问题啦！

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