C++ 二叉搜索树原理与高效实现

C++ 二叉搜索树原理与高效实现

一、二叉搜索树介绍

二叉搜索树（Binary Search Tree, BST）又称二叉排序树，是一种基础且强大的数据结构。它通过特定的节点排列规则实现了数据的有序存储，在算法设计与内存优化中扮演核心角色。

二、特点剖析

二叉搜索树可以为空树，其语言描绘特征如下：

1. 从根节点开始，左子节点的值小于父节点。
2. 从根节点开始，右子节点的值大于父节点。
3. 左右子树也分别为二叉搜索树。

三、二叉搜索树实现

（1）结构创建

实现一棵二叉搜索树，需要定义节点结构和功能结构。

节点结构包含左右子节点（left, right）和数据存储变量（data）。

（2）插入节点

插入节点需要根据数据的大小判断插在左右节点的 nullptr 位置。这里使用循环实现。

注意： 需要使用其他节点代替 node 去移动，否则 node 每次都不是指向根节点。

// 插入节点
void Insert(const T& data) {
    // 如果根节点为空
    if (node == nullptr) {
        node = new Node(data);
        return;
    }
    // 根据数据大小查找
    Node* parent = nullptr;
    Node* cur = node;
    while (cur) {
        // 记录父节点
        parent = cur;
        // 如果小于父节点
        if (data < cur->data) {
            cur = cur->left;
        } else {
            cur = cur->right;
        }
    }
    // 此时已经到了节点为空的位置
    // 如果小于父节点
    if (data < parent->data) {
        // 插在父节点左侧
        parent->left = new Node(data);
        return;
    } else {
        // 插在父节点右侧
        parent->right = new Node(data);
        return;
    }
}

（3）中序遍历

中序遍历调用递归完成：先遍历左子树，然后父节点，然后右子树。

// 中序遍历
void Inorder() {
    _Inorder(node);
}

void _Inorder(Node* ptr) {
    // 遇到空就返回
    if (ptr == nullptr) {
        return;
    }
    _Inorder(ptr->left);
    cout << ptr->data << " ";
    _Inorder(ptr->right);
}

（4）查找节点

找到对应节点之后，然后返回即可。根据要找的数据大小去查找，最多查找次数就是二叉树的深度次。

// 查找数据
bool Find(const T& data) {
    // 如果为空树，返回
    if (node == nullptr) {
        return false;
    }
    Node* cur = node;
    // 找节点
    while (cur) {
        // 如果 data 大于父节点，右边找，否则左边找
        if (data > cur->data) {
            cur = cur->right;
        } else if (data < cur->data) {
            cur = cur->left;
        } else {
            return true;
        }
    }
    // 如果出循环了还没有返回就说明没有找到
    return false;
}

（5）删除节点

删除节点需要考虑以下三种情况（重点是比较节点数据大小）：

1. 该节点无孩子节点：先删，然后置空。
2. 该节点有一个孩子节点：先连接再删。

   注意： 这两种情况可以概括为一类，参考下面代码注释。

3. 该节点有两个孩子节点：我们需要找一个特定大小的节点去替代它。

   替代思路：让它的左子树最大值或者右子树最小值去替换，然后删除它（以左子树 max 为例）。

解释： 例如下面这幅图，我们要删除 3。

1. 先找到目标节点 cur（3），然后找目标节点左子树的最大值 left_max。
2. 交换目标节点 cur 和最大值 left_max 的数据。
3. 这里需要标记 left_max 的父节点为 parent。

第一种情况：

1. 因为找的是左子树的最大值，所以只可能父节点 parent 的右边还存在子节点，将它连接在 parent 的右边。
2. 再将 cur 指向 left_max，删除。

第二种情况：

1. 因为找的是左子树的最大值，可能 parent 的左边还存在子节点。
2. 再将 cur 指向 left_max，删除。

（6）析构

我们可以利用上面的'删除节点' + '根节点是否为空循环'来不断析构。

注意： 上面我们的析构是利用第三方指针 cur 代替 node 删除的，所以当二叉树只有一个根节点删除后需要考虑置空，这样才可以利用到循环。

// 析构
~BST() {
    while (node) {
        Erase(node->data);
        cout << "删除成功" << endl;
    }
}

（7）拷贝构造

拷贝构造可以利用递归遍历不断开新节点。

注意： 递归左右节点时要连接起来。

// 拷贝构造
BST(const BST<T>& ptr) {
    // 如果拷贝对象是空
    if (ptr.node == nullptr) {
        return;
    }
    // 这里的 ptr 是拷贝的对象，node 是待拷贝的对象的根节点
    node = Copy(node, ptr.node);
}

Node* Copy(Node* _node, Node* copy_node) {
    if (copy_node == nullptr) {
        return nullptr;
    }
    // 前序拷贝
    _node = new Node(copy_node->data);
    // 空间是开辟成功了，但是这里 node 的左右子树，没有连接，需要接收 copy 的返回值才能完成连接
    _node->left = Copy(_node->left, copy_node->left);
    _node->right = Copy(_node->right, copy_node->right);
    // 返回根节点
    return _node;
}