C++二叉搜索树(BST)递归实现clone()深拷贝方法的相关问题

1. clone方法实现 #

clone的逻辑是递归完成深拷贝，终止条件为传入节点为空，否则新建节点后递归克隆左右子树：

Node* clone(Node* n) const
{
    // 递归终止：空节点直接返回空
    if (n == nullptr) {
        return nullptr;
    }
    // 新建节点，复制当前节点值
    Node* newNode = new Node(n->x);
    // 递归克隆左、右子树
    newNode->left = clone(n->left);
    newNode->right = clone(n->right);
    return newNode;
}

2. 拷贝构造函数修改 #

原有拷贝构造是浅拷贝，仅复制根节点指针，会导致两个树共用同一份节点内存，出现double free、修改互相影响的问题，修改为调用clone完成深拷贝：

Tree(const Tree &t) 
{
    root = clone(t.root);
}

3. 其他待实现方法参考 #

3.1 迭代查找 #

Node* find(int key)
{
    Node* cur = root;
    while (cur != nullptr) {
        if (cur->x == key) return cur;
        cur = key < cur->x ? cur->left : cur->right;
    }
    return nullptr;
}

3.2 递归查找 #

private: Node* find2(int key, Node* n)
{
    if (n == nullptr) return nullptr;
    if (n->x == key) return n;
    return key < n->x ? find2(key, n->left) : find2(key, n->right);
}

3.3 统计节点总数 #

private: int node_count(Node* n)
{
    if (n == nullptr) return 0;
    return 1 + node_count(n->left) + node_count(n->right);
}

3.4 计算最大深度 #

private: int depth(Node* n)
{
    if (n == nullptr) return 0;
    int left_depth = depth(n->left);
    int right_depth = depth(n->right);
    return 1 + (left_depth > right_depth ? left_depth : right_depth);
}

4. 已知bug修复 #

原有公有的前序、后序遍历方法错误调用了中序遍历，修改为：

public: void preOrder(){ preOrder(root); }
public: void postOrder(){ postOrder(root); }

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