快捷導(dǎo)航

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，簡(jiǎn)稱BST）是一種基礎(chǔ)且重要的數(shù)據(jù)結(jié)構(gòu)，它在查找、插入和刪除操作上具有高效性。本文將圍繞搜索二叉樹的原理，結(jié)合C++代碼實(shí)現(xiàn)，深入探討這一數(shù)據(jù)結(jié)構(gòu)的核心特性與具體實(shí)現(xiàn)。

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

二叉搜索樹（Binary Search Tree，簡(jiǎn)稱 BST）是一種特殊的二叉樹，它滿足以下性質(zhì)：

對(duì)于樹中的每個(gè)節(jié)點(diǎn)，其左子樹中所有節(jié)點(diǎn)的值都小于該節(jié)點(diǎn)的值

對(duì)于樹中的每個(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) 級(jí)別的查找效率，但是?分查找有兩?缺陷：

需要存儲(chǔ)在?持下標(biāo)隨機(jī)訪問的結(jié)構(gòu)中，并且有序。
插?和刪除數(shù)據(jù)效率很低，因?yàn)榇鎯?chǔ)在下標(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)勢(shì)，我們可以利用節(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)可以存儲(chǔ)任意類型的數(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)深拷貝，確保新對(duì)象與原對(duì)象相互獨(dú)立
賦值運(yùn)算符：采用"拷貝交換"技術(shù)，先創(chuàng)建傳入對(duì)象的副本，然后交換當(dāng)前對(duì)象與副本的根節(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)值與插入值的大小：
- 若當(dāng)前節(jié)點(diǎn)值小于插入值，向右轉(zhuǎn)
- 若當(dāng)前節(jié)點(diǎn)值大于插入值，向左轉(zhuǎn)
- 若相等，說明鍵值已存在，插入失敗
找到合適的插入位置（空指針處）后，創(chuàng)建新節(jié)點(diǎn)并連接到父節(jié)點(diǎ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) → 右子樹，對(duì)于搜索二叉樹來說，中序遍歷的結(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)是有序的），搜索二叉樹會(huì)退化為鏈表，此時(shí)所有操作的時(shí)間復(fù)雜度都會(huì)退化為O(n)。為了避免這種情況，可以使用平衡二叉樹（如AVL樹、紅黑樹等）來保證樹的高度始終保持在O(log n)。

搜索二叉樹的應(yīng)用場(chǎng)景

搜索二叉樹在實(shí)際應(yīng)用中非常廣泛，以下是一些常見的應(yīng)用場(chǎng)景：

字典和映射：可以用搜索二叉樹實(shí)現(xiàn)字典結(jié)構(gòu)，提供快速的查找、插入和刪除操作。
數(shù)據(jù)庫(kù)索引：數(shù)據(jù)庫(kù)中的索引結(jié)構(gòu)通?；谒阉鳂涞淖兎N，如B樹、B+樹等，以支持高效的查詢操作。
編譯器符號(hào)表：編譯器在處理變量和函數(shù)聲明時(shí)，需要快速查找和插入符號(hào)，搜索二叉樹是一種合適的數(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;
};