C++ N叉树拷贝构造函数问题排查

问题描述 #

拷贝构造函数未实现正确的深拷贝：拷贝生成copyTree后，删除原树firstTree的子节点时，copyTree也受到影响。同时析构函数相关逻辑存在错误。

类头文件 #

class Tree
{
private:
    string label;
    vector<Tree*> children;
    void free(Tree* tree);
    Tree* copyFrom(const Tree* other);

public:
    Tree(string _label, vector<Tree*> _children= vector<Tree*>());
    Tree(const Tree& other);
    void addChild(Tree* child);
    Tree& operator=(const Tree& other);
    Tree* addChild(Tree* parent, string label);
    void removeChild(vector<Tree*>::iterator position);
    void insertTree(Tree* tree, vector<Tree*>::iterator position);
    ~Tree();
};

实现代码 #

#include "Tree.h"

string Tree::getLabel() const
{
    return label;
}

Tree* Tree::copyFrom(const Tree* other)
{
    if (other == nullptr)
    {
        return nullptr;
    }
    Tree* result = new Tree(other->label);
    vector<Tree*> _children;
    for (int i = 0; i < other->children.size(); i++)
    {
        _children.push_back(copyFrom(other->children[i]));
    }
    result->children= _children;
    
    return result;
}

void Tree::free(Tree* tree)
{
    if (this == nullptr)
    {
        return;
    }
    for (int i = 0; i < tree->children.size(); i++)
    {
        delete tree->_children[i];
    }
    tree->children.clear();
    
}

Tree::Tree(string _label, vector<Tree*> _children)
    :label(_label), children(_children)
{

}

Tree::Tree(const Tree& other)
{
    const Tree* pointer = &other;
    copyFrom(pointer);
    this->label = pointer->label;
    this->children= pointer->children;
    pointer = nullptr;
}

Tree& Tree::operator=(const Tree& other)
{
    if (this != &other)
    {
        free(this);
        const Tree* pointer = &other;
        copyFrom(pointer);
        this->label = pointer->label;
        this->children= pointer->children;
        pointer = nullptr;
    }
    return *this;
}

Tree::~Tree()
{
    free(this);
}

void Tree::addChild(Tree* child)
{
    children.push_back(child);
}

Tree* Tree::addChild(Tree* parent, string label)
{
    if (parent == nullptr)
    {
        throw "No parent";
    }
    Tree* result = new Tree(label);
    parent->children.push_back(result);
    return result;
}

void Tree::removeChild(vector<Tree*>::iterator position)
{
    if (children.size() == 0)
    {
        throw "No children to delete from!";
    }
    int index = position - children.begin();
    Tree* toDelete = children.at(index);
    children.erase(position);
    delete toDelete;
}

void  Tree::insertChild(Tree* tree, vector<Tree*>::iterator position)
{
    if (tree== nullptr)
    {
        throw "Tree cannot be null!";
    }
    children.insert(position, tree);
}

错误分析 #

1. 拷贝构造函数与赋值运算符的核心错误 #

copyFrom函数确实实现了深拷贝逻辑，会创建新的Tree节点并递归拷贝子节点，但拷贝构造函数和operator=完全没有使用copyFrom的返回值，反而直接将原对象的children指针容器赋值给当前对象：

this->children= pointer->children;

这是典型的浅拷贝，导致两个Tree对象共享同一批子节点指针。当原树删除子节点时，拷贝树的指针也会指向已释放的内存，表现为拷贝树被影响。

2. free函数的错误 #

• 判断条件错误：if (this == nullptr)毫无意义，因为成员函数调用时this不可能为空，应该判断传入的tree是否为空：if (tree == nullptr)。
• 变量名错误：delete tree->_children[i]中的_children是笔误，类成员变量是children，应该改为tree->children[i]。
• 未正确释放子节点：当前逻辑只遍历子节点并delete，但没有递归调用free处理子节点的子节点，会导致内存泄漏。

3. 拷贝构造函数的冗余逻辑 #

copyFrom(pointer)创建了一个完整的深拷贝Tree对象，但这个对象的指针被直接丢弃，完全没有用到，属于无效代码。

修复方案 #

修复拷贝构造函数 #

删除无效的copyFrom调用，直接递归深拷贝原对象的子节点：

Tree::Tree(const Tree& other) : label(other.label) {
    // 递归拷贝每个子节点
    for (const Tree* child : other.children) {
        children.push_back(new Tree(*child));
    }
}

修复赋值运算符operator= #

采用拷贝并交换（Copy-and-Swap） idiom，简洁且安全：

#include <algorithm> // 用于swap

Tree& Tree::operator=(const Tree& other) {
    if (this != &other) {
        Tree temp(other); // 利用拷贝构造函数创建临时深拷贝对象
        // 交换当前对象与临时对象的资源
        std::swap(label, temp.label);
        std::swap(children, temp.children);
    }
    return *this;
}
// 临时对象temp会在函数结束时自动销毁，带走原对象的旧资源

修复free函数 #

修正判断条件、变量名，并递归释放子节点：

void Tree::free(Tree* tree) {
    if (tree == nullptr) {
        return;
    }
    // 递归释放每个子节点的资源
    for (Tree* child : tree->children) {
        free(child);
        delete child;
    }
    tree->children.clear();
}

修复析构函数 #

当前析构函数调用free(this)是合理的，但修复后的free会递归释放所有子节点，无需额外修改：

Tree::~Tree() {
    free(this);
}

额外优化建议 #

• 将copyFrom函数改为私有辅助函数，用于递归拷贝子节点，而非返回新Tree对象，避免资源浪费。
• 考虑使用智能指针（如std::unique_ptr<Tree>）替代原始指针，自动管理内存，减少手动释放的错误。

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