一篇文章教会你什么是二叉搜索树（上）

二叉搜索树概念

二叉搜索树（Binary Search Tree，BST）是一种二叉树的特殊形式，它具有以下关键性质：

1. 有序性：每个节点都包含一个值，且左子树中的所有节点的值都小于等于该节点的值，右子树中的所有节点的值都大于等于该节点的值。这意味着对于任何节点，它的左子树都包含比它小的值，右子树都包含比它大的值。
2. 递归性质：整棵二叉搜索树本身也是一个二叉搜索树，因为它的左子树和右子树也满足二叉搜索树的性质。这意味着可以递归地应用相同的规则来构建和操作树。
3. 无重复值：通常，BST中不允许包含重复的值。每个值在树中只能出现一次。

由于这些性质，二叉搜索树在很多应用中都非常有用，尤其是在需要高效地进行搜索、插入和删除操作的情况下。

以下是一些关于二叉搜索树的详细解释：

1. 插入操作：

• 插入操作从根节点开始，根据节点值的大小逐步向下搜索树，直到找到一个合适的位置插入新节点。
• 如果要插入的值小于当前节点的值，就继续在左子树中搜索，否则在右子树中搜索，直到找到一个空位置插入新节点。

2. 搜索操作：

• 搜索操作也从根节点开始，根据节点值的大小逐步向下搜索树。
• 如果要搜索的值等于当前节点的值，就找到了目标节点。
• 如果要搜索的值小于当前节点的值，就在左子树中搜索；如果大于当前节点的值，就在右子树中搜索。
• 如果一直搜索到叶子节点仍然没有找到目标值，则说明目标值不在树中。

3. 删除操作：

• 删除操作通常比较复杂，因为需要考虑多种情况。删除节点时有以下几种情况：

• 被删除节点是叶子节点（没有子节点）：直接删除即可。
• 被删除节点有一个子节点：将子节点替换为被删除节点的位置。
• 被删除节点有两个子节点：找到被删除节点的中序遍历前驱或后继节点，用其值替换被删除节点的值，然后递归删除前驱或后继节点。

4. 遍历操作：

• 二叉搜索树可以通过不同的遍历方式进行访问，包括中序遍历、前序遍历和后序遍历。
• 中序遍历可以按照升序顺序遍历树中的所有节点，因为它首先遍历左子树，然后当前节点，最后右子树。

5. 平衡性：

• 当二叉搜索树的高度不平衡时，搜索、插入和删除操作的时间复杂度可能会退化为O(n)，其中n是节点数。为了避免这种情况，通常使用平衡二叉搜索树（如AVL树或红黑树）来确保树的高度保持在较小的范围内。

总之，二叉搜索树是一种基于节点值大小有序排列的二叉树，它支持高效的搜索、插入和删除操作，但需要注意平衡性问题以避免性能退化。

二叉搜索树操作

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

1.二叉搜索树的查找

在二叉查找树b中查找x的过程为：

1. 若b是空树，则搜索失败，否则：
2. 若x等于b的根节点的数据域之值，则查找成功；否则：
3. 若x小于b的根节点的数据域之值，则搜索左子树；否则：
4. 查找右子树

2.二叉搜索树的插入

向一个二叉搜索树b中插入一个节点s的算法，过程为：

1. 若b是空树，则将s所指节点作为根节点插入，否则：
2. 若s->data等于b的根节点的数据域之值，则返回，否则：
3. 若s->data小于b的根节点的数据域之值，则把s所指节点插入到左子树中，否则：
4. 把s所指节点插入到右子树中。（新插入节点总是叶子节点）

3.二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：

a. 要删除的结点无孩子结点

b. 要删除的结点只有左孩子结点

c. 要删除的结点只有右孩子结点

d. 要删除的结点有左、右孩子结点

看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：

情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除

情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除

情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题–替换法删除

4.二叉搜索树的遍历

二叉搜索树的遍历最常用的是中序遍历，因为二叉搜索树（BST）的中序遍历结果是升序的。中序遍历是一种遍历二叉树的方式，按照以下规则进行：

1. 首先遍历左子树。
2. 然后遍历当前节点。
3. 最后遍历右子树。

由于BST的性质，即左子树的值都小于当前节点的值，右子树的值都大于当前节点的值，所以中序遍历的过程中，首先访问左子树，然后访问当前节点，最后访问右子树。这导致中序遍历结果是按照升序排列的。

因此，中序遍历是一种有助于获取BST中所有节点按升序排列的有效方法。这个性质也是BST在进行搜索操作时能够快速定位目标值的关键之一。

二叉搜索树的实现

1.二叉搜索树节点结构

template<class K>
struct BSTreeNode
{
  BSTreeNode<K>* _left;
  BSTreeNode<K>* _right;
  K _key;
  BSTreeNode(const K& key)
    :_left(nullptr)
    , _right(nullptr)
    , _key(key)
  {}
};

1. _left：指向左子节点的指针。
2. _right：指向右子节点的指针。
3. _key：存储节点的关键字或值。

每个节点都有一个关键字 _key，用来表示节点在二叉搜索树中的位置。这个关键字通常是用来比较节点的大小，以便将节点插入到正确的位置，以满足二叉搜索树的性质。根据节点关键字的大小，节点将被放置在左子树或右子树中。

这是一个模板类，它可以用于创建不同类型的二叉搜索树，只需指定不同的关键字类型 K 即可。这使得代码更加通用，可以适用于不同类型的数据。

2.二叉搜索树类

template<class K>
class BSTree
{
  typedef BSTreeNode<K> Node;
private:
  Node* _root = nullptr;
}

二叉搜索树（Binary Search Tree，BST）类模板 BSTree 的定义。这个类包含一个私有成员 _root，它是指向树的根节点的指针。

• template<class K>：这是一个类模板声明，使用了模板参数 K，它表示关键字或值的数据类型。这允许你在创建 BSTree 实例时指定不同的数据类型。
• typedef BSTreeNode<K> Node;：这行代码用于定义一个别名 Node，它是 BSTreeNode<K> 类的别名。这个别名使得在类中使用节点类型更加方便。
• Node* _root = nullptr;：这是一个指向根节点的指针 _root，它初始化为 nullptr，表示树开始为空树。

3.二叉搜索树的构造及析构

构造函数

BSTree() = default;

BSTree() = default; 是C++中的默认构造函数的声明方式。这行代码表示你正在声明一个默认构造函数（无参数的构造函数），并使用 = default 表示使用默认的构造函数实现。

默认构造函数是一个特殊的构造函数，它在对象创建时被自动调用，不接受任何参数。默认构造函数的主要作用是初始化对象的成员变量，确保对象在创建后处于一个合法的初始状态。

使用 = default 表示你希望编译器生成默认的构造函数实现，而不需要自己编写构造函数的定义。这通常用于以下情况：

1. 你的类不需要特殊的构造逻辑，只需要成员变量的默认初始化。
2. 你想确保编译器生成默认构造函数，以便可以在不提供自定义构造函数的情况下创建对象。

这里需要注意的是在C++中，如果你提供了自定义的拷贝构造函数，编译器通常不会再自动生成默认的拷贝构造函数，所以我们需要再将默认构造自定义提供

析构函数

~BSTree()
{
    _Destory(_root);
}
private:
  void _Destory(Node*& root)
    {
        if (root == nullptr)
        {
            return;
        }
        _Destory(root->_left);
        _Destory(root->_right);
        delete root;
        root = nullptr;
    }

1. ~BSTree()

• 这是BST类的析构函数。析构函数在对象被销毁时自动调用，用于执行清理和释放资源的操作。
• 在这个析构函数中，它调用了私有辅助函数 _Destory(_root)，传递根节点 _root 作为参数，开始递归地销毁整棵树。

2. _Destory(Node*& root)

• 这是一个递归辅助函数，用于销毁二叉搜索树中的节点。
• 函数接受一个指向节点指针的引用作为参数，以便可以修改节点指针，将其设置为 nullptr，以避免悬挂指针问题。
• 函数首先检查节点是否为空。如果节点为空，表示已经到达树的底部，函数直接返回，不执行任何操作。
• 如果节点不为空，函数递归地调用自己来销毁左子树和右子树。
• 然后，函数删除当前节点，释放节点的内存。
• 最后，将当前节点指针设置为 nullptr，以确保不会再访问已释放的节点。

这样，当你销毁BST对象时，析构函数会从根节点开始递归地销毁整棵树，确保释放所有节点的内存，防止内存泄漏。这是一种正确释放资源的方式，以确保程序的健壮性。

4.二叉搜索树的拷贝构造及赋值重载

拷贝构造

BSTree(const BSTree<K>& t)
{
    _root = _Copy(t._root);
}
private:
    Node* _Copy(Node* root)
    {
        if (root == nullptr)
        {
            return nullptr;
        }
        Node* copyRoot = new Node(root->_key);
        copyRoot->_left = _Copy(root->_left);
        copyRoot->_right = _Copy(root->_right);
        return copyRoot;
    }

1. BSTree(const BSTree<K>& t)

• 这是拷贝构造函数，它用于创建一个新的BST对象，该对象是根据另一个BST对象 t 进行拷贝构造的。
• 在构造函数内部，它调用了私有的辅助函数 _Copy(t._root)，传递 t 的根节点 _root 作为参数，从而创建了一个新的BST。

2. _Copy(Node* root)

• 这是一个递归辅助函数，用于复制一棵二叉树。
• 如果传入的根节点 root 为空（nullptr），则返回 nullptr，表示空树。
• 如果根节点不为空，函数首先创建一个新的节点 copyRoot，并将其关键字设置为 root 节点的关键字。
• 然后，函数递归地调用自己来复制左子树和右子树，并将它们分别赋值给 copyRoot->_left 和 copyRoot->_right。
• 最后，返回 copyRoot，这样递归过程会构建出一棵与原始树相同结构和内容的树。

这样，拷贝构造函数 _Copy 会递归地复制整棵树，确保你创建的新BST对象与原始对象具有相同的结构和内容。这对于在不破坏原始树的情况下创建一个新树非常有用。