【C++】二叉搜索树深拷贝的致命陷阱：如何用前序遍历解决90%程序员的内存崩溃难题

我不是呆头

发布于 2025-12-20 14:38:25

170

摘要

本文以 “Key 结构→KeyValue 结构” 为演进主线，完整实现了两种结构的非递归与递归操作（插入、查找、删除），并针对默认成员函数（拷贝构造、赋值运算符重载、析构）的深拷贝需求，设计了基于前序遍历的拷贝逻辑、“拷贝 - 交换” 的赋值技法及后序遍历的销毁逻辑，同时结合 “小区车库车牌验证”“单词拼写检查”“中英互译字典” 等实际场景，清晰区分两种结构的适用范围，为 BST 的工程化应用提供了可直接复用的代码模板与逻辑指导。

一、key结构的默认成员函数

1. 拷贝构造函数

在二叉搜索树的默认成员函数里，拷贝构造函数是必须重点处理的部分。要是我们不手动实现，编译器生成的默认拷贝构造函数会采用浅拷贝（按字节序复制），但二叉搜索树的节点都是通过new从堆区分配的，这就会导致拷贝后的对象和原对象指向同一块堆内存——等两个对象析构时，同一块内存会被释放两次，最终引发程序崩溃，所以必须显式手写拷贝构造函数。

比如我们有棵二叉搜索树t1，它的根节点是用new在堆里创建的（存着值8），t1的_root指针就指向这块堆内存。当我们用默认拷贝构造函数创建t2（BSTree t2(t1)）时，浅拷贝只会让t2的_root也指向t1._root那同一块堆内存，而不会新new一块空间存8。等程序结束，t1析构时会把这块堆内存释放掉，可t2析构时还会去释放同一个地址，这就造成了内存二次释放，程序直接崩溃。

实现拷贝的核心是复制原树的节点和结构，关键要正确获取节点的_key并重新分配堆空间。有人可能会想到用之前的中序遍历拿_key，但中序遍历二叉搜索树得到的是升序序列（比如原树中序是1 3 4 6 7 8 10 13 14），按这个序列new节点链接的话，拷贝树的根节点会变成1（而非原树的8），整个树的结构会完全错乱，所以中序遍历不可行。
真正合适的是前序遍历，因为前序遍历按“根→左→右”的顺序，能完整保留原树结构（比如原树前序是8 3 1 6 4 7 10 14 13），按这个序列new节点，拷贝树的根节点和结构都能和原树一致。但拷贝构造函数本身没法递归（没有返回值，不能传递子树指针），所以需要设计一个私有成员函数Copy来辅助——设为私有是为了不让外部调用，只允许类内部使用。
Copy函数的逻辑很清晰：它接收原树待拷贝节点的指针（比如copy），返回值是BSTNode*类型（拷贝后子树的根指针）。当copy是nullptr时，直接返回nullptr（不用拷贝）；当copy不为空时，先new一个新节点，把copy的_key赋给新节点，再递归调用Copy(copy->_left)拷贝左子树，把返回的指针赋给新节点的_left，接着递归Copy(copy->_right)拷贝右子树，赋值给新节点的_right，最后返回这个新节点。

比如原二叉搜索树里有个节点copyNode，存着值8，它的左孩子是存3的节点，右孩子是存10的节点。调用Copy(copyNode)时，先new一个新节点存8；接着递归调用Copy(copyNode->_left)去拷贝左孩子，得到存3的新节点指针，把它赋给新节点的_left；再递归Copy(copyNode->_right)拷贝右孩子，得到存10的新节点指针，赋给新节点的_right；最后返回这个存8的新节点——这样就完整拷贝出以8为根的子树，和原树结构、值都一样。要是copyNode是nullptr（比如原节点没有左孩子），就直接返回nullptr，不用创建新节点。

最后在拷贝构造函数里，只要调用Copy(原树的_root)，再把返回的指针赋值给当前对象的_root，就能完成深拷贝——这样拷贝后的树和原树完全独立，不会有内存访问冲突。

public:
    // 拷贝构造函数：用已存在的二叉搜索树t（被拷贝的原树），初始化新创建的二叉搜索树对象（当前对象）
    // 参数说明：
    //   const BinarySearchTree<K>& t：被拷贝的原树，加const是为了防止函数内意外修改原树数据
    //   加&（引用）是为了避免传值时调用自身拷贝构造函数，导致递归死循环
    // 功能：通过调用Copy函数拷贝原树的所有节点，最终让当前对象的_root指向拷贝后的新树根节点
    BinarySearchTree(const BinarySearchTree<K>& t)
    {
        // 调用Copy函数，传入原树的根节点t._root，返回的新根节点赋值给当前对象的_root
        _root = Copy(t._root);
    }

private:
    // 递归拷贝子函数：负责深度拷贝原树的单个节点及其左右子树，返回拷贝后的新节点指针
    // 参数说明：
    //   const BSTNode* copy：原树中当前要拷贝的节点，加const防止修改原树节点的_key和子树指针
    // 返回值：拷贝完成的新节点指针，用于给父节点的_left/_right赋值，构建新树的结构
    BSTNode* Copy(const BSTNode* copy)
    {
        // 递归终止条件：如果原树当前要拷贝的节点copy是空（比如原树的叶子节点的子节点）
        // 说明没有节点可拷贝，直接返回空指针，避免后续无效操作
        if (copy == nullptr) 
        { 
            return nullptr; 
        }

        // 步骤1：拷贝当前节点——为新树创建一个新节点，值与原树copy节点的_key完全相同
        // 此时新节点的_left和_right默认是nullptr，后续通过递归赋值
        BSTNode* newNode = new BSTNode(copy->_key);

        // 步骤2：递归拷贝左子树——用原树copy节点的左子节点（copy->_left），构建新节点的左子树
        // 原理：Copy(copy->_left)会返回拷贝后的左子树根节点，将其赋值给newNode->_left，完成左子树链接
        newNode->_left = Copy(copy->_left);

        // 步骤3：递归拷贝右子树——用原树copy节点的右子节点（copy->_right），构建新节点的右子树
        // 原理：与左子树拷贝一致，Copy(copy->_right)返回拷贝后的右子树根节点，赋值给newNode->_right
        newNode->_right = Copy(copy->_right);

        // 步骤4：返回当前拷贝好的新节点（newNode）
        // 这个返回值会被父节点的_left或_right接收，最终层层递归构建出完整的新树
        return newNode;
    }

2. 赋值运算符重载函数

如果我们不写赋值运算符重载，编译器同样的默认生成为浅拷贝，我们需要我们自己写一个深拷贝的赋值运算符重载函数。

BinarySearchTree<K>& operator=(BinarySearchTree<K> t)  // 注意参数是值传递
{
    swap(_root, t._root);  // 交换当前对象与临时对象的根节点
    return *this;          // 返回当前对象
}

当调用赋值运算符时（例如 t1 = t2），参数 t 是通过值传递接收的。这会自动调用我们之前实现的拷贝构造函数，将 t2 深拷贝一份到临时对象 t 中（t 拥有独立的堆内存节点，与 t2 完全分离）。
swap(_root, t._root) 这行代码会交换两个指针：

当前对象（t1）的 _root 指向临时对象 t 的深拷贝数据（新节点）。临时对象 t 的 _root 指向当前对象原来有的数据（旧节点）。

析构阶段：自动释放旧数据 当赋值函数执行结束时，临时对象 t 会被销毁（超出作用域）。

此时会调用析构函数，释放 t 所持有的的“旧数据”（原来属于 t1 的节点），无需手动释放，完美避免内存泄漏。

假设 t2 是一棵有节点 8→3→10 的树，执行 t1 = t2 时：

先通过拷贝构造创建 t（t 是 t2 的深拷贝，节点地址全新）。
交换后，t1._root 指向 t 的新节点（8→3→10），t._root 指向 t1 原来的旧节点。
函数结束，t 被销毁，顺带释放 t1 的旧节点，t1 最终持有 t2 的深拷贝数据。

3. 析构函数

在二叉搜索树中，所有节点都是通过 new 动态分配在堆上的，因此必须显式定义析构函数来逐个释放节点内存。析构过程需要采用后序遍历（左→右→根），确保在删除父节点前，其所有子节点已被释放。
由于析构函数只能操作 this 对象本身，无法直接访问子节点对象去调用它们的析构函数，需要辅助函数来控制递归参数(传入不同的节点指针)，因此需要创建辅助销毁函数 Destroy，这里我们需要使用节点指针的引用作为参数：因为要修改二叉树中的指针（如 _root、left、right）所以采用指针的引用，可以直接影响原始树结构。
递归逻辑

1. 若节点为空 → 直接返回
2. 递归销毁左子树
3. 递归销毁右子树
4. 删除当前节点
5. 置空当前节点指针

假设有如下二叉搜索树：

销毁顺序（后序遍历）：

删除节点 1 → 3->left = nullptr
删除节点 3 → 5->left = nullptr
删除节点 6 → 7->left = nullptr
删除节点 9 → 7->right = nullptr
删除节点 7 → 5->right = nullptr
删除节点 5 → _root = nullptr

puclic:
	~BinarySearchTree()
	{
		Destory(_root);
	}
private:
	void Destory(BSTNode*& root)
	{
		if (root == nullptr){return;}

		Destory(root->_left);
		Destory(root->_right);

		delete root;
		root = nullptr;
	}

二、二叉搜索树key结构和key/val结构使用场景

当二叉搜索树仅以key作为关键码，且结构中只存储key时，它能支持核心的增、删、查操作，但不支持修改操作——因为修改key会直接破坏二叉搜索树“左子树key小于根、右子树key大于根”的结构特性，导致后续搜索逻辑失效。这类二叉搜索树的核心作用，就是判断目标key是否存在于集合中，适用于多种“存在性验证”场景。

比如小区无人值守车库场景，物业会将购买车位的业主车牌号作为key，录入二叉搜索树后台系统。当车辆进入时，系统扫描车牌并在树中查找对应的key：若key存在，说明是本小区有车位的业主车辆，自动抬杆放行；若key不存在，则判定为非本小区车辆，弹出提示禁止进入。
再比如英文文章单词拼写检查场景，会先将标准词库中的所有单词作为key存入二叉搜索树。当读取文章中的每个单词时，都会在树中搜索对应的key：若key存在，说明单词拼写正确，正常显示；若key不存在，则通过波浪线标红的方式，提示用户该单词可能存在拼写错误。

当二叉搜索树的节点同时存储关键码key和对应的值value（value可设为任意类型）时，增、删、查操作仍以key为核心遵循二叉搜索树规则，通过key的大小比较快速定位节点，进而获取对应的value。这类树支持修改操作，但仅能修改value——修改key会打破“左子树key小于根、右子树key大于根”的结构特性，导致后续搜索逻辑失效。

在简单中英互译字典场景中，二叉搜索树的节点会存储key（英文单词）和value（对应的中文释义）。当需要翻译时，输入英文单词作为key在树中搜索，找到匹配节点后，即可直接获取对应的value（中文释义），实现快速互译。
商场无人值守车库场景也适用这类树：车辆入场时，系统扫描车牌作为key，将入场时间作为value存入树中；车辆离场时，再次扫描车牌定位到对应的节点，读取value（入场时间），用当前时间减去入场时间计算停车时长，进而算出停车费用，用户缴费后系统抬杆放行，整个过程通过key快速关联关键信息，提升通行效率。
统计文章单词出现次数时，同样可借助该结构：读取文章中的每个单词作为key在树中查找，若key不存在，说明单词首次出现，以“单词为key、1为value”创建新节点存入树中；若key已存在，则直接找到对应节点，将value（出现次数）加1，最终遍历树即可得到所有单词的出现频次，实现高效统计。

三、key/val结构的模拟实现以及和key结构的对比

对比维度	Key 版本	Key-Value 版本
应用场景	集合(Set)：去重、查找存在性	字典(Map)：键值映射、缓存
节点数据	仅存储键 _key	存储键值对 _key + _value
模板参数	template<class K>	template<class K, class V>
插入操作	键重复则拒绝	键重复时可选择更新值
查找返回	bool（存在性）	BSTNode*（访问值）
使用复杂度	简单，只需传键	略复杂，需同时传键和值

#include<iostream>
using namespace std;

namespace dh
{
    // 模板声明,K为键类型,V为值类型
    template<class K, class V>
    // 定义节点结构体
    struct BinarySearchTreeNode
    {
        typedef BinarySearchTreeNode<K, V> BSTNode;

        BSTNode* _left;      // 左子节点指针
        BSTNode* _right;     // 右子节点指针
        K _key;              // 键
        V _value;            // 值

        // 构造函数:初始化键值对
        BinarySearchTreeNode(const K& key, const V& value)
            : _left(nullptr)
            , _right(nullptr)
            , _key(key)
            , _value(value)
        {
        }
    };

    template<class K, class V>
    class BinarySearchTree
    {
    public:
        typedef BinarySearchTreeNode<K, V> BSTNode;

        // 构造函数
        BinarySearchTree()
            : _root(nullptr)
        {
        }

        // ==================== 非递归实现 ====================

        // 非递归插入
        bool Insert(const K& key, const V& value)
        {
            if (_root == nullptr)
            {
                _root = new BSTNode(key, value);
                return true;
            }

            BSTNode* parent = nullptr;
            BSTNode* cur = _root;

            while (cur != nullptr)
            {
                if (key > cur->_key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (key < cur->_key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    // 键已存在,更新值
                    cur->_value = value;
                    return false;
                }
            }

            // 插入新节点
            if (key > parent->_key)
                parent->_right = new BSTNode(key, value);
            else
                parent->_left = new BSTNode(key, value);

            return true;
        }

        // 非递归查找 - 返回指针,方便获取value
        BSTNode* Find(const K& key)
        {
            BSTNode* cur = _root;

            while (cur != nullptr)
            {
                if (key > cur->_key)
                    cur = cur->_right;
                else if (key < cur->_key)
                    cur = cur->_left;
                else
                    return cur;  // 找到返回节点指针
            }

            return nullptr;  // 未找到
        }

        // 非递归删除
        bool Erase(const K& key)
        {
            BSTNode* parent = nullptr;
            BSTNode* cur = _root;

            // 查找目标节点
            while (cur != nullptr)
            {
                if (key > cur->_key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (key < cur->_key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else  // 找到目标节点
                {
                    // 情况1: 右子树为空
                    if (cur->_right == nullptr)
                    {
                        if (parent == nullptr)  // 删除根节点
                            _root = cur->_left;
                        else
                        {
                            if (key > parent->_key)
                                parent->_right = cur->_left;
                            else
                                parent->_left = cur->_left;
                        }
                    }
                    // 情况2: 左子树为空
                    else if (cur->_left == nullptr)
                    {
                        if (parent == nullptr)  // 删除根节点
                            _root = cur->_right;
                        else
                        {
                            if (key > parent->_key)
                                parent->_right = cur->_right;
                            else
                                parent->_left = cur->_right;
                        }
                    }
                    // 情况3: 左右子树都存在(替换法)
                    else
                    {
                        // 找左子树最大节点
                        BSTNode* subMaxParent = cur;
                        BSTNode* subMax = cur->_left;

                        while (subMax->_right != nullptr)
                        {
                            subMaxParent = subMax;
                            subMax = subMax->_right;
                        }

                        // 替换键值对
                        cur->_key = subMax->_key;
                        cur->_value = subMax->_value;

                        // 删除替换节点
                        if (subMaxParent == cur)
                            subMaxParent->_left = subMax->_left;
                        else
                            subMaxParent->_right = subMax->_left;

                        cur = subMax;  // 转移删除目标
                    }

                    delete cur;
                    return true;
                }
            }

            return false;  // 未找到
        }

        // ==================== 递归实现 ====================

        // 递归插入
        bool InsertR(const K& key, const V& value)
        {
            return _InsertR(_root, key, value);
        }

        // 递归查找
        BSTNode* FindR(const K& key)
        {
            return _FindR(_root, key);
        }

        // 递归删除
        bool EraseR(const K& key)
        {
            return _EraseR(_root, key);
        }

        // ==================== 遍历 ====================

        // 中序遍历
        void InOrder()
        {
            _InOrder(_root);
            cout << endl;
        }

        // ==================== 拷贝控制 ====================

        // 拷贝构造
        BinarySearchTree(const BinarySearchTree<K, V>& t)
        {
            _root = Copy(t._root);
        }

        // 赋值运算符重载
        BinarySearchTree<K, V>& operator=(BinarySearchTree<K, V> t)
        {
            swap(_root, t._root);
            return *this;
        }

        // 析构函数
        ~BinarySearchTree()
        {
            Destroy(_root);
        }

    private:
        BSTNode* _root;

        // ==================== 私有递归辅助函数 ====================

        // 递归插入辅助
        bool _InsertR(BSTNode*& root, const K& key, const V& value)
        {
            if (root == nullptr)
            {
                root = new BSTNode(key, value);
                return true;
            }

            if (key > root->_key)
                return _InsertR(root->_right, key, value);
            else if (key < root->_key)
                return _InsertR(root->_left, key, value);
            else
            {
                // 键已存在,更新值
                root->_value = value;
                return false;
            }
        }

        // 递归查找辅助
        BSTNode* _FindR(BSTNode* root, const K& key)
        {
            if (root == nullptr)
                return nullptr;

            if (key > root->_key)
                return _FindR(root->_right, key);
            else if (key < root->_key)
                return _FindR(root->_left, key);
            else
                return root;
        }

        // 递归删除辅助
        bool _EraseR(BSTNode*& root, const K& key)
        {
            if (root == nullptr)
                return false;

            if (key > root->_key)
                return _EraseR(root->_right, key);
            else if (key < root->_key)
                return _EraseR(root->_left, key);
            else  // 找到目标节点
            {
                BSTNode* delNode = root;

                // 右子树为空
                if (root->_right == nullptr)
                {
                    root = root->_left;
                    delete delNode;
                    return true;
                }
                // 左子树为空
                else if (root->_left == nullptr)
                {
                    root = root->_right;
                    delete delNode;
                    return true;
                }
                // 左右都存在
                else
                {
                    // 找左子树最大节点
                    BSTNode* subMax = root->_left;
                    while (subMax->_right)
                        subMax = subMax->_right;

                    // 替换键值对
                    root->_key = subMax->_key;
                    root->_value = subMax->_value;

                    // 递归删除替换节点
                    return _EraseR(root->_left, subMax->_key);
                }
            }
        }

        // 中序遍历辅助
        void _InOrder(BSTNode* cur)
        {
            if (cur == nullptr)
                return;

            _InOrder(cur->_left);
            cout << cur->_key << ":" << cur->_value << " ";
            _InOrder(cur->_right);
        }

        // 拷贝辅助
        BSTNode* Copy(const BSTNode* copy)
        {
            if (copy == nullptr)
                return nullptr;

            BSTNode* newNode = new BSTNode(copy->_key, copy->_value);
            newNode->_left = Copy(copy->_left);
            newNode->_right = Copy(copy->_right);

            return newNode;
        }

        // 销毁辅助
        void Destroy(BSTNode*& root)
        {
            if (root == nullptr)
                return;

            Destroy(root->_left);
            Destroy(root->_right);

            delete root;
            root = nullptr;
        }
    };
}

总结

通过对二叉搜索树key结构和key/value结构的深入剖析，我们不仅掌握了拷贝控制成员函数的正确实现方式，理解了深拷贝的必要性和实现技巧，还明确了两种结构在实际应用中的定位差异——key结构专注于集合操作和存在性判断，而key/value结构则更适用于字典映射和关联数据存储。这些核心知识点为后续学习更复杂的树形结构（如AVL树、红黑树）奠定了坚实的理论基础和实践指导。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-12-09，如有侵权请联系 cloudcommunity@tencent.com 删除

c++