C++ 二叉樹深拷貝陷阱：預設拷貝構造函數導致的雙重釋放與正確實現模式

C++ 類若包含原始指標成員（如二叉樹根節點指標），預設拷貝構造函數與拷貝賦值運算符執行**淺拷貝**，導致多個對象共享同一塊動態記憶體，析構時觸發**雙重釋放**崩潰。本文通過具體錯誤案例深度剖析問題根因，提供三種標準解決方案（深拷貝、引用計數、禁止拷貝/移動語義），並給出完整可編譯的正確實現代碼。

一、問題複現：淺拷貝導致的雙重釋放

錯誤代碼分析

// binarytree.h - 錯誤版本
template <class T>
struct BTNode {
    T element;
    BTNode<T>* lChild;
    BTNode<T>* rChild;
    BTNode() : lChild(nullptr), rChild(nullptr) {}
    BTNode(const T& x) : element(x), lChild(nullptr), rChild(nullptr) {}
    BTNode(const T& x, BTNode<T>* l, BTNode<T>* r) 
        : element(x), lChild(l), rChild(r) {}
};

template <class T>
class BinaryTree {
public:
    BinaryTree() : root(nullptr) {}
    ~BinaryTree() { Clear(); }  // 遞歸刪除所有節點
    
    // 缺少拷貝構造函數、拷貝賦值運算符、移動構造、移動賦值
    // 編譯器生成預設版本 → 淺拷貝 root 指標！
    
    void Copy(BinaryTree<T>& x) { x.root = Copy(root); }  // 邏輯錯誤：共享節點
    
private:
    BTNode<T>* root;
    void Clear(BTNode<T>*& t) { /* 遞歸 delete */ }
    BTNode<T>* Copy(BTNode<T>* t) { /* 遞歸 new 節點 */ }
};

main.cpp 錯誤調用

// main.cpp
BinaryTree<char> z;  // 建立樹 z
// ... 構建 z ...

BinaryTree<char> k = new BinaryTree<char>();  // 錯誤語法！new 返回指標，非對象
// 正確應為：BinaryTree<char> k;  或  auto k = make_unique<BinaryTree<char>>();

z.Copy(k);  // k.root = Copy(z.root) → k.root 指向 z 的節點副本？
// 實際上 Copy 返回新節點，但 k 稍後析構會 delete 這些節點
// z 後續析構再次 delete 相同節點 → 雙重釋放崩潰

編譯錯誤訊息解讀

error: no match for 'operator=' (operand types are 'BinaryTree<char>' and 'BinaryTree<char>*')
BinaryTree<char> k = new BinaryTree<char>();  // new 返回指標，無法賦值給對象

二、核心原理：C++ 物件生命週期與資源管理

預設特殊成員函數行為

雙重釋放時序圖

BinaryTree z;           // z.root → 節點A
BinaryTree k = z;       // 預設拷貝構造：k.root → 節點A (共享！)
k.~BinaryTree();        // k 析構：Clear() delete 節點A
z.~BinaryTree();        // z 析構：Clear() 再次 delete 節點A → CRASH (double free)

三、三大標準解決方案

方案一：深拷貝 (Rule of Three / Five 完整實現)

// binarytree.h - 正確版本：深拷貝
template <class T>
class BinaryTree {
public:
    BinaryTree() : root(nullptr) {}
    
    // 析構函數
    ~BinaryTree() { Clear(root); }
    
    // 拷貝構造函數
    BinaryTree(const BinaryTree& other) : root(Clone(other.root)) {}
    
    // 拷貝賦值運算符 (Copy-and-Swap 慣用法)
    BinaryTree& operator=(BinaryTree other) {  // 參數按值傳遞 → 自動拷貝/移動
        swap(root, other.root);
        return *this;
    }
    
    // 移動構造函數 (C++11)
    BinaryTree(BinaryTree&& other) noexcept : root(other.root) {
        other.root = nullptr;
    }
    
    // 移動賦值運算符 (C++11)
    BinaryTree& operator=(BinaryTree&& other) noexcept {
        if (this != &other) {
            Clear(root);
            root = other.root;
            other.root = nullptr;
        }
        return *this;
    }
    
    // 業務介面
    void Copy(BinaryTree& target) const {  // 深拷貝給目標樹
        target.Clear();
        target.root = Clone(root);
    }
    
private:
    BTNode<T>* root;
    
    // 遞歸深度克隆
    static BTNode<T>* Clone(BTNode<T>* node) {
        if (!node) return nullptr;
        return new BTNode<T>(node->element, Clone(node->lChild), Clone(node->rChild));
    }
    
    static void Clear(BTNode<T>*& node) {
        if (node) {
            Clear(node->lChild);
            Clear(node->rChild);
            delete node;
            node = nullptr;
        }
    }
};

方案二：shared_ptr 引用計數共享所有權

// 現代 C++ 風格：shared_ptr 自動管理
template <class T>
struct BTNode {
    T element;
    shared_ptr<BTNode> left, right;
    BTNode(const T& x) : element(x) {}
};

template <class T>
class BinaryTree {
public:
    BinaryTree() = default;
    // 無需顯式析構/拷貝/移動！shared_ptr 自動引用計數
    // 複製 BinaryTree = 複製 root shared_ptr → 共享節點，計數+1
    // 最後一個 BinaryTree 銷毀時 → 計數歸零 → 遞歸釋放所有節點
    
    void Copy(BinaryTree& target) const {
        target.root = root;  // 共享所有權，非深拷貝
    }
    
private:
    shared_ptr<BTNode<T>> root;
};

方案三：unique_ptr 獨佔所有權 + 禁止拷貝/啟用移動

// 獨佔語義：樹不可拷貝，只可移動
template <class T>
struct BTNode {
    T element;
    unique_ptr<BTNode> left, right;
    BTNode(const T& x) : element(x) {}
};

template <class T>
class BinaryTree {
public:
    BinaryTree() = default;
    ~BinaryTree() = default;  // unique_ptr 自動遞歸釋放
    
    BinaryTree(const BinaryTree&) = delete;            // 禁用拷貝
    BinaryTree& operator=(const BinaryTree&) = delete; // 禁用拷貝賦值
    
    BinaryTree(BinaryTree&&) = default;                // 啟用移動
    BinaryTree& operator=(BinaryTree&&) = default;     // 啟用移動賦值
    
    // 深拷貝需顯式方法
    BinaryTree DeepCopy() const {
        BinaryTree copy;
        copy.root = Clone(root);
        return copy;  // 移動返回 (RVO/NRVO)
    }
    
private:
    unique_ptr<BTNode<T>> root;
    
    static unique_ptr<BTNode<T>> Clone(const unique_ptr<BTNode<T>>& node) {
        if (!node) return nullptr;
        auto copy = make_unique<BTNode<T>>(node->element);
        copy->left = Clone(node->left);
        copy->right = Clone(node->right);
        return copy;
    }
};

四、方案選擇決策矩陣

五、正確使用示例

// 方案一：深拷貝版本
void testDeepCopy() {
    BinaryTree<char> z;
    // ... 構建 z ...
    
    BinaryTree<char> k;           // 正確：預設構造
    z.Copy(k);                    // 正確：深拷貝到 k
    // 或：BinaryTree<char> k = z;  // 正確：拷貝構造深拷貝
    // 或：BinaryTree<char> k = z.DeepCopy();  // 顯式深拷貝
    
    k.PreOrder(Visit);            // 獨立遍歷
}  // k, z 依序析構，各自釋放自己的節點，無衝突

// 方案三：unique_ptr 版本
void testUniquePtr() {
    BinaryTree<char> z;
    // ... 構建 z ...
    
    // BinaryTree<char> k = z;  // 編譯錯誤：拷貝被刪除
    BinaryTree<char> k = z.DeepCopy();  // 正確：顯式深拷貝
    // 或：auto k = z.DeepCopy();        // C++17 CTAD
    
    k.PreOrder(Visit);
}

六、常見衍生問題與避坑

七、現代 C++ 最佳實踐總結

1. 優先使用智慧指標：unique_ptr 表達獨佔樹結構，shared_ptr 表達共享
2. 值語義類型實現 Rule of Five：析構、拷貝構造、拷貝賦值、移動構造、移動賦值
3. Copy-and-Swap 慣用法：拷貝賦值參數按值傳遞，swap 交換資源，異常安全、自處理自賦值
4. 移動操作標記 noexcept：讓 STL 容器優化重新分配時使用移動而非拷貝
5. 禁止隱式昂貴拷貝：大型樹結構用 = delete 禁用拷貝，提供顯式 DeepCopy()
6. 遞歸轉迭代：生產級代碼避免遞歸棧溢出，用顯式 std::stack

八、面試高頻考點

1. 淺拷貝 vs 深拷貝 區別與後果
2. Rule of Three / Five / Zero 原則
3. Copy-and-Swap 慣用法實現與優勢
4. 智慧指標如何解決資源管理問題
5. unique_ptr vs shared_ptr 選擇場景
6. 二叉樹拷貝的遞歸實現與記憶體安全

九、總結

二叉樹類包含動態分配節點指標，是 C++ 資源管理經典場景。**預設拷貝淺拷貝指標值**導致雙重釋放崩潰，是 C++ 初學者最高頻踩坑點。三大解決方案各有適用場景：

• 🏆 **現代首選**：unique_ptr 節點 + 禁用拷貝/啟用移動 + 顯式 DeepCopy()
• 🥈 **共享場景**：shared_ptr 節點 + 默認特殊成員函數 (Rule of Zero)
• 🥉 **傳統/教學**：完整 Rule of Five 深拷貝實現 (Copy-and-Swap)

核心原則：**誰分配、誰釋放、所有權清晰、編譯期強制**。掌握這些模式，不僅解決二叉樹拷貝問題，更能應對所有含動態資源類的設計挑戰。