C++ 二叉搜索树：从原理到增删查实现

1. 核心概念

二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树结构，它满足以下性质：

若左子树不空，则左子树上所有节点的值均小于根节点的值。
若右子树不空，则右子树上所有节点的值均大于根节点的值。
左、右子树也分别为二叉搜索树。

这种有序性使得查找、插入和删除操作在平衡状态下具有 $O(\log n)$ 的时间复杂度。如果树退化为链表（例如按顺序插入数据），性能则会下降至 $O(n)$。

2. 关键操作详解

我们将二叉搜索树封装为一个模板类 BSTree，并声明一个 _root 指针指向树的根节点。

2.1 查找节点

给定目标值 val，从根节点出发循环比较：

若 val < cur->_key，向左子树移动。
若 val > cur->_key，向右子树移动。
若相等，返回当前节点。

Node* find(const K& val) {
    Node* cur = _root;
    while (cur) {
        if (val < cur->_key)
            cur = cur->_left;
        else if (val > cur->_key)
            cur = cur->_right;
        else
            break;
    }
    return cur;
}

2.2 插入节点

插入时需保持 BST 的有序性。流程如下：

查找位置：逻辑同查找，直到遇到空指针。
插入节点：在空指针处创建新节点。

注意：BST 通常不允许重复键值。若待插入值已存在，直接返回失败。

bool insert(const K& val) {
    // 空树情况
    if (_root == nullptr) {
        _root = new Node(val);
        return true;
    }

    Node* cur = _root;
    Node* curPre = nullptr; // 记录父节点

    while (cur) {
         (val == cur->_key)
             ; 
          (val < cur->_key) {
            curPre = cur;
            cur = cur->_left;
        }  {
            curPre = cur;
            cur = cur->_right;
        }
    }

    
    Node* newNode =  (val);
     (curPre->_left == cur)
        curPre->_left = newNode;
    
        curPre->_right = newNode;

     ;
}

#pragma once #include <iostream> #include <vector> using namespace std; template<class K> struct BSTNode { BSTNode<K>* _left; BSTNode<K>* _right; K _key; BSTNode(const K& val) : _left(nullptr), _right(nullptr), _key(val) {} }; template<class K> class BSTree { public: typedef BSTNode<K> Node; BSTree() : _root(nullptr) {} ~BSTree() { destroy(_root); } Node* find(const K& val) { Node* cur = _root; while (cur) { if (val < cur->_key) cur = cur->_left; else if (val > cur->_key) cur = cur->_right; else break; } return cur; } bool insert(const K& val) { if (_root == nullptr) { _root = new Node(val); return true; } Node* cur = _root; Node* curPre = nullptr; while (cur) { if (val == cur->_key) return false; else if (val < cur->_key) { curPre = cur; cur = cur->_left; } else { curPre = cur; cur = cur->_right; } } Node* newNode = new Node(val); if (curPre->_left == cur) curPre->_left = newNode; else curPre->_right = newNode; return true; } bool erase(const K& val) { if (_root == nullptr) return false; Node* cur = _root; Node* curPre = nullptr; while (cur) { if (val < cur->_key) { curPre = cur; cur = cur->_left; } else if (val > cur->_key) { curPre = cur; cur = cur->_right; } else break; } if (cur == nullptr) return false; if (cur->_left == nullptr || cur->_right == nullptr) { Node* curNext = cur->_left ? cur->_left : cur->_right; if (cur != _root) { if (curPre->_left == cur) curPre->_left = curNext; else curPre->_right = curNext; } else { _root = curNext; } delete cur; } else { Node* rightMin = cur->_right; Node* rightMinPre = cur; while (rightMin->_left) { rightMinPre = rightMin; rightMin = rightMin->_left; } cur->_key = rightMin->_key; Node* rightMinNext = rightMin->_right; if (rightMinPre->_left == rightMin) rightMinPre->_left = rightMinNext; else rightMinPre->_right = rightMinNext; delete rightMin; } return true; } void inOrder() { _inOrder(_root); cout << endl; } private: Node* _root; void destroy(Node* root) { if (root == nullptr) return; destroy(root->_left); destroy(root->_right); delete root; } void _inOrder(Node* root) { if (root == nullptr) return; _inOrder(root->_left); cout << root->_key << " "; _inOrder(root->_right); } };

C++ 二叉搜索树：从原理到增删查实现