【C++】二叉搜索树

发布于：2025-04-17 ⋅ 阅读:(28) ⋅ 点赞:(0)
一、概念与特性

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

  1. 左子树所有节点的值均小于根节点的值
  2. 右子树所有节点的值均大于根节点的值
  3. 左右子树也必须是二叉搜索树

        这种特性使得其查找时间复杂度在平衡状态下可达O(log⁡n)，例如当树为满二叉树时。

         

        增删查改的时间复杂度是O(h) h是树的高度 最坏情况下h是N。 

         理想情况下才是O(log⁡n)，还是要改进平衡树，一种叫AVL树，一种叫红黑树。这个后面写。

 二、代码实现
template<class K>
class BSTreeNode
{
public:
	BSTreeNode<K>* _right;
	BSTreeNode<K>* _left;

	BSTreeNode(const K& key)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
	{
	}

	K _key;
};

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

        搜索二叉树类里面的数据是指针，那么使用默认的构造函数就行。 

        节点结构（C++模板）

        1.插入数据

        非递归 

bool Insert(const T& n)
{
	if (_root == nullptr) {    // 处理空树
		_root = new Node(n);
		return true;
	}

	Node* parent = nullptr;
	Node* cur = _root;

	while (cur)    // 定位插入位置
	{
		if (cur->_key < n) {
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > n) {
			parent = cur;
			cur = cur->_left;
		}
		else {
			return false; //已经有一个值会插入失败，重复值处理
		}
	}

	cur = new Node(n);    // 创建新节点
	if (parent->_key < n) {    // 链接到父节点
		parent->_right = cur;
	}
	else {
		parent->_left = cur;
	}
	return true;
}
  1. 显式路径追踪：使用parent指针记录当前节点的父节点
  2. 循环定位：通过while循环代替递归调用栈
  3. 手动链接：需显式判断插入左/右子树

        递归

bool InsertR(const T& key)
{
	return _InsertR(_root,key);
}

//为了方便连接父节点，这里使用了引用。是非常巧妙的用法
bool _InsertR(Node*& node,const T& key)
{
	if (node==nullptr) {
		node = new Node(key); //相当于连接把父子节点连接起来了，这里是node是上一个节点右指针或者左指针的别名
		return true;
	}

	if (node->_key < key)
		return _InsertR(node->_right,key);
	else if(node->_key > key)
		return _InsertR(node->_left, key);
	else 
		return false;
}
  • 基线条件：当递归到空子树时，创建新节点作为该位置的新根。
  • 递归方向：通过比较节点值决定插入左/右子树。
  • 结构维护：每次递归返回当前子树根节点，确保父节点指针正确链接。
  • 时间复杂度：O(h)（h为树高），最坏情况（退化成链表）为O(n)。
  • 空间复杂度：O(h)（递归栈深度）。

        这里使用了一个非常巧妙的写法，使用了引用。

Node*& node

        node自己为空，但同时也是上一个节点的别名（node->_right、node->_left ）

  1. 指针引用传参：Node*& root允许直接修改父节点的左右指针。例如当递归到空节点时，root = new Node(...)实际上修改的是父节点的_left或_right指针。
  2. 隐式回溯：递归调用结束后自动返回调用栈，无需显式重新链接节点。
  3. 时间复杂度：平均O(log⁡n)，最坏O(n)（树退化为链表时）。

PS：这里建议记住怎么使用就可以的，其本质是个二级指针，除非指针的理解非常透彻，不然会感觉很绕。

特性 递归实现(_InsertR) 非递归实现(Insert)
代码复杂度 低 中（需处理父子指针链接）
内存消耗 O(h)（h为树高） O(1)
最大可处理树高 受限于系统栈深度 仅受内存限制
指针操作安全性 自动维护（引用传参） 需手动维护parent指针
可调试性 调用栈复杂 线性流程易跟踪 
// 通过返回值重建链接
Node* insert(Node* root, int key) 
{
    if (!root) 
        return new Node(key);
    if (key < root->key) 
        root->left = insert(root->left, key);
    else 
        root->right = insert(root->right, key);
    return root;
}

        递归的另一种写法，每次递归返回当前子树根节点，需要显式重新赋值给父节点指针

        2.查找数据

        非递归查找

bool Find(const T& n)
{
	Node* cur = _root;
	while (cur)
	{
		if (cur->_key < n) {
			cur = cur->_right;
		}
		else if (cur->_key > n) {
			cur = cur->_left;
		}
		else {
			return true;
		}
	}
	return false;
}

        递归查找

//递归查找
bool FindR(const T& key)
{
	return _FindR(_root,key);
}

bool _FindR(Node* node,const T& key)
{
	if (node==nullptr) {
		return false;
	}

	if (node->_left < key)
		return _FindR(node->_right, key);
	else if (node->_right > key)
		return _FindR(node->_left, key);
	else
		return true;

	return false;
}

        这个理解起来比较简单，要查找的值比节点大走右子树，比它小走左子树。

        3.删除数据

        删除数据要点就比较多了，其主要有三种情况：

删除场景 处理方式 时间复杂度
叶子节点（删除节点没有孩子） 直接删除，父节点指针置空 O(1)
单子节点（删除节点有一个孩子） 用子节点替代被删节点 O(1)
双子节点（删除节点有两个孩子） 找右子树最小节点（或左子树最大节点）替换被删节点，再递归删除替换节点 O(h)（树高）

 

        非递归 

bool Erase(const T& 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) {

				if (cur==_root) {
					_root = cur->_right;  //要删除的值是头节点的情况
				}
				else {

					if (cur == parent->_left) {
						parent->_left = cur->_right;
					}
					else {
						parent->_right = cur->_right;
					}
				}
				delete cur;
				cur = nullptr;
			}
			else if (cur->_right==nullptr) {

				if (cur==_root) {
					_root = _root->_left;
				}
				else {
					if (cur == parent->_left) {
						parent->_left = cur->_left;
					}
					else {
						parent->_right = cur->_left;
					}
				}
				delete cur;
				cur = nullptr;

			}
			else {
				//替换法删除
				//找到右子树的最小节点进行替换
				Node* minParent = cur;
				Node* Min = cur->_right;
				while (Min->_left) {
					minParent = Min;
					Min = Min->_left;
				}
					
				swap(cur->_key,Min->_key);
				if (minParent->_left == Min)
					minParent->_left = Min->_right;
				else
					minParent->_right = Min->_right;

				delete Min;
			}

			return true;
		}
	}

	return false;
}

  三种情况用代码表示就是：1.节点左为空 2.右为空 3.左右都不为空

       细节还是比较多的，这里能发现删除完成后没打乱数据，其还是一个搜索二叉树。

         其实看图就能看出来，为什么上面节点左为空 、右为空，整合了节点有一个孩子、没有孩子两种情况。（不要太认真思考为啥代码是这样的，这代码是根据搜索二叉树特性设计的，记住就行）

        递归

bool EraseR(const T& key)
{
	return _EraseR(_root,key);
}

bool _EraseR(Node*& node,const T& key)
{
	if (node == nullptr) {
		return false;
	}

	if (node->_key < key)
		return _EraseR(node->_right, key);    //大走右边
	else if (node->_key > key)
		return _EraseR(node->_left, key);     //小走左边
	else                                      //查找到数据后 进行删除  
	{
		Node* del = node;
		if (node->_left == nullptr)    //左为空
		{
			node = node->_right;
		}
		else if (node->_right == nullptr)    //右为空
		{
			node = node->_left;
		}
		else                          //两边都不为NULL   替换法删除 
		{
			Node* min = node->_right;    //找到右子树最小节点
			while (min->_left)
			{
				min = min->_left;
			}
			swap(min->_key,node->_key);
			return _EraseR(node->_right,key); //这一步是删除节点。走的是节点左边为NULL的情况

		}
		delete del;
		return true;
	}

	return false;
}

        这里也使用了 指针引用传参：参数Node*& root确保直接修改父节点的子指针。Node是parent 的 _left 或者 _right 的别名。

        过程跟上面差不多，也是先找数据，找到后判断是哪种种情况然后连接、删除节点。

return _EraseR(node->_right,key);

        这里替换后的删除比较巧妙，首先 key 被替换到了右子树的最小节点。然后继续去找key，这里其实变成了 递归删除叶子节点、单子节点的情况了。

        4.中序遍历

        通过中序遍历验证BST有序性。

void InOrder()
{
	_InOrder(_root);
}

void _InOrder(Node* root)
{
	if (root==nullptr) {
		return;
	}
	_InOrder(root->_left);
	cout << root->_key << endl;
	_InOrder(root->_right);
}
  • 原理：通过递归隐式维护调用栈，天然实现左-根-右的顺序。
  • 时间复杂度：O(n)，每个节点访问一次。
  • 空间复杂度：O(h)（h为树高，递归栈深度）

        由于BST遵循 左子树节点值 < 根节点值 < 右子树节点值 的规则，中序遍历（左-根-右） 会按升序输出所有节点值。这是验证BST有效性和提取有序数据的基础。

        非递归实现

void InOrder_NonRecursive(Node* root) {
    stack<Node*> stk;
    Node* cur = root;
    
    while (!stk.empty() || cur != nullptr) {
        // 向左遍历到底，模拟递归压栈
        while (cur != nullptr) {
            stk.push(cur);
            cur = cur->left;
        }
        // 弹栈访问节点，转向右子树
        Node* top = stk.top();
        stk.pop();
        cout << top->key << " ";
        cur = top->right;
    }
}
        5.拷贝问题
//强制生成默认构造。
BSTree() = default;

        默认的构造就能用，注意这里写了拷贝构造，编译器就不会自动生成默认的构造函数，要手动写一下。

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

	Node* copynode = new Node(node->_key);
	copynode->_left = _Copy(node->_left);
	copynode->_right = _Copy(node->_right);
	return copynode;
}

BSTree(const BSTree<T>& bst)
{
	_root = _Copy(bst._root);
}

        二叉搜索树的深拷贝需要递归复制每个节点及其子树，核心操作是前序遍历复制过程。

BSTree<T>& operator=(BSTree<T> k)
{
	swap(_root,k._root);
	return *this;
}

        拷贝赋值运算符重载，现代写法，前面有介绍。

        6.析构
~BSTree()
{
	_Destory(_root);
}

void _Destory(Node*& node)
{
	if (node == nullptr) {
		return;
	}
	_Destory(node->_left);
	_Destory(node->_right);
	delete node;
	node = nullptr;
}

        二叉搜索树的析构需要递归释放所有节点内存，核心逻辑采用后序遍历删除

  1. 后序遍历必要性
    必须保证子节点先于父节点被删除，若采用前序遍历会导致访问已释放内存。

  2. 引用参数的作用
    参数Node*& root实现：

    • 直接修改外部指针值（如_root）
    • 自动完成 root = nullptr 操作
    • 避免内存泄漏（传统指针参数无法修改原指针）
三、Key-Value模型

        Key-Value 模型通过键与值的关联存储，在保持二叉搜索树高效查找特性的基础上扩展了功能边界

特性 Key-Value 模型 Key 模型
存储内容 键 + 关联值 仅键
查找结果 返回键关联的完整数据 返回布尔存在性
典型应用 字典、数据库索引、缓存系统 黑白名单、存在性校验
内存占用 较高（需存储额外值） 较低 
    template<class K, class V>
struct BSTNode {
    BSTNode<K,V>* _left;
    BSTNode<K,V>* _right;
   
   BSTreeNode(const K& key,const V& value)
	    :_left(nullptr)
	    , _right(nullptr)
	    , _key(key)
	    ,_value(value)
    {
    }
private:
    K _key;    // 维持排序的键
    V _value;  // 存储关联数据
};

            节点包含键（Key）、值（Value）以及左右子节点指针。        键值对（Key-Value） 。

    键值映射

    • 每个键（Key）对应唯一的值（Value），支持通过键快速定位关联数据
    • 示例：字典应用中，单词（Key）映射到释义（Value）

    场景类型 Key-Value 模型优势 Key 模型局限性
    数据库索引 通过键直接获取记录地址或完整数据 仅能判断记录是否存在
    缓存系统 存储键对应的缓存内容（如网页、图像） 无法关联具体内容
    配置文件解析 键表示配置项，值存储配置参数 无法表达参数含义

    网站公告

    今日签到

    点亮在社区的每一天
    去签到

    热门文章

    最新发布