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

二叉搜索树（C++实现）

news 2025/8/3 13:45:50

二叉搜索树（C++实现）

本节的主要内容是：用C++实现二叉搜索树。目的是：为接下来的map和set两个容器的学习做铺垫。

一、简单认识一下二叉搜索树

二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树，其核心特性是通过节点值的有序性实现高效的查找、插入和删除操作。

核心定义与性质

二叉搜索树的每个节点最多有两个子节点（左子树和右子树），且满足以下关键条件：
对于树中的任意节点，其左子树中所有节点的值都小于该节点的值，且右子树中所有节点的值都大于该节点的值；同时，左子树和右子树本身也必须是二叉搜索树（递归定义）。

关键特点

有序性：二叉搜索树的中序遍历（左→根→右）结果是一个严格递增的序列，这是其最核心的特性。
递归结构：每个子树都遵循相同的规则，因此操作（如查找、插入）可通过递归或迭代高效实现。
高效操作：在平衡的情况下（左右子树高度接近），查找、插入、删除的时间复杂度为 O(log n)（n为节点数）；但在极端情况下（如退化为单链表），复杂度会退化为 O(n)（因此衍生出红黑树、AVL树等平衡二叉搜索树优化这一问题）。

关于重复值的说明

标准定义中通常默认节点值不重复。若需处理重复值，常见的扩展规则有：

允许左子树节点值“小于等于”当前节点值；
允许右子树节点值“大于等于”当前节点值；
单独用一个计数器记录重复次数。

二、实现二叉搜索树

代码

这里使用两种不同方法来实现二叉搜索树，一种是使用递归的，一种是不使用递归的。

BinarySearchTree.h（命名空间BST里主体逻辑是没有用递归的，BST_R里是全部使用递归的）

#pragma once
#include<iostream>
#include<cassert>
using namespace std;namespace BST
{template<class K>struct BinarySearchTreeNode{typedef BinarySearchTreeNode<K> TreeNode;TreeNode* _left;TreeNode* _right;K _key;BinarySearchTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}};template<class K>class BinarySearchTree{public:BinarySearchTree() = default;BinarySearchTree(const BinarySearchTree<K>& k){_root = Copy(k._root);}BinarySearchTree<K>& operator=(BinarySearchTree<K> k){swap(_root, k._root);return *this;}~BinarySearchTree(){Destroy(_root);}bool Find(const K& key){TreeNode* cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if (key > cur->_key){cur = cur->_right;}else{return true;}}return false;}bool Insert(const K& key){if (_root == nullptr){_root = new TreeNode(key);return true;}TreeNode* cur = _root;TreeNode* parent = nullptr;while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else{return false;}}cur = new TreeNode(key);if (key > parent->_key){parent->_right = cur;}else if(key < parent->_key){parent->_left = cur;}return true;}bool Erase(const K& key){assert(_root != nullptr);TreeNode* cur = _root;TreeNode* parent = cur;while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else{if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (cur == parent->_right){parent->_right = cur->_right;}else if (cur == parent->_left){parent->_left = cur->_right;}}delete cur;return true;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (cur == parent->_right){parent->_right = cur->_left;}else if (cur == parent->_left){parent->_left = cur->_left;}}delete cur;return true;}else{TreeNode* RightTreeMin = cur->_right;TreeNode* RightTreeMin_p = cur;while (RightTreeMin->_left != nullptr){RightTreeMin_p = RightTreeMin;RightTreeMin = RightTreeMin->_left;}cur->_key = RightTreeMin->_key;if (RightTreeMin_p->_left != RightTreeMin){RightTreeMin_p->_right = RightTreeMin->_right;}else{RightTreeMin_p->_left = RightTreeMin->_right;//注意}delete RightTreeMin;return true;}}}}void Inorder(){_Inorder(_root);cout << endl;}private:typedef BinarySearchTreeNode<K> TreeNode;TreeNode* _root = nullptr;void _Inorder(TreeNode* root){if (root == nullptr)//递归返回条件{return;}_Inorder(root->_left);cout << root->_key << " ";_Inorder(root->_right);}void Destroy(TreeNode* root){if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;}TreeNode* Copy(TreeNode* root){if (root == nullptr){return nullptr;}TreeNode* newRoot = new TreeNode(root->_key);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}};
}namespace BST_R
{template<class K>struct BinarySearchTreeNode{typedef BinarySearchTreeNode<K> TreeNode;TreeNode* _left;TreeNode* _right;K _key;BinarySearchTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}};template<class K>class BinarySearchTree{public:BinarySearchTree() = default;BinarySearchTree(const BinarySearchTree<K> & k){_root = Copy(k._root);}BinarySearchTree<K>& operator=(BinarySearchTree<K> k){swap(_root, k._root);return *this;}~BinarySearchTree(){Destroy(_root);}bool Find(const K& key){return _Find(_root, key);}bool Insert(const K& key){return _Insert(_root, key);}bool Erase(const K& key){return _Erase(_root, key);}void Inorder(){_Inorder(_root);cout << endl;}private:typedef BinarySearchTreeNode<K> TreeNode;TreeNode* _root = nullptr;bool _Find(TreeNode* root, const K& key){if (root == nullptr){return false;}if (key < root->_key){_Find(root->_left, key);}else if (key > root->_key){_Find(root->_right, key);}else{return true;}}bool _Insert(TreeNode*& root, const K& key){if (root == nullptr){root = new TreeNode(key);return true;}if (key < root->_key){_Insert(root->_left, key);}else if (key > root->_key){_Insert(root->_right, key);}else{return false;}}bool _Erase(TreeNode*& root, const K& key){if (root == nullptr){return false;}if (key < root->_key){_Erase(root->_left, key);}else if (key > root->_key){_Erase(root->_right, key);}else{TreeNode* del = root;if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{TreeNode* RightTreeMin = root->_right;while (RightTreeMin->_left != nullptr){RightTreeMin = RightTreeMin->_left;}swap(root->_key, RightTreeMin->_key);return _Erase(root->_right, key);}delete del;return true;}}void _Inorder(TreeNode* root){if (root == nullptr)//递归返回条件{return;}_Inorder(root->_left);cout << root->_key << " ";_Inorder(root->_right);}void Destroy(TreeNode* root){if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;}TreeNode* Copy(TreeNode* root){if (root == nullptr){return nullptr;}TreeNode* newRoot = new TreeNode(root->_key);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}};
}

test.cpp（测试）

#include"BinarySearchTree.h"namespace BST
{void test1(){int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BinarySearchTree<int> bt;for (const auto& e : a){bt.Insert(e);}bt.Inorder();for (const auto& e : a){bt.Erase(e);bt.Inorder();}}
}
namespace BST_R
{void test2(){int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BinarySearchTree<int> bt;for (const auto& e : a){bt.Insert(e);}bt.Inorder();for (const auto& e : a){bt.Erase(e);bt.Inorder();}}
}int main()
{BST::test1();BST_R::test2();return 0;
}

代码讲解

我们先讲命名空间BST里面的二叉搜索树：
在这里插入图片描述

在这里插入图片描述

补充

二叉搜索树的应用

**K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。 **

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

**KV模型：每一个关键码key，都有与之对应的值Value，即<Key,Value>的键值对。**该种方式在现实生活中非常常见：

比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<Word,Chinese>就构成一种键值对；
再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数<Word,Count>就是就构成一种键值对。

我们这节写的二叉搜索树的类型就是K模型的。当然了，你想写成KV模型也很简单，我们只需要在树节点的结构体里加上_value成员变量就ok了。其他的什么查找逻辑，插入删除逻辑都是一样的，通过_key找到目标节点之后，就相当于找到了_value。所以没啥不一样的。下面我也给你们贴出部分代码，我就不讲了：

// 改造二叉搜索树为KV结构 
template<class K, class V>struct BSTNode{BSTNode(const K& key = K(), const V& value = V()): _pLeft(nullptr) , _pRight(nullptr), _key(key), _Value(value){}BSTNode<T>* _pLeft;BSTNode<T>* _pRight;K _key;V _value};
template<class K, class V>class BSTree{typedef BSTNode<K, V> Node;typedef Node* PNode;public:BSTree(): _pRoot(nullptr){}PNode Find(const K& key);bool Insert(const K& key, const V& value)bool Erase(const K& key)private:PNode _pRoot;};
void TestBSTree3()
{// 输入单词，查找单词对应的中文翻译BSTree<string, string> dict;dict.Insert("string", "字符串");dict.Insert("tree", "树");dict.Insert("left", "左边、剩余");dict.Insert("right", "右边");dict.Insert("sort", "排序");// 插入词库中所有单词string str;while (cin>>str){BSTreeNode<string, string>* ret = dict.Find(str);if (ret == nullptr){cout << "单词拼写错误，词库中没有这个单词:" <<str <<endl;}else{cout << str << "中文翻译:" << ret->_value << endl;}}
}
void TestBSTree4()
{// 统计水果出现的次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };BSTree<string, int> countTree;for (const auto& str : arr){// 先查找水果在不在搜索树中// 1、不在，说明水果第一次出现，则插入<水果, 1>// 2、在，则查找到的节点中水果对应的次数++//BSTreeNode<string, int>* ret = countTree.Find(str);auto ret = countTree.Find(str);if (ret == NULL){countTree.Insert(str, 1);}else{ret->_value++;}}countTree.InOrder();
}