C++模擬實現(xiàn)二叉搜索樹功能
更新時間：2026年02月14日 10:23:50 作者：yuuki233233
二叉搜索樹（Binary Search Tree,BST）作為一種經典的樹形數(shù)據(jù)結構,憑借其高效的動態(tài)查找、插入和刪除特性,在計算機科學領域有著廣泛的應用,本文給大家介紹C++模擬實現(xiàn) 二叉搜索樹功能,感興趣的朋友跟隨小編一起看看吧
前言
二叉搜索樹（Binary Search Tree，BST）作為一種經典的樹形數(shù)據(jù)結構，憑借其高效的動態(tài)查找、插入和刪除特性，在計算機科學領域有著廣泛的應用。從底層實現(xiàn)來看，C++ 標準庫中的map、set、multimap、multiset等關聯(lián)式容器，其核心邏輯正是基于二叉搜索樹（紅黑樹作為其平衡優(yōu)化版本）構建。相較于面向對象編程中的多態(tài)特性（側重行為的動態(tài)綁定與代碼復用），二叉搜索樹聚焦于數(shù)據(jù)的有序存儲與高效檢索，其核心價值在于利用 “左子樹值≤根節(jié)點值≤右子樹值” 的結構性約束，將查找、插入、刪除操作的時間復雜度控制在近似 O(logN)（理想的平衡狀態(tài)下）；而在最壞的單支樹場景下，時間復雜度退化為 O(N)，這也體現(xiàn)了數(shù)據(jù)結構設計中 “結構與性能” 的強關聯(lián)性。
本文將從二叉搜索樹的核心定義出發(fā)，逐步拆解節(jié)點設計、樹的構建、插入、查找、刪除等核心操作的實現(xiàn)邏輯，并區(qū)分 “僅存關鍵碼（key）” 與 “鍵值對（key/value）” 兩種典型應用場景，最終給出完整的可運行代碼實現(xiàn)。代碼實現(xiàn)過程中兼顧 C++11 語法特性（如
using類型別名）、代碼封裝性（私有成員訪問控制）與邏輯健壯性（邊界條件處理），力求在清晰性與工程性之間找到平衡。
一、二叉搜索樹的概念
二叉搜索樹又稱二叉排序樹，滿足以下核心特性：
- 左子樹不為空，則左子樹上所有節(jié)點的值都小于等于根節(jié)點的值
- 右子樹不為空，則右子樹上所有節(jié)點的值都大于等于根節(jié)點的值
- 左右子樹也分別為二叉搜索樹
- 二叉搜索樹中可以支持插入相同的值，也可以不支持插入相等的值。其中
map、set、multimap、multiset系列的如期底層就是二叉搜索樹，其中map、set不支持插入相等值，multimap、multiset支持插入相等的值。
二、二叉搜索樹的性能分析
最好情況：樹的結構接近完全二叉樹，高度為 logN，此時查找、插入、刪除操作的時間復雜度為 O(logN)；
最壞情況：樹退化為單支樹，高度為 N，此時操作的時間復雜度退化為 O(N)。
三、二叉搜索樹的整體框架
3.1 節(jié)點
二叉搜索樹本質是由節(jié)點連接而成的鏈式結構，每個節(jié)點包含關鍵碼、左孩子指針、右孩子指針，具體實現(xiàn)如下：
#pragma once
#include<iostream>
using namespace std;
// 二叉搜索樹節(jié)點結構
template<class K>
struct BSTNode
{
K _key; // 節(jié)點存儲的關鍵碼
BSTNode<K>* _left; // 左孩子節(jié)點指針
BSTNode<K>* _right; // 右孩子節(jié)點指針
// 構造函數(shù)：初始化節(jié)點
BSTNode(const K& key)
:_key(key)
, _left(nullptr)
, _right(nullptr)
{
}
};3.2 樹的類封裝
將二叉搜索樹封裝為類，根節(jié)點作為私有成員（保證數(shù)據(jù)封裝性），使用 C++11 的 using 簡化節(jié)點類型名：
template<class K>
class BSTree
{
using Node = BSTNode<K>; // C++11 類型別名，替代傳統(tǒng) typedef
public:
// 核心操作聲明（插入、查找、刪除、中序遍歷）
bool Insert(const K& key);
bool Find(const K& key);
bool Erase(const K& key);
void InOrder();
private:
// 私有輔助函數(shù)：中序遍歷的遞歸實現(xiàn)
void _InOrder(Node* root);
Node* _root = nullptr; // 根節(jié)點指針，初始化為空
};3.3 插入
插入邏輯：
- 若樹為空，直接創(chuàng)建新節(jié)點作為根節(jié)點；
- 若樹不為空，按二叉搜索樹規(guī)則遍歷：插入值大于當前節(jié)點則向右走，小于則向左走，找到空位置后插入新節(jié)點；
- 若不支持重復值插入，遇到與當前節(jié)點值相等的情況則返回插入失敗。
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
template<class K>
bool BSTree<K>::Insert(const K& key)
{
// 情況1：樹為空，直接創(chuàng)建根節(jié)點
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
// 情況2：樹不為空，遍歷找到插入位置
Node* cur = _root;
Node* parent = nullptr; // 記錄當前節(jié)點的父節(jié)點（用于后續(xù)連接新節(jié)點）
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right; // 大于當前節(jié)點，向右遍歷
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left; // 小于當前節(jié)點，向左遍歷
}
else
{
// 找到相等值，不插入（若支持重復值，可改為向右/左遍歷）
return false;
}
}
// 找到空位置，創(chuàng)建新節(jié)點并連接到父節(jié)點
cur = new Node(key);
if (parent->_key < key)
{
parent->_right = cur; // 新節(jié)點值更大，連接到父節(jié)點右孩子
}
else
{
parent->_left = cur; // 新節(jié)點值更小，連接到父節(jié)點左孩子
}
return true;
}3.4 查找
- 從根節(jié)點開始比較：查找值大于根節(jié)點則向右查找，小于則向左查找；
- 遍歷至空節(jié)點則說明查找失敗，找到相等值則返回成功；
- 若支持重復值，通常要求返回中序遍歷的第一個目標值（需額外邏輯，本文實現(xiàn)基礎版）。
template<class K>
bool BSTree<K>::Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right; // 大于當前節(jié)點，向右查找
}
else if (cur->_key > key)
{
cur = cur->_left; // 小于當前節(jié)點，向左查找
}
else
{
return true; // 找到目標值，返回成功
}
}
return false; // 遍歷至空，查找失?。ㄑa充原代碼缺失的返回值）
}3.5 刪除
刪除邏輯：
- 先查找目標節(jié)點：不存在則返回失?。?/li>
- 存在則分三種情況處理（合并葉子節(jié)點與單孩子節(jié)點邏輯）：
- 左孩子為空：將父節(jié)點的對應指針指向當前節(jié)點的右孩子，刪除當前節(jié)點；
- 右孩子為空：將父節(jié)點的對應指針指向當前節(jié)點的左孩子，刪除當前節(jié)點；
左右孩子都不為空：采用 “替換法”—— 找右子樹的最小節(jié)點（最左節(jié)點）或左子樹的最大節(jié)點（最右節(jié)點）替換目標節(jié)點，再刪除替換節(jié)點（替換節(jié)點必為單孩子 / 葉子節(jié)點）。
template<class K>
bool BSTree<K>::Erase(const K& key)
{
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else // 找到要刪除的節(jié)點
{
// 情況1：左孩子為空（葉子節(jié)點/僅右孩子）
if (cur->_left == nullptr)
{
// 處理根節(jié)點刪除的特殊情況
if (cur == _root)
{
_root = cur->_right;
}
else
{
// 父節(jié)點的左/右指針指向當前節(jié)點的右孩子
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur; // 釋放節(jié)點內存
}
// 情況2：右孩子為空（葉子節(jié)點/僅左孩子）
else if (cur->_right == nullptr)
{
// 處理根節(jié)點刪除的特殊情況
if (cur == _root)
{
_root = cur->_left;
}
else
{
// 父節(jié)點的左/右指針指向當前節(jié)點的左孩子
if (parent->_right == cur)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
delete cur; // 釋放節(jié)點內存
}
// 情況3：左右孩子都不為空（替換法刪除）
else
{
// 找右子樹的最小節(jié)點（最左節(jié)點）作為替換節(jié)點
Node* replaceParent = cur;
Node* replace = cur->_right;
while (replace->_left) // 遍歷至右子樹最左節(jié)點
{
replaceParent = replace;
replace = replace->_left;
}
// 替換目標節(jié)點的關鍵碼
cur->_key = replace->_key;
// 連接替換節(jié)點的父節(jié)點與替換節(jié)點的右孩子（替換節(jié)點左必為空）
if (replaceParent->_left == replace)
{
replaceParent->_left = replace->_right;
}
else
{
replaceParent->_right = replace->_right;
}
delete replace; // 釋放替換節(jié)點內存
}
return true; // 刪除成功
}
}
return false; // 未找到目標節(jié)點，刪除失敗
}3.6 中序遍歷（驗證二叉搜索樹的有序性）
二叉搜索樹的中序遍歷結果為升序序列，是驗證樹結構正確性的核心方式。通過 “公有接口 + 私有遞歸函數(shù)” 的方式訪問私有根節(jié)點：
template<class K>
void BSTree<K>::_InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left); // 遍歷左子樹
cout << root->_key << " "; // 訪問當前節(jié)點
_InOrder(root->_right); // 遍歷右子樹
}
template<class K>
void BSTree<K>::InOrder()
{
_InOrder(_root); // 調用私有遞歸函數(shù)
cout << endl;
}四、二叉搜索樹的兩種應用場景
4.1 僅關鍵碼（key）場景
核心特點
節(jié)點僅存儲關鍵碼 key，操作僅關注 “key 是否存在”，不支持修改 key（修改會破壞樹的結構），支持增刪查。
典型場景
- 小區(qū)車庫車牌驗證：錄入業(yè)主車牌，車輛進場時查找車牌是否存在；
- 英文單詞拼寫檢查：將詞庫單詞存入樹，遍歷文章單詞并查找，不存在則標紅。
4.2 鍵值對（key/value）場景
核心特點
節(jié)點存儲 key + value（value 為任意類型），增刪查以 key 為關鍵字，支持修改 value（不修改 key）。
典型場景
- 中英互譯字典：key 為英文單詞，value 為中文釋義，查找 key 即可獲取釋義；
- 停車計費系統(tǒng)：key 為車牌，value 為入場時間，離場時查找 key 計算停車時長；
- 單詞詞頻統(tǒng)計：key 為單詞，value 為出現(xiàn)次數(shù)，查找單詞存在則 value++。
// 鍵值對版本的節(jié)點結構
template<class K, class T>
struct BSTNodeKV
{
K _key;
T _value;
BSTNodeKV<K, T>* _left;
BSTNodeKV<K, T>* _right;
BSTNodeKV(const K& key, const T& value)
:_key(key)
, _value(value)
, _left(nullptr)
, _right(nullptr)
{
}
};
// 鍵值對版本的二叉搜索樹
template<class K, class T>
class BSTreeKV
{
using Node = BSTNodeKV<K, T>;
public:
// 插入鍵值對
bool Insert(const K& key, const T& value)
{
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false; // 不支持重復key
}
}
cur = new Node(key, value);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
// 查找key并返回value的指針（方便修改value）
T* 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 &(cur->_value); // 返回value地址，支持修改
}
}
return nullptr; // 查找失敗
}
// 刪除（邏輯與key版本一致，略）
bool Erase(const K& key)
{
Node* cur = _root;
Node* parent = nullptr;
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 (parent->_left == cur)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_right == cur)
parent->_right = cur->_left;
else
parent->_left = cur->_left;
}
delete cur;
}
else
{
Node* replaceParent = cur;
Node* replace = cur->_right;
while (replace->_left)
{
replaceParent = replace;
replace = replace->_left;
}
// 替換key和value
cur->_key = replace->_key;
cur->_value = replace->_value;
if (replaceParent->_left == replace)
replaceParent->_left = replace->_right;
else
replaceParent->_right = replace->_right;
delete replace;
}
return true;
}
}
return false;
}
// 中序遍歷（打印key和value）
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << "key: " << root->_key << ", value: " << root->_value << " ";
_InOrder(root->_right);
}
Node* _root = nullptr;
};五、代碼易錯說明
代碼規(guī)范性優(yōu)化：
- 類的成員函數(shù)聲明與實現(xiàn)分離，提升代碼可讀性；
- 變量命名語義化（如
replaceParent替代原parent，避免歧義）； - 補充關鍵邏輯注釋，降低維護成本。
功能增強：
- 鍵值對版本的查找函數(shù)返回
value指針，支持修改 value； - 中序遍歷打印 key 和 value，便于驗證鍵值對的正確性。
- 鍵值對版本的查找函數(shù)返回
六、使用示例
// 測試key版本的二叉搜索樹
void TestBSTree()
{
BSTree<int> t;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto e : a)
{
t.Insert(e);
}
cout << "中序遍歷（升序）：";
t.InOrder(); // 輸出：1 3 4 6 7 8 10 13 14
cout << "查找6：" << (t.Find(6) ? "成功" : "失敗") << endl; // 成功
cout << "刪除3：" << (t.Erase(3) ? "成功" : "失敗") << endl; // 成功
cout << "刪除后中序遍歷：";
t.InOrder(); // 輸出：1 4 6 7 8 10 13 14
}
// 測試鍵值對版本的二叉搜索樹
void TestBSTreeKV()
{
BSTreeKV<string, int> dict;
dict.Insert("apple", 1);
dict.Insert("banana", 2);
dict.Insert("orange", 3);
cout << "中序遍歷鍵值對：";
dict.InOrder(); // 輸出：key: apple, value: 1 key: banana, value: 2 key: orange, value: 3
// 修改banana的value
int* p = dict.Find("banana");
if (p)
{
*p = 20;
}
cout << "修改后中序遍歷：";
dict.InOrder(); // 輸出：key: apple, value: 1 key: banana, value: 20 key: orange, value: 3
}
int main()
{
TestBSTree();
TestBSTreeKV();
return 0;
}總結
二叉搜索樹的核心是 “有序性”，其所有操作均圍繞這一特性展開。本文實現(xiàn)的基礎版本覆蓋了二叉搜索樹的核心功能，而實際工程中（如 C++ 標準庫）會通過紅黑樹對其進行平衡優(yōu)化，避免單支樹的性能退化。理解二叉搜索樹的底層邏輯，是掌握關聯(lián)式容器、高效檢索算法的關鍵基礎。
到此這篇關于【C++】模擬實現(xiàn) 二叉搜索樹的文章就介紹到這了,更多相關C++二叉搜索樹內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了c++ 隨機數(shù)問題的相關研究，幫助大家更好的理解和學習使用c++，感興趣的朋友可以了解下2021-03-03
.ini文件是Initialization?File的縮寫,即初始化文件,下面這篇文章主要給大家介紹了關于Qt讀寫ini文件(含源碼+注釋)的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2022-10-10
打磚塊游戲是一種動作電子游戲的名稱。玩家操作一根螢幕上水平的“棒子”，讓一顆不斷彈來彈去的“球”在撞擊作為過關目標消去的“磚塊”的途中不會落到螢幕底下。球碰到磚塊、棒子與底下以外的三邊會反彈，落到底下會失去一顆球，把磚塊全部消去就可以破關2021-11-11
STL是C++標準庫的重要組成部分,不僅是一個可復用的 組件庫,而且是一個包羅數(shù)據(jù)結構與算法的軟件框架,本文給大家介紹C++ STL中容器string超詳細講解,感興趣的朋友跟隨小編一起看看吧2025-10-10
使用C語言實現(xiàn)珠璣妙算Mastermind小游戲
這篇文章主要介紹了使用C語言實現(xiàn)珠璣妙算Mastermind小游戲,這是一款益智類多人游戲游戲,非常有趣,需要的朋友可以參考下2023-03-03
構造函數(shù)是一種特殊的函數(shù)，它用于在創(chuàng)建對象時初始化對象的值。在本文中，我們將學習C++的構造函數(shù)以及如何使用它們來創(chuàng)建對象，希望對大家有所幫助2023-05-05
這篇文章主要為大家詳細介紹了C語言實現(xiàn)經典24點紙牌益智游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-10-10
這篇文章主要介紹了c++11&14-智能指針的要點，文中代碼非常詳細，供大家學習和參考，感興趣的朋友可以了解下2020-06-06
下面小編就為大家?guī)硪黄P于STL的erase()陷阱-迭代器失效問題的總結。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-12-12
這篇文章主要為大家詳細介紹了C++實現(xiàn)簡單五子棋游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-05-05