当前位置：首页 > news >正文

C++之二叉搜索树及其实现

news 2026/5/12 14:58:21

一.二叉搜索树的基本概念

二叉搜索树（Binary Search Tree，简称 BST）是一种特殊的二叉树，它满足以下性质：对于树中的每个节点，其左子树中所有节点的值都小于该节点的值对于树中的每个节点，其右子树中所有节点的值都大于该节点的值左右子树也分别是二叉搜索树这种特性使得二叉搜索树在查找、插入和删除操作上具有较高的效率，平均时间复杂度为 O (log n)。

在这里插入图片描述

二.二叉搜索树的性能分析

最优情况下，⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树)，其⾼度为：log2 N 最差情况下，⼆叉搜索树退化为单⽀树(或者类似单⽀)，其⾼度为：N 所以综合⽽⾔⼆叉搜索树增删查改时间复杂度为：O(N)

⼆分查找也可以实现O(log2N) 级别的查找效率，但是⼆分查找有两⼤缺陷：

需要存储在⽀持下标随机访问的结构中，并且有序。
插⼊和删除数据效率很低，因为存储在下标随机访问的结构中，插⼊和删除数据⼀般需要挪动数据。

这⾥也就体现出了平衡⼆叉搜索树的价值。

三.二叉搜索树的实现

搜索二叉树的基本概念与特性

搜索二叉树是一种特殊的二叉树，它满足以下性质：

若任意节点的左子树不为空，则左子树上所有节点的值均小于该节点的值
若任意节点的右子树不为空，则右子树上所有节点的值均大于该节点的值
任意节点的左、右子树也分别为搜索二叉树
没有键值相等的节点

这些性质使得搜索二叉树在进行查找操作时具有天然的优势，我们可以利用节点值的大小关系快速缩小查找范围，类似于有序数组的二分查找。

搜索二叉树的节点结构设计

首先来看搜索二叉树的节点结构实现：

代码语言：javascript

AI代码解释

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

_key：节点的关键字，用于比较和查找
_left：指向左子节点的指针
_right：指向右子节点的指针
构造函数：初始化节点的关键字，并将左右子节点指针置为nullptr

节点采用模板设计，使得该结构可以存储任意类型的数据，只要该类型支持比较运算。

搜索二叉树的类结构与核心操作

类的基本结构

代码语言：javascript

AI代码解释

template<class K> class BSTree { typedef BSTreeNode<K> Node; public: // 构造、拷贝构造、赋值运算符、析构函数 BSTree() = default; BSTree(const BSTree<K>& t); BSTree<K>& operator=(BSTree<K> t); ~BSTree(); // 核心操作 bool Insert(const K& key); bool Find(const K& key); bool Erase(const K& key); // 中序遍历 void InOrder(); private: // 中序遍历的递归辅助函数 void _InOrder(Node* root); // 拷贝构造的递归辅助函数 Node* Copy(Node* root); // 析构函数的递归辅助函数 void Destory(Node* root); private: Node* _root = nullptr; };

构造与析构函数

默认构造函数：使用C++11的default关键字，生成默认的构造函数，将根节点初始化为nullptr
拷贝构造函数：通过递归调用Copy函数实现深拷贝，确保新对象与原对象相互独立
赋值运算符：采用"拷贝交换"技术，先创建传入对象的副本，然后交换当前对象与副本的根节点指针，保证异常安全性
析构函数：调用Destory函数递归释放所有节点的内存，防止内存泄漏

插入操作（Insert）

插入操作是构建搜索二叉树的基础，其实现逻辑如下：

代码语言：javascript

AI代码解释

bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { return false; // 键值已存在，插入失败 } } // 找到插入位置，创建新节点并连接到树中 cur = new Node(key); if (parent->_key > key) { parent->_left = cur; } else { parent->_right = cur; } return true; }

插入操作的步骤：

如果树为空，直接创建根节点
否则从根节点开始，比较当前节点值与插入值的大小：
- 若当前节点值小于插入值，向右转
- 若当前节点值大于插入值，向左转
- 若相等，说明键值已存在，插入失败
找到合适的插入位置（空指针处）后，创建新节点并连接到父节点

查找操作（Find）

查找是搜索二叉树的核心功能，利用树的特性可以高效地定位目标节点：

代码语言：javascript

AI代码解释

bool Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key < key) { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else { return true; // 找到目标节点 } } return false; // 未找到目标节点 }

查找操作的逻辑非常直观，与插入操作类似：

从根节点开始，比较当前节点值与目标值
根据大小关系决定向左还是向右查找
若找到相等的值，返回true
若遍历完所有可能的节点仍未找到，返回false

删除操作（Erase）

删除操作是搜索二叉树中最复杂的操作，需要考虑多种情况：

代码语言：javascript

AI代码解释

bool Erase(const K& key) { Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { // 找到要删除的节点，处理不同情况 if (cur->_left == nullptr) { // 情况1：左子树为空 if (cur == _root) { _root = _root->_right; } if (parent->_right == cur) { parent->_right = cur->_right; } else { parent->_left = cur->_right; } delete cur; } else if(cur->_right == nullptr) { // 情况2：右子树为空 if (cur == _root) { _root = _root->_left; } if (parent->_right == cur) { parent->_right = cur->_left; } else { parent->_left = cur->_left; } delete cur; } else { // 情况3：左右子树都不为空 Node* pMinRight = cur; Node* minRight = cur->_right; while (minRight->_left) { pMinRight = minRight; minRight = minRight->_left; } // 找到右子树中的最小节点（最左节点） swap(minRight->_key, cur->_key); // 删除右子树中的最小节点 if (pMinRight->_left == minRight) { pMinRight->_left = minRight->_right; } else { pMinRight->_right = minRight->_right; } delete minRight; } return true; } } return false; // 未找到要删除的节点 }

删除操作需要处理三种情况：