二叉搜索树最大素数查找代码输出恒为0如何修复

问题现象 #

编写程序查找二叉搜索树中的最大素数时，运行结果始终输出0，原始实现代码如下：

bool isPrime(int number) {
    bool is_prime = true;

    if (number == 0 || number == 1)
        is_prime = false;

    for (int i = 2; i <= number / 2; i++)
    {
        if (number % i == 0) {
            is_prime = false;
            break;
        }
    }
    return is_prime;
}

BSTNode* largestPrime(BSTNode* root)
{
    BSTNode* temp = new BSTNode;
    temp->data = 0;

    if (root != nullptr) {
        largestPrime(root->left);
        if (isPrime(root->data) && temp->data < root->data)
            temp->data = root->data;
        largestPrime(root->right);
    }
    return temp;
}

问题根因 #

• 递归结果未透传：每次进入largestPrime函数都会在当前函数栈新建一个初始值为0的temp节点，左右子树的递归调用返回值完全没有被接收和使用，子递归中找到的素数结果只存在于子函数的局部变量中，函数返回后就被销毁，根本无法同步到最外层调用的temp变量。
• 无效内存分配：每次递归都会new一个新的BSTNode，这些节点既没有被释放，绝大多数也没有被实际使用，既造成内存泄漏，还因为只初始化了data字段，left/right指针为野值，存在运行崩溃风险。
• 逻辑未利用二叉搜索树特性：采用普通二叉树的遍历逻辑，没有利用BST右子树值>根节点值>左子树值的性质做优化，遍历效率低。
• 素数判断逻辑有缺陷：未处理负数场景，循环上界设置为number/2，存在大量冗余计算。

修复后代码 #

优化后的素数判断函数 #

bool isPrime(int number) {
    // 小于2的所有整数都不是素数
    if (number <= 1) return false;
    // 2是唯一的偶素数
    if (number == 2) return true;
    // 大于2的偶数直接排除
    if (number % 2 == 0) return false;
    // 循环上界取平方根即可，步长设为2跳过偶数，减少一半循环量
    for (int i = 3; i * i <= number; i += 2) {
        if (number % i == 0) return false;
    }
    return true;
}

优化后的最大素数查找函数 #

利用BST的排序特性，采用右子树->根节点->左子树的遍历顺序，从值最大的节点开始查找，第一个遇到的素数就是整棵树的最大素数，找到后直接返回，不需要遍历整棵树：

BSTNode* largestPrime(BSTNode* root)
{
    // 空节点直接返回空
    if (root == nullptr) return nullptr;
    // 优先查找值更大的右子树，右子树找到素数直接返回
    BSTNode* rightPrime = largestPrime(root->right);
    if (rightPrime != nullptr) return rightPrime;
    // 右子树无素数，判断当前节点是否为素数
    if (isPrime(root->data)) return root;
    // 当前节点不是素数，查找左子树
    return largestPrime(root->left);
}

修复说明 #

• 移除了所有无效的new操作，直接返回树中已存在的节点指针，不存在内存泄漏问题
• 递归调用的结果逐层向上返回，不会丢失子树的查找结果
• 如果整棵树中不存在素数，函数直接返回nullptr，调用方可以根据返回值判断是否找到结果，不会返回无意义的0值
• 遍历逻辑针对BST特性做了优化，平均查找效率远高于原始实现
• 素数判断函数修复了边界问题，计算效率提升明显

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