Posted in技术指南

打破编程瓶颈！掌握二叉搜索树的高效实现与技巧

No Comments
打破编程瓶颈！掌握二叉搜索树的高效实现与技巧

摘要

本文详细探讨了二叉搜索树（Binary Search Tree, BST）的核心概念和技术细节，包括插入、查找、删除、遍历等基本操作，并结合实际代码演示了如何实现这些功能。文章深入分析了二叉搜索树的性能优势及其时间复杂度，同时介绍了前驱、后继的查找方法等高级功能。通过自定义实现的二叉搜索树类，读者能够掌握其实际应用，此外，文章还建议进一步扩展为平衡树（如 AVL 树、红黑树）以优化极端情况下的性能退化。

  

1、引言

二叉搜索树（Binary Search Tree, 简称 BST）是计算机科学中非常重要的树形数据结构之一。它能够高效地存储和管理有序数据，并允许快速查找、插入和删除操作。二叉搜索树在很多实际应用中都有使用，比如数据库索引、文件系统、搜索引擎等。理解并掌握二叉搜索树及其实现是学习数据结构和算法的基础之一。

本博客将详细介绍二叉搜索树的概念、性质、常见操作的实现方法、如何优化、平衡性问题，以及各种遍历算法。文章还会提供详细的 C++ 实现，帮助读者深度理解二叉搜索树的内部机制和实际应用场景。

  

这篇博客所涉及的所有代码可以从我的代码仓库获得：https://git.lenyiin.com/Lenyiin/BSTree

  

2、什么是二叉搜索树？

二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树，它的主要特点是每个节点的左子树节点值小于根节点，右子树节点值大于根节点。这种结构使得二叉搜索树具备高效查找、插入和删除操作的能力，特别是在数据有序的场景中，二叉搜索树表现出优越的性能。

定义：

  • 二叉树： 每个节点最多有两个子节点，分别为左子节点和右子节点。
  • 二叉搜索树： 对于任意一个节点，其左子树的所有节点的值都小于该节点的值，右子树的所有节点的值都大于该节点的值。

2.1、为什么要使用二叉搜索树？

二叉搜索树的设计初衷是为了快速进行查找、插入和删除操作。在平衡的二叉搜索树中，这些操作的时间复杂度为 O(log⁡n)，大大优于链表的线性时间复杂度 O(n) 。因此，BST 在需要高效查询和动态维护数据的场景下非常有用。

2.2、二叉搜索树的概念扩展

二叉搜索树可以视为递归数据结构，因为每个子树本身也是一棵二叉搜索树。这种递归性质不仅体现在树的定义上，还反映在二叉搜索树的各类操作上，如插入、查找和删除操作中。

例如，如果我们要在二叉搜索树中查找一个值，从根节点开始，首先将该值与根节点的值进行比较。如果目标值小于根节点，则递归查找左子树；如果大于根节点，则递归查找右子树。这种递归的性质使得二叉搜索树具有灵活且高效的查询能力。

  

3、二叉搜索树的性质

要更深入理解二叉搜索树的运作机制，首先要掌握其几个核心性质：

  1. 递归性： 对于每个节点，其左子树和右子树都是二叉搜索树，这种递归结构是二叉搜索树的一个重要特征。
  2. 有序性： 对于任意节点 N，左子树中所有节点的值都小于 N 的值，右子树中所有节点的值都大于 N 的值。这个特性使得二叉搜索树在查找时可以快速定位节点。
  3. 动态性： 二叉搜索树可以根据插入和删除操作自动调整其结构，适应数据的动态变化，保证树的有序性。

3.1、树的高度

树的高度是指从根节点到叶子节点的最长路径所包含的节点数。在理想情况下，二叉搜索树是平衡的，其高度接近 log⁡n（n 为节点数）。然而，如果插入数据是有序的，二叉搜索树可能退化成链表，此时树的高度为 O(n)，这会导致查找、插入和删除操作的性能急剧下降。

3.2、平衡性问题

理想的二叉搜索树应该尽量保持平衡，即左右子树的高度差不能过大。否则，树的性能会退化。为了保证树的平衡性，有一些自平衡二叉搜索树如 AVL 树和红黑树，它们在插入和删除操作后自动调整树的结构，保持平衡。

  

4、搜索二叉树的数据成员的设计与初始化

要实现一个搜索二叉树，我们首先定义一个表示搜索二叉树节点的结构体。该结构体包含四个重要成员：键值 _key，存储数据的 _value，指向左孩子节点的 _left 指针，以及指向右孩子节点的 _right 指针。我们可以使用一个模板类来实现这一结构，使得该搜索二叉树能够存储任何类型的元素。

namespace Lenyiin
{
    template <class K, class V>
    struct BSTreeNode
    {
        BSTreeNode(const K& key = K(), const V& value = V())
            : _key(key), _value(value), _left(nullptr), _right(nullptr)
        {
        }

        K _key;
        V _value;
        BSTreeNode<K, V>* _left;
        BSTreeNode<K, V>* _right;
    };

    template <class K, class V>
    class BSTree
    {
    private:
        typedef BSTreeNode<K, V> Node;

        Node* _Copy(Node* root)
        {
            if (root == nullptr)
            {
                return nullptr;
            }

            Node* cur = new Node(root->_key, root->_value);
            cur->_left = _Copy(root->_left);
            cur->_right = _Copy(root->_right);

            return cur;
        }

    public:
        // 默认构造
        BSTree()
            : _root(nullptr)
        {}

        // 拷贝构造
        BSTree(const BSTree<K, V>& tree)
        {
            _root = _Copy(tree._root);
        }

    private:
        Node* _root = nullptr;
    };
}

  

5、二叉搜索树的基本操作

二叉搜索树（BST）的基本操作如插入、查找、删除等都具有递归和非递归两种实现方式。理解不同实现的优缺点，有助于我们在具体项目中进行更合理的选择。在本节中，我们将探讨 BST 实现的一些细节，包括递归与非递归的差异、内存管理、树的高度对性能的影响等。

递归实现二叉搜索树的各种操作代码简洁，易于理解，并且自然契合树的递归结构。然而，递归在栈空间的使用上有一定的限制，可能在深度很大的树上引发栈溢出问题。非递归实现则通过显式使用栈或队列来避免递归的栈空间限制，但代码可能相对复杂一些。

以下是详细的操作分析及其实现。

5.1、插入操作

插入操作是 BST 中最常见的操作之一。插入新节点时，我们从根节点开始，逐步比较新节点的值与当前节点的值：

  • 如果待插入的值小于当前节点，移动到左子树；

  • 如果大于当前节点，移动到右子树；

  • 如果为空位置，则插入新节点。

5.1.1、递归插入操作实现

// 辅助函数
Node* _insert(Node* root, const K& key, const V& value)
{
    if (root == nullptr)
    {
        return new Node(key, value);
    }
    if (key < root->_key)
    {
        root->_left = _insert(root->_left, key, value);
    }
    else if (key > root->_key)
    {
        root->_right = _insert(root->_right, key, value);
    }
    return root;
}

// 插入
void Insert(const K& key, const V& value)
{
    _root = _insert(_root, key, value);
}

插入操作解析：

  1. 递归检查当前节点是否为空。如果为空，则创建新节点并返回。
  2. 如果要插入的值小于当前节点的值，则递归插入左子树；如果大于当前节点的值，则递归插入右子树。

递归的核心思想是通过递归函数返回树的左、右子树，逐步形成最终的完整树。

5.1.2、非递归插入操作实现

// 插入
bool Insert(const K& key, const V& value)
{
    // 如果根为空, 直接插入
    if (_root == nullptr)
    {
        _root = new Node(key, value);
        return true;
    }

    // 如果根不为空, 找到插入位置
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
        if (cur->_key > key)
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (cur->_key < key)
        {
            parent = cur;
            cur = cur->_right;
        }
        else
        {
            return false;   // 如果相等, 表示我已经有了, 不需要插入了
        }
    }

    // 插入节点
    cur = new Node(key, value);
    if (parent->_key > key)
    {
        parent->_left = cur;
    }
    else
    {
        parent->_right = cur;
    }

    return true;
}

在非递归实现中，我们使用 parent 指针来保持对父节点的引用，从而在最后确定插入节点应作为父节点的左子树或右子树。

  

5.2、查找操作

查找操作与插入操作类似，也是通过递归比较值来确定目标节点的位置。如果找到与目标值相同的节点，则返回该节点；否则继续在左子树或右子树中查找。

5.2.1、递归查找实现

// 辅助函数
Node* _find(Node* root, const K& key)
{
    if (root == nullptr || root->_key == key)
    {
        return root;
    }
    if (key < root->_key)
    {
        return _find(root->_left, key);
    }
    else
    {
        return _find(root->_right, key);
    }
}

// 查找节点
Node* Find(const K& key)
{
    return _find(_root, key);
}

5.2.2、非递归查找实现

// 查找节点
Node* Find(const K& key)
{
    Node* cur = _root;
    while (cur)
    {
        if (cur->_key > key)
        {
            cur = cur->_left;
        }
        else if (cur->_key < key)
        {
            cur = cur->_right;
        }
        else
        {
            return cur;
        }
    }
    return nullptr;
}

查找操作解析：

  1. 首先判断当前节点是否为空或值是否等于目标值。如果满足，则返回节点。
  2. 如果目标值小于当前节点的值，则递归查找左子树；如果大于当前节点的值，则递归查找右子树。

  

5.3、删除操作

删除操作是 BST 中较为复杂的操作之一。删除节点的难度在于需要根据被删除节点的子节点情况进行不同的处理。主要有三种情况：

  1. 删除叶子节点： 直接删除该节点。
  2. 删除只有一个子节点的节点： 用该节点的子节点替代该节点。
  3. 删除有两个子节点的节点： 用右子树的最小节点替代被删除节点，然后删除该最小节点。

5.3.1、递归删除实现

Node* _erase(Node* root, const K& key)
{
    if (root == nullptr)
    {
        return root;
    }
    if (key < root->_key)
    {
        root->_left = _erase(root->_left, key);
    }
    else if (key > root->_key)
    {
        root->_right = _erase(root->_right, key);
    }
    else
    {
        if (root->_left == nullptr)
        {
            Node* ret = root->_right;
            delete root;
            return ret;
        }
        if (root->_right == nullptr)
        {
            Node* ret = root->_left;
            delete root;
            return ret;
        }
        Node* minNode = getMin(root->_right);
        root->_key = minNode->_key;
        root->_right = _erase(root->_right, minNode->_key);
    }
    return root;
}

Node* getMin(Node* node) 
{
    while (node->_left != nullptr) 
    {
        node = node->_left;
    }
    return node;
}

// 删除节点
void Erase(const K& key)
{
    _erase(_root, key);
}

5.3.2、非递归删除实现

// 删除节点
bool Erase(const K& key)
{
    // 找到要删除的节点
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
        if (cur->_key > key)
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (cur->_key < key)
        {
            parent = cur;
            cur = cur->_right;
        }
        else
        {
            break;
        }
    }

    // 没找到
    if (cur == nullptr)
    {
        return false;
    }

    // 找到了
    // 1. 要删除的节点没有左孩子
    if (cur->_left == nullptr)
    {
        if (cur == _root)
        {
            _root = cur->_right;
        }
        else
        {
            if (parent->_left == cur)
            {
                parent->_left = cur->_right;
            }
            else
            {
                parent->_right = cur->_right;
            }
        }
        delete cur;
    }
    // 2. 要删除的节点没有右孩子
    else if (cur->_right == nullptr)
    {
        if (cur == _root)
        {
            _root = cur->_left;
        }
        else
        {
            if (parent->_left == cur)
            {
                parent->_left = cur->_left;
            }
            else
            {
                parent->_right = cur->_left;
            }
        }
        delete cur;
    }
    // 3. 左右都不为空, 不能直接删除, 使用替换法删除
    // 可以找左子树的最大节点或者右子树的最小节点去替代它
    else
    {
        // 右子树最小节点
        Node* rightMinParent = cur;
        Node* rightMin = cur->_right;
        while (rightMin->_left)
        {
            rightMinParent = rightMin;
            rightMin = rightMin->_left;
        }

        // 替换删除的节点
        std::swap(cur->_key, rightMin->_key);
        std::swap(cur->_value, rightMin->_value);

        // 把问题转换成删除 rightMin
        if (rightMinParent->_left == rightMin)
        {
            rightMinParent->_left = rightMin->_right;
        }
        else
        {
            rightMinParent->_right = rightMin->_right;
        }

        delete rightMin;
    }

    return true;
}

删除操作解析：

  1. 递归查找到要删除的节点。
  2. 如果删除的节点没有子节点或只有一个子节点，直接返回其子节点或 nullptr。
  3. 如果删除的节点有两个子节点，找到右子树的最小节点，用该节点的值替代当前节点的值，并递归删除右子树中的最小节点。

  

6、优化二叉搜索树

二叉搜索树的效率在很大程度上取决于树的高度。理想情况下，二叉搜索树的高度应该为 O(log⁡n)，即平衡的二叉搜索树。然而，如果插入的数据是有序的，二叉搜索树会退化为链表，树的高度将达到 O(n)，从而使查找、插入和删除操作的时间复杂度变为线性。

要避免树的退化问题，通常可以考虑使用自平衡的二叉搜索树，如 AVL 树 和 红黑树。这些树在插入或删除节点时，会通过旋转操作保证树的高度尽量保持在 O(log⁡n) 的水平。以确保查找、插入和删除操作的高效性。

6.1、AVL 树

AVL 树 是第一种被发明的自平衡二叉搜索树。它在每次插入和删除节点后，会自动检测并调整树的平衡。AVL 树的特点是每个节点的左右子树的高度差不超过 1。为了维持平衡，AVL 树需要在插入或删除节点时进行额外的旋转操作。

AVL 树的插入操作与普通 BST 的插入过程类似，唯一的不同点是插入后可能需要旋转以保持平衡。通常有两种旋转操作：左旋 和 右旋，还有两种组合旋转：左-右旋 和 右-左旋。

  

更多关于 AVL 树的技术详情，请移步这篇博客：自平衡的艺术：深入了解 AVL 树的核心原理与实现

  

6.2、红黑树

红黑树是一种更加复杂的自平衡二叉搜索树。与 AVL 树相比，红黑树的旋转次数较少，但它的平衡性略逊于 AVL 树。红黑树的特点是通过颜色（红色或黑色）标记节点，并通过颜色规则保持树的平衡。

红黑树的规则包括：

  1. 每个节点不是红色就是黑色。
  2. 根节点是黑色。
  3. 所有叶子节点（空节点）是黑色。
  4. 如果一个节点是红色，则它的子节点必须是黑色（即不存在两个连续的红色节点）。
  5. 从任意节点到其每个叶子的所有路径都包含相同数量的黑色节点。

红黑树的实现较为复杂，涉及左旋、右旋、变色等操作。但其主要优点是插入、删除的平衡操作次数较少，能够保证 O(log⁡n) 的时间复杂度。

  

7、二叉搜索树的遍历

遍历是操作二叉搜索树的重要内容之一。通过不同的遍历方法，我们可以按不同的顺序访问树中的所有节点。常见的遍历方法包括中序遍历（In-order Traversal）、前序遍历（Pre-order Traversal）、后序遍历（Post-order Traversal）和层次遍历（Level-order Traversal）。每种遍历方法都有其特殊用途和实现细节。

7.1、中序遍历（In-order Traversal）

中序遍历是二叉搜索树最常用的遍历方式，它按升序或降序访问节点。在 BST 中，中序遍历会先访问左子树的所有节点，再访问根节点，最后访问右子树的所有节点。因此，如果按照中序遍历访问 BST，结果将是按递增顺序输出。

7.1.1、中序遍历的递归实现

// 辅助函数
void _InOrder(Node* root)
{
    if (root == nullptr)
    {
        return;
    }

    _InOrder(root->_left);   // 访问左子树
     //std::cout << root->_key << " : " << root->_value << std::endl;
    std::cout << root->_key << " ";    // 访问根节点
    _InOrder(root->_right);  // 访问右子树
}

void InOrder()
{
    _InOrder(_root);
    std::cout << std::endl;
}

7.1.2、中序遍历的非递归实现

void InOrder()
{
    std::stack<Node*> stack;
    Node* cur = _root;

    while (cur != nullptr || !stack.empty()) {
        // 找到最左边的节点
        while (cur != nullptr) {
            stack.push(cur);
            cur = cur->_left;
        }

        // 处理当前节点
        cur = stack.top();
        stack.pop();
        std::cout << cur->_key << " ";

        // 转向右子树
        cur = cur->_right;
    }
    std::cout << std::endl;
}

递归实现代码简洁，但在深度较大的树上可能会面临栈溢出问题；非递归实现利用栈模拟递归过程，能够避免这一问题。

  

7.2、前序遍历（Pre-order Traversal）

前序遍历的顺序是首先访问根节点，然后访问左子树，最后访问右子树。这种遍历方式常用于构建、复制二叉树或需要先处理节点本身的场景。

7.2.1、前序遍历的递归实现

// 辅助函数
void _PreOrder(Node* root)
{
    if (root == nullptr) 
    {
        return;
    }

    std::cout << root->_key << " ";   // 访问根节点
    _PreOrder(root->_left);   // 访问左子树
    _PreOrder(root->_right);  // 访问右子树
}

void PreOrder()
{
    _PreOrder(_root);
    std::cout << std::endl;
}

7.2.2、前序遍历的非递归实现

void PreOrder() 
{
    if (_root == nullptr) 
    {
        return;
    }

    std::stack<Node*> stack;
    stack.push(_root);

    while (!stack.empty()) {
        Node* cur = stack.top();
        stack.pop();
        std::cout << cur->_key << " ";  // 访问当前节点

        // 先压入右子树再压入左子树（确保左子树先处理）
        if (cur->_right != nullptr) 
        {
            stack.push(cur->_right);
        }
        if (cur->_left != nullptr) {
            stack.push(cur->_left);
        }
    }
    std::cout << std::endl;
}

  

7.3、后序遍历（Post-order Traversal）

后序遍历的顺序是首先访问左子树，然后访问右子树，最后访问根节点。后序遍历常用于删除树或需要先处理子节点的场景，如在动态内存管理中可以用于递归删除节点。

7.3.1、后序遍历的递归实现

// 辅助函数
void _PostOrder(Node* root) {
    if (root == nullptr) 
    {
        return;
    }

    _PostOrder(root->_left);    // 访问左子树
    _PostOrder(root->_right);   // 访问右子树
    std::cout << root->_key << " ";     // 访问根节点
}

void PostOrder()
{
    _PostOrder(_root);
    std::cout << std::endl;
}

7.3.2、后续遍历的非递归实现

非递归的后序遍历比较复杂，因为需要在访问根节点之前处理左右子树。

void PostOrder() 
{
    if (_root == nullptr)
    {
        return ;
    }

    std::stack<Node*> st;
    Node* cur = _root;
    Node* lastNode = nullptr; // 最近访问的节点
    while (cur || !st.empty()) 
    {
        while (cur) 
        {
            st.push(cur);
            cur = cur->_left;
        }

        Node* top = st.top();
        if ((top->_right == nullptr) || (lastNode == top->_right)) 
        {
            std::cout << top->_key << " ";
            lastNode = top;
            st.pop();
        }
        else {
            cur = top->_right;
        }
    }
    std::cout << std::endl;
}

  

7.4、层序遍历（Level-order Traversal）

层序遍历按树的层级顺序依次访问节点，即先访问根节点，然后从左到右依次访问每一层的节点。层次遍历通常使用队列来实现，在树的广度优先搜索（BFS）中非常常见。

// 层序遍历
void LevelOrder() 
{
    if (_root == nullptr) 
    {
        return;
    }

    std::queue<Node*> queue;
    queue.push(_root);

    while (!queue.empty()) 
    {
        Node* cur = queue.front();
        queue.pop();
        std::cout << cur->_key << " ";   // 访问当前节点

        if (cur->_left != nullptr) {
            queue.push(cur->_left);      // 将左子树压入队列
        }
        if (cur->_right != nullptr) {
            queue.push(cur->_right);     // 将右子树压入队列
        }
    }
    std::cout << std::endl;
}

层次遍历常用于计算树的深度、查找树的最浅路径或寻找最优解等场景。

  

8、二叉搜索树的其他高级操作

除了基本的插入、查找、删除等操作，二叉搜索树还可以实现一些高级操作，如查找前驱和后继、区间查询、节点的排名等。这些操作可以扩展二叉搜索树的功能，增加其实用性。

8.1、查找后继节点

前驱是指比某个节点值小的最大节点，后继则是比某个节点值大的最小节点。在二叉搜索树中，查找前驱和后继是常见的操作，尤其在区间查询或范围搜索时非常有用。

查找后继的递归实现：

// 查找后继节点
Node* findMin(Node* node)
{
    while (node->_left != nullptr) 
    {
        node = node->_left;
    }
    return node;
}

Node* FindSuccessor(Node* node) 
{
    if (node->_right != nullptr) 
    {
        return findMin(node->_right);
    }

    Node* cur = _root;
    Node* successor = nullptr;
    while (cur != nullptr) 
    {
        if (node->_key < cur->_key)
        {
            successor = cur;
            cur = cur->_left;
        }
        else if (node->_key > cur->_key) 
        {
            cur = cur->_right;
        }
        else 
        {
            break;
        }
    }
    return successor;
}

查找后继时，如果节点有右子树，则后继为右子树中最小的节点；否则，后继为第一个大于该节点的祖先节点。

  

8.2、查找前驱节点

查找前驱的递归实现：

// 查找前驱节点
Node* findMax(Node* node)
{
    while (node->_right != nullptr)
    {
        node = node->_right;
    }
    return node;
}

Node* FindPredecessor(Node* node)
{
    if (node->_left != nullptr)
    {
        return findMax(node->_left);
    }

    Node* cur = _root;
    Node* predecessor = nullptr;
    while (cur != nullptr)
    {
        if (node->_key < cur->_key)
        {
            cur = cur->_left;
        }
        else if (node->_key > cur->_key)
        {
            predecessor = cur;
            cur = cur->_right;
        }
        else
        {
            break;
        }
    }
    return predecessor;
}

前驱的查找逻辑与后继类似，只是方向相反。

  

9、完整实现代码和测试

9.1、BSTree.hpp

#pragma once

#include <iostream>
#include <stack>
#include <queue>

namespace Lenyiin
{
    template <class K, class V>
    struct BSTreeNode
    {
        BSTreeNode(const K& key = K(), const V& value = V())
            : _key(key), _value(value), _left(nullptr), _right(nullptr)
        {
        }

        K _key;
        V _value;
        BSTreeNode<K, V>* _left;
        BSTreeNode<K, V>* _right;
    };

    template <class K, class V>
    class BSTree
    {
    private:
        typedef BSTreeNode<K, V> Node;

        Node* _Copy(Node* root)
        {
            if (root == nullptr)
            {
                return nullptr;
            }

            Node* cur = new Node(root->_key, root->_value);
            cur->_left = _Copy(root->_left);
            cur->_right = _Copy(root->_right);

            return cur;
        }

    public:
        // 默认构造
        BSTree()
            : _root(nullptr)
        {}

        // 拷贝构造
        BSTree(const BSTree<K, V>& tree)
        {
            _root = _Copy(tree._root);
        }

        // 非递归插入
        //bool Insert(const K& key, const V& value)
        //{
        //  // 如果根为空, 直接插入
        //  if (_root == nullptr)
        //  {
        //      _root = new Node(key, value);
        //      return true;
        //  }

        //  // 如果根不为空, 找到插入位置
        //  Node* parent = nullptr;
        //  Node* cur = _root;
        //  while (cur)
        //  {
        //      if (cur->_key > key)
        //      {
        //          parent = cur;
        //          cur = cur->_left;
        //      }
        //      else if (cur->_key < key)
        //      {
        //          parent = cur;
        //          cur = cur->_right;
        //      }
        //      else
        //      {
        //          return false;   // 如果相等, 表示我已经有了, 不需要插入了
        //      }
        //  }

        //  // 插入节点
        //  cur = new Node(key, value);
        //  if (parent->_key > key)
        //  {
        //      parent->_left = cur;
        //  }
        //  else
        //  {
        //      parent->_right = cur;
        //  }

        //  return true;
        //}

        // 递归插入
        // 辅助函数
        Node* _insert(Node* root, const K& key, const V& value)
        {
            if (root == nullptr)
            {
                return new Node(key, value);
            }
            if (key < root->_key)
            {
                root->_left = _insert(root->_left, key, value);
            }
            else if (key > root->_key)
            {
                root->_right = _insert(root->_right, key, value);
            }
            return root;
        }

        // 插入
        void Insert(const K& key, const V& value)
        {
            _root = _insert(_root, key, value);
        }

        // 非递归查找节点
        //Node* Find(const K& key)
        //{
        //  Node* cur = _root;
        //  while (cur)
        //  {
        //      if (cur->_key > key)
        //      {
        //          cur = cur->_left;
        //      }
        //      else if (cur->_key < key)
        //      {
        //          cur = cur->_right;
        //      }
        //      else
        //      {
        //          return cur;
        //      }
        //  }
        //  return nullptr;
        //}

        // 递归查找节点
        // 辅助函数
        Node* _find(Node* root, const K& key)
        {
            if (root == nullptr || root->_key == key)
            {
                return root;
            }
            if (key < root->_key)
            {
                return _find(root->_left, key);
            }
            else
            {
                return _find(root->_right, key);
            }
        }

        // 查找节点
        Node* Find(const K& key)
        {
            return _find(_root, key);
        }

        // 非递归删除节点
        //bool Erase(const K& key)
        //{
        //  // 找到要删除的节点
        //  Node* parent = nullptr;
        //  Node* cur = _root;
        //  while (cur)
        //  {
        //      if (cur->_key > key)
        //      {
        //          parent = cur;
        //          cur = cur->_left;
        //      }
        //      else if (cur->_key < key)
        //      {
        //          parent = cur;
        //          cur = cur->_right;
        //      }
        //      else
        //      {
        //          break;
        //      }
        //  }

        //  // 没找到
        //  if (cur == nullptr)
        //  {
        //      return false;
        //  }

        //  // 找到了
        //  // 1. 要删除的节点没有左孩子
        //  if (cur->_left == nullptr)
        //  {
        //      if (cur == _root)
        //      {
        //          _root = cur->_right;
        //      }
        //      else
        //      {
        //          if (parent->_left == cur)
        //          {
        //              parent->_left = cur->_right;
        //          }
        //          else
        //          {
        //              parent->_right = cur->_right;
        //          }
        //      }
        //      delete cur;
        //  }
        //  // 2. 要删除的节点没有右孩子
        //  else if (cur->_right == nullptr)
        //  {
        //      if (cur == _root)
        //      {
        //          _root = cur->_left;
        //      }
        //      else
        //      {
        //          if (parent->_left == cur)
        //          {
        //              parent->_left = cur->_left;
        //          }
        //          else
        //          {
        //              parent->_right = cur->_left;
        //          }
        //      }
        //      delete cur;
        //  }
        //  // 3. 左右都不为空, 不能直接删除, 使用替换法删除
        //  // 可以找左子树的最大节点或者右子树的最小节点去替代它
        //  else
        //  {
        //      // 右子树最小节点
        //      Node* rightMinParent = cur;
        //      Node* rightMin = cur->_right;
        //      while (rightMin->_left)
        //      {
        //          rightMinParent = rightMin;
        //          rightMin = rightMin->_left;
        //      }

        //      // 替换删除的节点
        //      std::swap(cur->_key, rightMin->_key);
        //      std::swap(cur->_value, rightMin->_value);

        //      // 把问题转换成删除 rightMin
        //      if (rightMinParent->_left == rightMin)
        //      {
        //          rightMinParent->_left = rightMin->_right;
        //      }
        //      else
        //      {
        //          rightMinParent->_right = rightMin->_right;
        //      }

        //      delete rightMin;
        //  }

        //  return true;
        //}

        // 递归删除节点
        // 辅助函数
        Node* _erase(Node* root, const K& key)
        {
            if (root == nullptr)
            {
                return root;
            }
            if (key < root->_key)
            {
                root->_left = _erase(root->_left, key);
            }
            else if (key > root->_key)
            {
                root->_right = _erase(root->_right, key);
            }
            else
            {
                if (root->_left == nullptr)
                {
                    Node* ret = root->_right;
                    delete root;
                    return ret;
                }
                if (root->_right == nullptr)
                {
                    Node* ret = root->_left;
                    delete root;
                    return ret;
                }
                Node* minNode = getMin(root->_right);
                root->_key = minNode->_key;
                root->_right = _erase(root->_right, minNode->_key);
            }
            return root;
        }

        Node* getMin(Node* node) 
        {
            while (node->_left != nullptr) 
            {
                node = node->_left;
            }
            return node;
        }

        // 删除节点
        void Erase(const K& key)
        {
            _erase(_root, key);
        }

        // 递归中序遍历
        // 辅助函数
        //void _InOrder(Node* root)
        //{
        //  if (root == nullptr)
        //  {
        //      return;
        //  }

        //  _InOrder(root->_left);
        //   //std::cout << root->_key << " : " << root->_value << std::endl;
        //  std::cout << root->_key << " ";
        //  _InOrder(root->_right);
        //}

        //void InOrder()
        //{
        //  _InOrder(_root);
        //  std::cout << std::endl;
        //}

        // 非递归中序遍历
        void InOrder()
        {
            std::stack<Node*> stack;
            Node* cur = _root;

            while (cur != nullptr || !stack.empty()) {
                // 找到最左边的节点
                while (cur != nullptr) {
                    stack.push(cur);
                    cur = cur->_left;
                }

                // 处理当前节点
                cur = stack.top();
                stack.pop();
                std::cout << cur->_key << " ";

                // 转向右子树
                cur = cur->_right;
            }
            std::cout << std::endl;
        }

        // 递归前序遍历
        // 辅助函数
        //void _PreOrder(Node* root)
        //{
        //  if (root == nullptr) 
        //  {
        //      return;
        //  }

        //  std::cout << root->_key << " ";   // 访问根节点
        //  _PreOrder(root->_left);   // 访问左子树
        //  _PreOrder(root->_right);  // 访问右子树
        //}

        //void PreOrder()
        //{
        //  _PreOrder(_root);
        //  std::cout << std::endl;
        //}

        // 非递归前序遍历
        void PreOrder() 
        {
            if (_root == nullptr) 
            {
                return;
            }

            std::stack<Node*> stack;
            stack.push(_root);

            while (!stack.empty()) {
                Node* cur = stack.top();
                stack.pop();
                std::cout << cur->_key << " ";  // 访问当前节点

                // 先压入右子树再压入左子树（确保左子树先处理）
                if (cur->_right != nullptr) 
                {
                    stack.push(cur->_right);
                }
                if (cur->_left != nullptr) {
                    stack.push(cur->_left);
                }
            }
            std::cout << std::endl;
        }

        // 递归后序遍历
        // 辅助函数
        //void _PostOrder(Node* root) {
        //  if (root == nullptr) 
        //  {
        //      return;
        //  }

        //  _PostOrder(root->_left);    // 访问左子树
        //  _PostOrder(root->_right);   // 访问右子树
        //  std::cout << root->_key << " ";     // 访问根节点
        //}

        //void PostOrder()
        //{
        //  _PostOrder(_root);
        //  std::cout << std::endl;
        //}

        // 非递归后序遍历
        void PostOrder() 
        {
            if (_root == nullptr)
            {
                return ;
            }

            std::stack<Node*> st;
            Node* cur = _root;
            Node* lastNode = nullptr; // 最近访问的节点
            while (cur || !st.empty()) 
            {
                while (cur) 
                {
                    st.push(cur);
                    cur = cur->_left;
                }

                Node* top = st.top();
                if ((top->_right == nullptr) || (lastNode == top->_right)) 
                {
                    std::cout << top->_key << " ";
                    lastNode = top;
                    st.pop();
                }
                else {
                    cur = top->_right;
                }
            }
            std::cout << std::endl;
        }

        // 层序遍历
        void LevelOrder() 
        {
            if (_root == nullptr) 
            {
                return;
            }

            std::queue<Node*> queue;
            queue.push(_root);

            while (!queue.empty()) 
            {
                Node* cur = queue.front();
                queue.pop();
                std::cout << cur->_key << " ";   // 访问当前节点

                if (cur->_left != nullptr) {
                    queue.push(cur->_left);      // 将左子树压入队列
                }
                if (cur->_right != nullptr) {
                    queue.push(cur->_right);     // 将右子树压入队列
                }
            }
            std::cout << std::endl;
        }

        // 查找前驱节点
        Node* findMax(Node* node)
        {
            while (node->_right != nullptr)
            {
                node = node->_right;
            }
            return node;
        }

        Node* FindPredecessor(Node* node)
        {
            if (node->_left != nullptr)
            {
                return findMax(node->_left);
            }

            Node* cur = _root;
            Node* predecessor = nullptr;
            while (cur != nullptr)
            {
                if (node->_key < cur->_key)
                {
                    cur = cur->_left;
                }
                else if (node->_key > cur->_key)
                {
                    predecessor = cur;
                    cur = cur->_right;
                }
                else
                {
                    break;
                }
            }
            return predecessor;
        }

        // 查找后继节点
        Node* findMin(Node* node)
        {
            while (node->_left != nullptr) 
            {
                node = node->_left;
            }
            return node;
        }

        Node* FindSuccessor(Node* node) 
        {
            if (node->_right != nullptr) 
            {
                return findMin(node->_right);
            }

            Node* cur = _root;
            Node* successor = nullptr;
            while (cur != nullptr) 
            {
                if (node->_key < cur->_key)
                {
                    successor = cur;
                    cur = cur->_left;
                }
                else if (node->_key > cur->_key) 
                {
                    cur = cur->_right;
                }
                else 
                {
                    break;
                }
            }
            return successor;
        }

    private:
        Node* _root = nullptr;
    };
}

  

9.2、BSTree.cpp

#include "BSTree.hpp"
#include <string>

using namespace Lenyiin;

void test_BSTree_1()
{
    BSTree<int, int> t;
    int a[] = { 5,3,4,1,7,8,2,6,0,9 };
    for (const auto& e : a)
    {
        t.Insert(e, e);
    }

    // 搜索二叉树的中序遍历
    t.InOrder();
    // 搜索二叉树的前序遍历
    t.PreOrder();
    // 搜索二叉树的后序遍历
    t.PostOrder();
    // 搜索二叉树的层序遍历
    t.LevelOrder();

    auto node = t.Find(5);
    if (node != nullptr)
    {
        std::cout << node->_value << std::endl;
    }
    else
    {
        std::cout << "没找到" << std::endl;
    }

    auto pre = t.FindPredecessor(node);
    if (pre != nullptr)
    {
        std::cout << node->_key << " 的前驱节点是: " << pre->_key << std::endl;
    }
    else
    {
        std::cout << "前驱节点为空" << std::endl;
    }

    auto suc = t.FindSuccessor(node);
    if (suc != nullptr)
    {
        std::cout << node->_key << " 的后继节点是: " << suc->_key << std::endl;
    }
    else
    {
        std::cout << "后继节点为空" << std::endl;
    }

    // 1. 叶子
    t.Erase(5);
    t.InOrder();

    // 左为空或者右为空
    t.Erase(8);
    t.Erase(1);
    t.InOrder();

    // 重复删除
    t.Erase(5);
    t.InOrder();
}

void test_BSTree_2()
{
    BSTree<std::string, std::string> dict;
    dict.Insert("sort", "排序");
    dict.Insert("string", "字符串");
    dict.Insert("vector", "向量");
    dict.Insert("map", "映射");
    dict.Insert("set", "集合");
    dict.Insert("algorithm", "算法");
    dict.Insert("iterator", "迭代器");
    dict.Insert("stack", "栈");
    dict.Insert("queue", "队列");
    dict.Insert("list", "链表");
    dict.Insert("deque", "双端队列");
    dict.Insert("priority_queue", "优先级队列");
    dict.Insert("binary_search", "二分查找");
    dict.Insert("lower_bound", "下界");
    dict.Insert("upper_bound", "上界");

    dict.InOrder();

    std::string str;
    while (std::cin >> str)
    {
        BSTreeNode<std::string, std::string>* ret = dict.Find(str);
        if (ret)
        {
            std::cout << ret->_key << ":" << ret->_value << std::endl;
        }
        else
        {
            std::cout << "没找到" << std::endl;
        }
    }
}

void test_BSTree_3()
{
    std::string strArr[] = { "西瓜", "苹果", "西瓜", "苹果", "西瓜", "香蕉", "西瓜", "樱桃", "西瓜", "苹果",
                       "西瓜", "苹果", "西瓜", "香蕉", "西瓜", "樱桃", "西瓜", "苹果", "西瓜", "苹果", "西瓜", "香蕉",
                       "西瓜", "樱桃", "西瓜", "苹果", "西瓜", "苹果", "西瓜", "香蕉", "西瓜", "樱桃", "西瓜", "苹果",
                       "西瓜", "苹果", "西瓜", "香蕉", "西瓜", "樱桃", "西瓜", "苹果", "西瓜", "苹果", "西瓜", "香蕉" };

    BSTree<std::string, int> countTree;

    for (auto str : strArr)
    {
        BSTreeNode<std::string, int>* ret = countTree.Find(str);
        if (ret == nullptr)
        {
            countTree.Insert(str, 1);
        }
        else
        {
            ret->_value++;
        }
    }

    countTree.InOrder();
}

int main()
{
    test_BSTree_1();
    //test_BSTree_2();
    test_BSTree_3();

    return 0;
}

  

10、总结

本文全面讨论了二叉搜索树（Binary Search Tree，BST）的核心概念及其各项操作，包括插入、查找、删除等基本操作，以及前序遍历、中序遍历、后序遍历和层次遍历等不同的遍历方式。我们不仅详细介绍了这些操作的递归与非递归实现，还结合具体代码演示了如何高效操作二叉搜索树。

二叉搜索树作为一种动态数据结构，具有快速查找、插入和删除的优势，其平均时间复杂度在平衡状态下为 O(log⁡n)，在处理有序数据或搜索大数据集时表现尤为突出。本文深入探讨了BST的插入、查找、删除操作，分析了其在不同情况下的时间复杂度。同时，通过遍历方法的介绍，读者可以理解如何按不同顺序访问树中的节点，从而满足各种算法需求。

在高级操作部分，本文讨论了查找前驱和后继的实现方法，这在区间查询等应用中非常实用。前驱和后继的概念使二叉搜索树能够方便地进行排序、范围查询等操作，进一步提升其实际应用的广泛性。

此外，本文还提供了一个自定义实现的二叉搜索树类，通过模板支持任意数据类型，并实现了插入、删除、遍历等常见功能。这个自定义实现为读者提供了从理论到实际应用的桥梁，帮助读者掌握二叉搜索树的核心实现逻辑，理解其在实际编程中的应用。

通过这篇文章，读者不仅能够深入理解二叉搜索树的基础理论，还能动手实现一个功能完备的二叉搜索树，并学会如何在应用中合理使用它。本文还为进一步扩展提供了建议，比如引入平衡机制（如AVL树或红黑树），以解决二叉搜索树在极端情况下可能退化为线性结构的问题。平衡树是二叉搜索树的高级形式，能够保证在最坏情况下依然能提供 O(log⁡n) 的性能。

总的来说，本文为想深入了解二叉搜索树技术细节的读者提供了全面的参考资料和具体代码实现，是理解和掌握二叉搜索树及其扩展结构的坚实基础。通过这一系列学习，读者可以将二叉搜索树应用到数据库、搜索引擎、文件系统等多个领域，为优化算法和提升程序性能打下基础。

  

希望这篇博客对您有所帮助，也欢迎您在此基础上进行更多的探索和改进。如果您有任何问题或建议，欢迎在评论区留言，我们可以共同探讨和学习。更多知识分享可以访问我的个人博客网站 ： https://blog.lenyiin.com/ 。本博客所涉及的代码也可以访问我的 git 仓库获取 ：https://git.lenyiin.com/Lenyiin/BSTree

  

  

Tags:

Comments

No comments yet. Why don’t you start the discussion?

发表回复