C++二叉搜索樹及其實(shí)現(xiàn)方法實(shí)例代碼
更新時(shí)間：2025年06月30日 09:30:43 作者：zzh_zao
這篇文章主要介紹了C++二叉搜索樹及其實(shí)現(xiàn)方法的相關(guān)資料,搜索二叉樹是一種左小右大的二叉樹結(jié)構(gòu),支持高效查找、插入和刪除操作,需要的朋友可以參考下
前言
搜索二叉樹（Binary Search Tree，簡稱BST）是一種基礎(chǔ)且重要的數(shù)據(jù)結(jié)構(gòu)，它在查找、插入和刪除操作上具有高效性。本文將圍繞搜索二叉樹的原理，結(jié)合C++代碼實(shí)現(xiàn)，深入探討這一數(shù)據(jù)結(jié)構(gòu)的核心特性與具體實(shí)現(xiàn)。
一.二叉搜索樹的基本概念
二叉搜索樹（Binary Search Tree，簡稱 BST）是一種特殊的二叉樹，它滿足以下性質(zhì)：
對于樹中的每個(gè)節(jié)點(diǎn)，其左子樹中所有節(jié)點(diǎn)的值都小于該節(jié)點(diǎn)的值
對于樹中的每個(gè)節(jié)點(diǎn)，其右子樹中所有節(jié)點(diǎn)的值都大于該節(jié)點(diǎn)的值
左右子樹也分別是二叉搜索樹
這種特性使得二叉搜索樹在查找、插入和刪除操作上具有較高的效率，平均時(shí)間復(fù)雜度為 O (log n)。
二.二叉搜索樹的性能分析
最優(yōu)情況下，?叉搜索樹為完全?叉樹(或者接近完全?叉樹)，其?度為：log2 N
最差情況下，?叉搜索樹退化為單?樹(或者類似單?)，其?度為：N
所以綜合???叉搜索樹增刪查改時(shí)間復(fù)雜度為：O(N)
?分查找也可以實(shí)現(xiàn)O(log2N) 級別的查找效率，但是?分查找有兩?缺陷：
需要存儲在?持下標(biāo)隨機(jī)訪問的結(jié)構(gòu)中，并且有序。
插?和刪除數(shù)據(jù)效率很低，因?yàn)榇鎯υ谙聵?biāo)隨機(jī)訪問的結(jié)構(gòu)中，插?和刪除數(shù)據(jù)?般需要挪動(dòng)數(shù)據(jù)。
這?也就體現(xiàn)出了平衡?叉搜索樹的價(jià)值。
三.二叉搜索樹的實(shí)現(xiàn)
搜索二叉樹的基本概念與特性
搜索二叉樹是一種特殊的二叉樹，它滿足以下性質(zhì)：
- 若任意節(jié)點(diǎn)的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值均小于該節(jié)點(diǎn)的值
- 若任意節(jié)點(diǎn)的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值均大于該節(jié)點(diǎn)的值
- 任意節(jié)點(diǎn)的左、右子樹也分別為搜索二叉樹
- 沒有鍵值相等的節(jié)點(diǎn)
這些性質(zhì)使得搜索二叉樹在進(jìn)行查找操作時(shí)具有天然的優(yōu)勢，我們可以利用節(jié)點(diǎn)值的大小關(guān)系快速縮小查找范圍，類似于有序數(shù)組的二分查找。
搜索二叉樹的節(jié)點(diǎn)結(jié)構(gòu)設(shè)計(jì)
首先來看搜索二叉樹的節(jié)點(diǎn)結(jié)構(gòu)實(shí)現(xiàn)：
template<class K>
struct BSTreeNode
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
BSTNode(const K& key)
:_key(key)
, _left(nullptr)
, _right(nullptr)
{
}
};
_key：節(jié)點(diǎn)的關(guān)鍵字，用于比較和查找_left：指向左子節(jié)點(diǎn)的指針_right：指向右子節(jié)點(diǎn)的指針- 構(gòu)造函數(shù)：初始化節(jié)點(diǎn)的關(guān)鍵字，并將左右子節(jié)點(diǎn)指針置為
nullptr
節(jié)點(diǎn)采用模板設(shè)計(jì)，使得該結(jié)構(gòu)可以存儲任意類型的數(shù)據(jù)，只要該類型支持比較運(yùn)算。
搜索二叉樹的類結(jié)構(gòu)與核心操作
類的基本結(jié)構(gòu)
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
// 構(gòu)造、拷貝構(gòu)造、賦值運(yùn)算符、析構(gòu)函數(shù)
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:
// 中序遍歷的遞歸輔助函數(shù)
void _InOrder(Node* root);
// 拷貝構(gòu)造的遞歸輔助函數(shù)
Node* Copy(Node* root);
// 析構(gòu)函數(shù)的遞歸輔助函數(shù)
void Destory(Node* root);
private:
Node* _root = nullptr;
};
構(gòu)造與析構(gòu)函數(shù)
- 默認(rèn)構(gòu)造函數(shù)：使用C++11的
default關(guān)鍵字，生成默認(rèn)的構(gòu)造函數(shù)，將根節(jié)點(diǎn)初始化為nullptr - 拷貝構(gòu)造函數(shù)：通過遞歸調(diào)用
Copy函數(shù)實(shí)現(xiàn)深拷貝，確保新對象與原對象相互獨(dú)立 - 賦值運(yùn)算符：采用"拷貝交換"技術(shù)，先創(chuàng)建傳入對象的副本，然后交換當(dāng)前對象與副本的根節(jié)點(diǎn)指針，保證異常安全性
- 析構(gòu)函數(shù)：調(diào)用
Destory函數(shù)遞歸釋放所有節(jié)點(diǎn)的內(nèi)存，防止內(nèi)存泄漏
插入操作（Insert）
插入操作是構(gòu)建搜索二叉樹的基礎(chǔ)，其實(shí)現(xiàn)邏輯如下：
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; // 鍵值已存在，插入失敗
}
}
// 找到插入位置，創(chuàng)建新節(jié)點(diǎn)并連接到樹中
cur = new Node(key);
if (parent->_key > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
插入操作的步驟：
- 如果樹為空，直接創(chuàng)建根節(jié)點(diǎn)
- 否則從根節(jié)點(diǎn)開始，比較當(dāng)前節(jié)點(diǎn)值與插入值的大?。?ul>
- 若當(dāng)前節(jié)點(diǎn)值小于插入值，向右轉(zhuǎn)
- 若當(dāng)前節(jié)點(diǎn)值大于插入值，向左轉(zhuǎn)
- 若相等，說明鍵值已存在，插入失敗
查找操作（Find）
查找是搜索二叉樹的核心功能，利用樹的特性可以高效地定位目標(biāo)節(jié)點(diǎn)：
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; // 找到目標(biāo)節(jié)點(diǎn)
}
}
return false; // 未找到目標(biāo)節(jié)點(diǎn)
}
查找操作的邏輯非常直觀，與插入操作類似：
- 從根節(jié)點(diǎn)開始，比較當(dāng)前節(jié)點(diǎn)值與目標(biāo)值
- 根據(jù)大小關(guān)系決定向左還是向右查找
- 若找到相等的值，返回
true - 若遍歷完所有可能的節(jié)點(diǎn)仍未找到，返回
false
刪除操作（Erase）
刪除操作是搜索二叉樹中最復(fù)雜的操作，需要考慮多種情況：
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 {
// 找到要?jiǎng)h除的節(jié)點(diǎn)，處理不同情況
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;
}
// 找到右子樹中的最小節(jié)點(diǎn)（最左節(jié)點(diǎn)）
swap(minRight->_key, cur->_key);
// 刪除右子樹中的最小節(jié)點(diǎn)
if (pMinRight->_left == minRight)
{
pMinRight->_left = minRight->_right;
}
else
{
pMinRight->_right = minRight->_right;
}
delete minRight;
}
return true;
}
}
return false; // 未找到要?jiǎng)h除的節(jié)點(diǎn)
}
刪除操作需要處理三種情況：
- 左子樹為空：直接用右子樹替換當(dāng)前節(jié)點(diǎn)
- 右子樹為空：直接用左子樹替換當(dāng)前節(jié)點(diǎn)
- 左右子樹都不為空：
- 找到當(dāng)前節(jié)點(diǎn)右子樹中的最小節(jié)點(diǎn)（最左節(jié)點(diǎn)）
- 將該最小節(jié)點(diǎn)的值與當(dāng)前節(jié)點(diǎn)的值交換
- 刪除原來的最小節(jié)點(diǎn)（此時(shí)該節(jié)點(diǎn)最多只有一個(gè)右子樹）
這種處理方式確保了刪除節(jié)點(diǎn)后，搜索二叉樹的性質(zhì)仍然保持。
中序遍歷（InOrder）
中序遍歷可以將搜索二叉樹中的節(jié)點(diǎn)按從小到大的順序輸出，這是搜索二叉樹的一個(gè)重要特性：
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << ' ';
_InOrder(root->_right);
}
中序遍歷的順序是：左子樹 → 根節(jié)點(diǎn) → 右子樹，對于搜索二叉樹來說，中序遍歷的結(jié)果正好是有序的。
搜索二叉樹的性能分析
時(shí)間復(fù)雜度
- 查找操作：在平均情況下，時(shí)間復(fù)雜度為O(log n)，其中n是樹中節(jié)點(diǎn)的數(shù)量。這是因?yàn)槊看伪容^都可以將查找范圍縮小一半，類似于二分查找。
- 插入操作：平均時(shí)間復(fù)雜度也是O(log n)，因?yàn)椴迦氩僮餍枰日业胶线m的位置，這與查找操作的過程類似。
- 刪除操作：平均時(shí)間復(fù)雜度同樣為O(log n)，刪除操作的主要時(shí)間消耗在查找節(jié)點(diǎn)和處理不同情況上。
空間復(fù)雜度
- 搜索二叉樹的空間復(fù)雜度為O(n)，其中n是樹中節(jié)點(diǎn)的數(shù)量，因?yàn)樾枰獮槊總€(gè)節(jié)點(diǎn)分配內(nèi)存空間。
最壞情況
搜索二叉樹的性能依賴于樹的高度，在最壞情況下（如插入的節(jié)點(diǎn)是有序的），搜索二叉樹會退化為鏈表，此時(shí)所有操作的時(shí)間復(fù)雜度都會退化為O(n)。為了避免這種情況，可以使用平衡二叉樹（如AVL樹、紅黑樹等）來保證樹的高度始終保持在O(log n)。
搜索二叉樹的應(yīng)用場景
搜索二叉樹在實(shí)際應(yīng)用中非常廣泛，以下是一些常見的應(yīng)用場景：
- 字典和映射：可以用搜索二叉樹實(shí)現(xiàn)字典結(jié)構(gòu)，提供快速的查找、插入和刪除操作。
- 數(shù)據(jù)庫索引：數(shù)據(jù)庫中的索引結(jié)構(gòu)通?；谒阉鳂涞淖兎N，如B樹、B+樹等，以支持高效的查詢操作。
- 編譯器符號表：編譯器在處理變量和函數(shù)聲明時(shí)，需要快速查找和插入符號，搜索二叉樹是一種合適的數(shù)據(jù)結(jié)構(gòu)。
- 文件系統(tǒng)目錄結(jié)構(gòu)：文件系統(tǒng)中的目錄結(jié)構(gòu)可以用搜索樹來組織，以便快速查找文件和目錄。
- 優(yōu)先隊(duì)列：雖然優(yōu)先隊(duì)列更常用堆來實(shí)現(xiàn)，但搜索二叉樹也可以用于實(shí)現(xiàn)優(yōu)先隊(duì)列。
總體代碼實(shí)現(xiàn)
using namespace std;
template<class K>
struct BSTreeNode
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
BSTNode(const K& key)
:_key(key)
, _left(nullptr)
, _right(nullptr)
{
}
};
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
BSTree() = default;
BSTree(const BSTree<K>& t)
{
_root = Copy(t._root);
}
BSTree<K>& operator=(BSTree<K> t)
{
swap(_root, t._root);
return *this;
}
~BSTree()
{
Destory(_root);
_root = nullptr;
}
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;
}
}
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;
}
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)
{
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)
{
if (cur == _root)
{
_root = _root->_left;
}
if (parent->_right == cur)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
delete cur;
}
else
{
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;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << ' ';
_InOrder(root->_right);
}
Node* Copy(Node* root)
{
if (root == nullptr)
return;
Node* copy = new Node(root->_key);
copy->_left = Copy(root->_left);
copy->_right = Copy(root->_right);
return copy;
}
void Destory(Node* root)
{
if (root == nullptr)
{
return;
}
Destory(root->_left);
Destory(root->_right);
delete root;
}
private:
Node* _root = nullptr;
};
總結(jié)
到此這篇關(guān)于C++二叉搜索樹及其實(shí)現(xiàn)方法的文章就介紹到這了,更多相關(guān)C++二叉搜索樹實(shí)現(xiàn)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
c++ TCHAR轉(zhuǎn)string導(dǎo)致中文缺失或亂碼問題及解決
這篇文章主要介紹了c++ TCHAR轉(zhuǎn)string導(dǎo)致中文缺失或亂碼問題及解決方案,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-08-08
visual studio code 配置C++開發(fā)環(huán)境的教程詳解 （windows 開發(fā)環(huán)境）
這篇文章主要介紹了 windows 開發(fā)環(huán)境下visual studio code 配置C++開發(fā)環(huán)境的圖文教程，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-03-03
這篇文章主要給大家分享的是C++中atof?函數(shù)的介紹，在?stdlib.h?中?atof?函數(shù),可用于將?char?字符串轉(zhuǎn)為?float?/?double?浮點(diǎn)數(shù)類型，想具體了解語法的小伙伴可以參考下面文章的內(nèi)容，希望對大家有所幫助2021-11-11
這篇文章主要為大家詳細(xì)介紹了C語言開發(fā)實(shí)現(xiàn)貪吃蛇游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-07-07
C++可調(diào)用對象callable object深入分析
所謂的callable object，表示可以被某種方式調(diào)用其某些函數(shù)的對象。它可以是：一個(gè)函數(shù)、一個(gè)指向成員函數(shù)的指針、一個(gè)函數(shù)對象，該對象擁有operator()、一個(gè)lambda表達(dá)式，嚴(yán)格的說它是一種函數(shù)對象2022-08-08
QT連接SQLServer數(shù)據(jù)庫的實(shí)現(xiàn)
要使用Qt連接SQL Server數(shù)據(jù)庫,需要使用Qt提供的SQL模塊和SQL Server驅(qū)動(dòng)程序,具有一定的參考價(jià)值,感興趣的可以了解一下2023-09-09
Microsoft Visual C++ 安裝失敗 0x80070666的問題解
本文主要介紹了Microsoft Visual C++ 安裝失敗 0x80070666的問題解決,錯(cuò)誤可能由已安裝其他VisualC++版本、VisualC++安裝異常、Windows更新計(jì)劃安裝同一VisualC++包等原因引起,下面就來介紹一下解決方案,感興趣的可以了解一下2025-03-03
這篇文章主要介紹了C++中的最小生成樹算法超詳細(xì)教程,最小生成樹的最著名的算法有兩個(gè), 一個(gè)是Prim算法, 另一個(gè)當(dāng)然就是Kruskal算法, 接下來, 我將盡我所能的介紹這兩個(gè)算法, 也算是對自己學(xué)習(xí)的一個(gè)回顧吧,需要的朋友可以參考下2023-08-08
這篇文章主要介紹了C++?多繼承詳情，C++支持多繼承，即允許一個(gè)類同時(shí)繼承多個(gè)類。只有C++等少數(shù)語言支持多繼承，下面我們就來看看具體的多繼承介紹吧,需要的朋友可以參考一下2022-03-03
這篇文章主要介紹了C++ 兩個(gè)vector對象拼接方式，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-11-11