BST的CloneSubtree函数实现错误排查及调用方法咨询

1. 子树根节点搜索逻辑完全错误 #

• 循环判断存在重复代码：两个分支判断条件都是key > cur->item.id，没有处理key < cur->item.id和key == cur->item.id的情况，会直接导致死循环，永远找不到目标节点。
• 搜索结束后没有判断是否找到目标节点：如果t1中不存在对应item的节点，cur会为NULL，后续访问cur成员会触发空指针崩溃。

2. 参数传递逻辑错误 #

• CloneSubtree的入参t1是值传递，会触发BST的拷贝构造，如果没有实现BST的深拷贝构造函数，会导致t1的内存被意外释放，也违背了t1不修改的要求，应该改为const BST& t1传常引用。
• CloneSubtree2的入参t2是指针值传递，函数内给t2赋值new的节点只会修改形参副本，不会修改当前BST对象的root指针，克隆结果根本不会保存到t2中，需要改为指针引用BTNode*& t2才能修改外部的指针变量。

3. 克隆逻辑完全写反且修改原树 #

• 节点赋值方向错误：代码写的是cur->left = t2->left、cur->right = t2->right，cur是原树t1的节点，直接修改了原树的内容，完全违反t1不能修改的要求，正确逻辑是给新创建的t2节点的左右指针赋值克隆后的子树。
• 递归逻辑错误：没有接收递归返回的新节点，左右子树的克隆完全没有生效。
• 克隆过程中反复调用preOrderPrint()，每次递归都会打印一次，不符合需求中克隆完成后才打印的要求。

4. 缺少前置校验 #

• 没有检查当前调用对象（也就是t2）是否为空树，不符合题目要求的t2克隆前必须为空的条件，会导致内存泄漏。

修正CloneSubtree函数 #

bool BST::CloneSubtree(const BST& t1, type item) {
    // 前置校验：当前对象必须为空
    if (!empty()) return false;
    if (t1.empty()) return false;

    BTNode* cur = t1.root;
    int key = item.id;
    // 修正搜索逻辑
    while (cur != nullptr) {
        if (key > cur->item.id) {
            cur = cur->right;
        } else if (key < cur->item.id) {
            cur = cur->left;
        } else {
            // 找到目标节点，跳出循环
            break;
        }
    }
    // 没找到目标节点直接返回
    if (cur == nullptr) return false;
    // 开始克隆
    CloneSubtree2(root, cur);
    return true;
}

修正CloneSubtree2函数 #

bool BST::CloneSubtree2(BTNode*& t2, BTNode* cur) {
    if (cur == nullptr) {
        t2 = nullptr;
        return true;
    }
    // 创建新节点，直接赋值原节点内容
    t2 = new BTNode(cur->item);
    // 递归克隆左右子树
    CloneSubtree2(t2->left, cur->left);
    CloneSubtree2(t2->right, cur->right);
    return true;
}

main函数调用示例 #

int main() {
    // 假设t1已经初始化完成
    BST t1, t2;
    // 插入t1的节点逻辑省略...
    Student target;
    target.id = 126;
    if (t2.CloneSubtree(t1, target)) {
        cout << "t1前序遍历结果：" << endl;
        t1.preOrderPrint();
        cout << "t2前序遍历结果：" << endl;
        t2.preOrderPrint();
    }
    // 内存释放逻辑省略...
    return 0;
}

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