二叉搜索树深拷贝构造函数实现：指针解引用问题求助

刚学C++的时候跟指针打交道真的容易头大，尤其是递归加二级指针的组合，我来帮你把这个深拷贝的问题捋明白～

首先先补充下默认的Node结构（方便后续理解）：

struct Node {
    int data;
    Node* left;
    Node* right;
    // 带参数的构造函数，方便创建节点
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

从你给出的代码片段来看，你的递归思路是对的，但可能在指针解引用或者递归调用的细节上出了问题。先给你修正后的完整helper函数：

void copyTree_helper(Node** destination, const Node* source) {
    // 终止条件：源节点为空，目标也设为空
    if (source == nullptr) {
        *destination = nullptr;
        return;
    }

    // 创建新节点并拷贝数据
    *destination = new Node(source->data);

    // 递归拷贝左子树：传递目标左节点的地址、源左节点指针
    copyTree_helper(&((*destination)->left), source->left);
    // 递归拷贝右子树
    copyTree_helper(&((*destination)->right), source->right);
}

关键细节解释 #

• 为什么用二级指针？因为我们需要修改外部指针的指向（让它指向新创建的节点）。如果传一级指针，只是传递指针的拷贝，函数内部的修改不会影响外部的指针变量。
• 关于解引用的优先级：->的优先级比&高，所以&((*destination)->left)是先拿到目标节点的左指针，再取它的地址传给下一层递归，括号可以保证运算顺序正确（其实不加括号也能运行，但加上更清晰）。
• 你之前的代码应该是没写完右子树的递归调用，补上就好啦。

更适合新手的简化写法（不用二级指针） #

其实可以让helper函数直接返回新创建的节点指针，逻辑更直观，不用纠结二级指针的解引用：

Node* copyTree_helper(const Node* source) {
    if (source == nullptr) {
        return nullptr;
    }

    // 创建当前节点
    Node* newNode = new Node(source->data);
    // 递归拷贝左右子树，直接赋值给新节点的左右指针
    newNode->left = copyTree_helper(source->left);
    newNode->right = copyTree_helper(source->right);

    return newNode;
}

然后在二叉搜索树的拷贝构造函数里这样用：

class BST {
private:
    Node* root;
    Node* copyTree_helper(const Node* source);
    // 记得实现销毁树的函数，避免内存泄漏
    void destroyTree(Node* node) {
        if (node == nullptr) return;
        destroyTree(node->left);
        destroyTree(node->right);
        delete node;
    }
public:
    // 拷贝构造函数
    BST(const BST& other) {
        root = copyTree_helper(other.root);
    }

    // 析构函数
    ~BST() {
        destroyTree(root);
    }

    // 赋值运算符重载（遵循三法则）
    BST& operator=(const BST& other) {
        if (this != &other) {
            // 先销毁当前树
            destroyTree(root);
            // 再拷贝新树
            root = copyTree_helper(other.root);
        }
        return *this;
    }
};

新手注意事项 #

• 优先用nullptr代替NULL，C++11之后的标准更推荐，类型更安全。
• 递归一定要写终止条件（源节点为空时返回），不然会触发栈溢出。
• 遵循三法则：如果实现了拷贝构造函数，一定要同时实现析构函数和赋值运算符重载，避免内存泄漏或者浅拷贝问题。

内容的提问来源于stack exchange，提问作者E.Bille