国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

〖數(shù)據(jù)結(jié)構(gòu)〗一棵有點自律的樹——搜索二叉樹

2年前作者：花想云分類：Toy博客閱讀(24)違法舉報

這篇具有很好參考價值的文章主要介紹了〖數(shù)據(jù)結(jié)構(gòu)〗一棵有點自律的樹——搜索二叉樹。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

〖數(shù)據(jù)結(jié)構(gòu)〗一棵有點自律的樹——搜索二叉樹

??專欄導(dǎo)讀

??作者簡介：花想云，在讀本科生一枚，致力于 C/C++、Linux 學(xué)習(xí)。

??本文收錄于 C++系列，本專欄主要內(nèi)容為 C++ 初階、C++ 進(jìn)階、STL 詳解等，專為大學(xué)生打造全套 C++ 學(xué)習(xí)教程，持續(xù)更新！

??相關(guān)專欄推薦：C語言初階系列 、C語言進(jìn)階系列 、數(shù)據(jù)結(jié)構(gòu)與算法、Linux從入門到精通

??文章導(dǎo)讀

本章我們將認(rèn)識一種新的二叉樹——搜索二叉樹。這棵樹有個神奇的功能就是會對數(shù)據(jù)自動排序且有著非常高的查找效率。搜索二叉樹作為set、map的基礎(chǔ)結(jié)構(gòu)，同樣又是接下來將要學(xué)到的AVL樹以及紅黑樹的實現(xiàn)基礎(chǔ)非常值得我們?nèi)ド钊雽W(xué)習(xí)~

〖數(shù)據(jù)結(jié)構(gòu)〗一棵有點自律的樹——搜索二叉樹

??搜索二叉樹概念

二叉搜索樹本質(zhì)上也是一種二叉樹，只不過多了一個約束規(guī)則——

若一棵二叉樹不為空，則：

若它的左子樹不為空，則左子樹上所有節(jié)點的值都小于根節(jié)點的值；
若它的右子樹不為空，則右子樹上所有節(jié)點的值都大于根節(jié)點的值；
它的左右子樹也分別為搜索二叉樹；

所以構(gòu)建一個搜索二叉樹，只需要在插入結(jié)點時滿足約束規(guī)則即可。

??二叉搜索樹的構(gòu)建

與二叉樹相同，二叉搜索樹由一個個結(jié)點鏈接而成。每個結(jié)點包含三個成員——

_left（左孩子）；
_right（有孩子）；
_key（鍵值）；

所以首先定義一個BSTNode（Binary Search Tree簡寫）結(jié)構(gòu)體——

template <class K>
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;
	K _key;

	BSTreeNode(const K& key) // 構(gòu)造函數(shù)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
	{}
};

同樣的，再定義一個搜索二叉樹的類，即class BSTree——

template <class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	// 成員函數(shù)的實現(xiàn)
	// 插入、刪除、查找...
private:
	Node* _root = nullptr;
};

接著就是各種成員函數(shù)的實現(xiàn)了~

??查找操作

搜索二叉樹的查找比較簡單而且更容易幫助我們理解搜索二叉樹的性質(zhì)，所以先從查找入手。

〖數(shù)據(jù)結(jié)構(gòu)〗一棵有點自律的樹——搜索二叉樹

以上圖為例，倘若我們要查找 7，具體的思路是這樣的——

7 < 8，因此去 8 的左子樹去查找；
7 > 3，因此去 3 的右子樹去查找；
7 > 6，因此去 6 的右子樹去查找；
7 = 7，找到了，返回true；

于是我們試著著手實現(xiàn)一個Find函數(shù)。

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; // 找到返回true
	}
	return false; // 未找到返回false
}

??插入操作

理解了如何查找，插入也就非常簡單。
〖數(shù)據(jù)結(jié)構(gòu)〗一棵有點自律的樹——搜索二叉樹
還是以此圖為例，倘若我們要插入 9 ，具體步驟為——

首先確定cur的位置，并隨時更新parent；
最終，cur走到10的左節(jié)點的位置，即cur = nullptr，循環(huán)結(jié)束；
此時patent = Node*(10)；
最后一步，new一個結(jié)點Node*(key)并賦值給parent->_left即可。

bool Insert(const K& key)
{
	// 如果是第一次插入，直接new一個新結(jié)點給_root
	if (_root == nullptr)
	{
		_root = new Node(key);
		return true;
	}
	
	Node* cur = _root; // cur用來定位插入的位置
	Node* parent = cur; // 記錄parent的父親
	
	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);
	// 插入時依舊要進(jìn)行判斷
	if (parent->_key < key)
		parent->_right = cur;
	else
		parent->_left = cur;
	return true;
}

??刪除操作

二叉搜索樹的刪除是最精華的部分。對與葉子節(jié)點，例如4、7、13，刪除非常簡單，只需將自身的位置替換為nullptr即可。

〖數(shù)據(jù)結(jié)構(gòu)〗一棵有點自律的樹——搜索二叉樹
如果要刪除14或者10，也是比較簡單的，因為10的左右子樹只有一方為nullptr（10的左子樹為空），所以只需要載刪除的時候讓父結(jié)點接管自己不為空的子樹即可。

倘若要刪除6或者3，由于它們的左右子樹都不為空，刪除時無法將兩個子樹都交給父結(jié)點，情況就較為復(fù)雜。

所以此種情況，我們只能想辦法請一個人來接替自己的位置，但是并不是誰來都能勝任這個位置的。這個接替者必須滿足二叉搜索樹的條件——左子樹都比它小，右子樹都比它大。那么這個接替者的人選只能有這兩個——

左子樹的最大（最右）節(jié)點；
或右子樹的最?。ㄗ钭螅┕?jié)點；

例如，倘若要刪除3，此時有兩種做法都可行——

用1替換3；
用7替換3；

綜上所述，刪除操作共分為一下幾種情況——

左子樹為空；
右子樹為空；
左右子樹都不為空；
（左右子樹都為空其實可以歸并到1或2的情況中）；

bool Erase(const K& key)
{
	Node* cur = _root;
	Node* parent = cur;
	while (cur)
	{
		// 找到值為key的結(jié)點
		if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else // 找到了
		{	
			// 刪除
			if (cur->_left == nullptr) // 1.左子樹為空
			{
				if (cur == _root) // 根節(jié)點的刪除
				{
					_root = cur->_right;
					return true;
				}
				else
				{
					if (parent->_left == cur)
						parent->_left = cur->_right;
					else
						parent->_right = cur->_right;
					delete cur;
				}
			}
			else if (cur->_right == nullptr) // 2.右子樹為空
			{
				if (cur == _root) // 根節(jié)點的刪除
				{
					_root = cur->_left;
					return true;
				}
				else
				{
					if (parent->_left == cur)
						parent->_left = cur->_left;
					else
						parent->_right = cur->_left;
					delete cur;
				}
			}
			else // 左右子樹都不為空
			{
				// 找左子樹的最大結(jié)點 或者 右子樹的最小結(jié)點
				Node* minRight = cur->_right;
				Node* pminRight = cur;

				while (minRight->_left)
				{
					pminRight = minRight;
					minRight = minRight->_left;
				}

				cur->_key = minRight->_key; // 替換
				
				if (pminRight->_left == minRight)
				{
					pminRight->_left = minRight->_right;
				}
				else
				{
					pminRight->_right = minRight->_right;
				}

				delete minRight;
			}
			return true;
		}
	}
	return false;
}

??遍歷操作

最后，二叉搜索樹的遍歷非常簡單，就是之前學(xué)習(xí)過的二叉樹的中序遍歷。

void InOrder()
{
	_InOrder(_root);
	cout << endl;
}

void _InOrder(Node* root)
{
	if (root == nullptr)
		return;
	_InOrder(root->_left);
	cout << root->_key << ' ';
	_InOrder(root->_right);
}

注：由于調(diào)用函數(shù)時C++封裝的特性，需設(shè)計兩個函數(shù)，InOrder接口對外提供，-—_InOrder不對外提供。

??測試

〖數(shù)據(jù)結(jié)構(gòu)〗一棵有點自律的樹——搜索二叉樹

我們可以構(gòu)建一棵這樣的搜索二叉樹，再對每一個結(jié)點進(jìn)行刪除操作，驗證代碼是否正確~

void BTreeTest()
{
	BSTree<int> tree;
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	for (auto e : a)
	{
		tree.InsertR(e);
	}

	for (auto e : a)
	{
		tree.EraseR(e);
		tree.InOrder();
	}
}

〖數(shù)據(jù)結(jié)構(gòu)〗一棵有點自律的樹——搜索二叉樹

???拓展——遞歸實現(xiàn)

對于搜索二叉樹來說，上面實現(xiàn)的非遞歸版本是比遞歸版本更優(yōu)的。此處的遞歸實現(xiàn)完全屬于多余了，但是作為拓展內(nèi)容看一看也未嘗不可。

??遞歸查找

bool FindR(const K& key)
{
	return _FindR(_root, key);
}

bool _FindR(Node* root, const K& key)
{
	if (root == nullptr)
		return false;
	if (root->_key == key)
		return true;
	if (root->_key > key)
		_FindR(root->_left, key);
	else
		_FindR(root->_right, key);
}

??遞歸插入

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

bool _InsertR(Node*& root, const K& key)
{
	if (root == nullptr)
	{
		root = new Node(key);
		return true;
	}
	if (root->_key < key)
		return _InsertR(root->_right, key);
	else if (root->_key > key)
		return _InsertR(root->_left, key);
	else
		return false;
}

??遞歸刪除

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

bool _EraseR(Node*& root,const K& key)
{
	if (root == nullptr)
		return false;
	if (root->_key < key)
		return _EraseR(root->_right, key);
	else if (root->_key > key)
		return _EraseR(root->_left, key);
	else
	{
		Node* del = root;
		if (root->_left == nullptr)
			root = root->_right;
		else if (root->_right == nullptr)
			root = root->_left;
		else
		{
			Node* maxLeft = root->_left;
			while (maxLeft->_right)
				maxLeft = maxLeft->_right;
			std::swap(root->_key, maxLeft->_key);
			return _EraseR(root->_left, key);
		}
		delete del;
		return true;
	}
}

??完整源碼

??非遞歸版

#include<iostream>
using namespace std;

template <class K>
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;
	K _key;

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

template <class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	BSTree() = default;
	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

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

		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->_right = cur;
		else
			parent->_left = 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* cur = _root;
		Node* parent = cur;
		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;
						return true;
					}
					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;
						return true;
					}
					else
					{
						if (parent->_left == cur)
							parent->_left = cur->_left;
						else
							parent->_right = cur->_left;
						delete cur;
					}
				}
				else
				{
					// 找左子樹的最大結(jié)點 或者 右子樹的最小結(jié)點
					Node* minRight = cur->_right;
					Node* pminRight = cur;

					while (minRight->_left)
					{
						pminRight = minRight;
						minRight = minRight->_left;
					}

					cur->_key = minRight->_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;
	}
protected:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_key << ' ';
		_InOrder(root->_right);
	}
private:
	Node* _root = nullptr;
};

??遞歸版本

#pragma once
#include<iostream>
using namespace std;

template <class K>
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;
	K _key;

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

template <class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	BSTree() = default;
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	bool FindR(const K& key)
	{
		return _FindR(_root, key);
	}

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

	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}
protected:
	bool _FindR(Node* root, const K& key)
	{
		if (root == nullptr)
			return false;
		if (root->_key == key)
			return true;
		if (root->_key > key)
			_FindR(root->_left, key);
		else
			_FindR(root->_right, key);
	}
	bool _EraseR(Node*& root,const K& key)
	{
		if (root == nullptr)
			return false;
		if (root->_key < key)
			return _EraseR(root->_right, key);
		else if (root->_key > key)
			return _EraseR(root->_left, key);
		else
		{
			Node* del = root;
			if (root->_left == nullptr)
				root = root->_right;
			else if (root->_right == nullptr)
				root = root->_left;
			else
			{
				Node* maxLeft = root->_left;
				while (maxLeft->_right)
					maxLeft = maxLeft->_right;
				std::swap(root->_key, maxLeft->_key);
				return _EraseR(root->_left, key);
			}
			delete del;
			return true;
		}
	}

	bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		if (root->_key < key)
			return _InsertR(root->_right, key);
		else if (root->_key > key)
			return _InsertR(root->_left, key);
		else
			return false;
	}
	
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_key << ' ';
		_InOrder(root->_right);
	}
private:
	Node* _root = nullptr;
};

〖數(shù)據(jù)結(jié)構(gòu)〗一棵有點自律的樹——搜索二叉樹

?抽獎活動?

抽獎文章鏈接——Spring Cloud——演進(jìn)與應(yīng)用的分布式系統(tǒng)開發(fā)利器（文末贈書3冊）

?感謝贊助?

618，清華社 IT BOOK 多得圖書活動開始啦！活動時間為2023年6月7日至6月18日，清華社為您精選多款高分好書，涵蓋了C++、Java、Python、前端、后端、數(shù)據(jù)庫、算法與機(jī)器學(xué)習(xí)等多個IT開發(fā)領(lǐng)域，適合不同層次的讀者。全場5折，掃碼領(lǐng)券更有優(yōu)惠哦！

優(yōu)惠購書請戳這里

〖數(shù)據(jù)結(jié)構(gòu)〗一棵有點自律的樹——搜索二叉樹文章來源地址http://www.zghlxwxcb.cn/news/detail-479944.html

到了這里，關(guān)于〖數(shù)據(jù)結(jié)構(gòu)〗一棵有點自律的樹——搜索二叉樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實不符，請點擊違法舉報進(jìn)行投訴反饋，一經(jīng)查實，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費用

【gdb調(diào)試】在ubuntu環(huán)境使用gdb調(diào)試一棵四層二叉樹的數(shù)據(jù)結(jié)構(gòu)詳解
目錄 ??1. 整體思路 ??2. 準(zhǔn)備內(nèi)容 ??2.1?配置.c文件 ??2.2 準(zhǔn)備測試程序 ??2.3 GDB調(diào)試基礎(chǔ) ??3. GDB調(diào)試四層二叉樹 ??3.1?測試程序分析 ??3.2 gdb分析 ??1. 設(shè)置斷點 ??2. 啟動程序并執(zhí)行到斷點處 ??3. 打印變量的值 ??4. 單步執(zhí)行 s 進(jìn)入buildTree函數(shù)內(nèi)部 a. 第一層：根節(jié)點賦
2024年04月17日
瀏覽(20)
二叉樹（下）+Leetcode每日一題——“數(shù)據(jù)結(jié)構(gòu)與算法”“對稱二叉樹”“另一棵樹的子樹”“二叉樹的前中后序遍歷”
各位CSDN的uu們你們好呀，今天小雅蘭的內(nèi)容仍然是二叉樹和Leetcode每日一題，下面，就讓我們進(jìn)入二叉樹的世界吧！??！這個題目需要重新定義一個函數(shù)，函數(shù)參數(shù)需要有左子樹和右子樹，題目所給定的函數(shù)無法解決問題。每個不為空的結(jié)點，都可以認(rèn)為是一棵子樹的根?
2024年02月16日
瀏覽(29)
二叉樹（中）+Leetcode每日一題——“數(shù)據(jù)結(jié)構(gòu)與算法”“劍指Offer55-I. 二叉樹的深度”“100.相同的樹”“965.單值二叉樹”
各位CSDN的uu們你們好呀，今天繼續(xù)數(shù)據(jù)結(jié)構(gòu)與算法專欄中的二叉樹，下面，讓我們進(jìn)入二叉樹的世界吧?。?！二叉樹（上）——“數(shù)據(jù)結(jié)構(gòu)與算法”_認(rèn)真學(xué)習(xí)的小雅蘭.的博客-CSDN博客二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實現(xiàn) 二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實現(xiàn) 求二叉樹的高度但是這種寫法有很大的問題
2024年02月17日
瀏覽(32)
數(shù)據(jù)結(jié)構(gòu) | 搜索和排序——搜索
目錄一、順序搜索二、分析順序搜索算法三、二分搜索四、分析二分搜索算法五、散列 5.1 散列函數(shù) 5.2 處理沖突 5.3 實現(xiàn)映射抽象數(shù)據(jù)類型搜索是指從元素集合中找到某個特定元素的算法過程。搜索過程通常返回True或False，分別表示元素是否存在。有時，可以修改搜索過
2024年02月14日
瀏覽(23)
【數(shù)據(jù)結(jié)構(gòu)】6.搜索樹
二叉搜索樹： ?一棵非空的二叉搜索樹每個元素都有一個，并且任意兩個元素的不同，所有都是唯一的根節(jié)點的左子樹小于根節(jié)點的根節(jié)點的右子樹大于根節(jié)點的左右子樹也是二叉搜索樹索引二叉搜索樹：源于普通的二叉搜索樹，在每個
2024年02月08日
瀏覽(18)
數(shù)據(jù)結(jié)構(gòu)-圖搜索算法詳解
圖搜索算法是數(shù)據(jù)結(jié)構(gòu)和算法學(xué)科中的一個重要領(lǐng)域，它們用于在圖中搜索頂點（節(jié)點）和邊（連接節(jié)點的線）。圖可以是有向的（邊有方向）或無向的（邊沒有方向）。圖搜索算法主要用于解決如路徑查找、網(wǎng)絡(luò)流分析等問題。下面詳細(xì)介紹幾種常見的圖搜索算法。深度優(yōu)
2024年04月28日
瀏覽(94)
數(shù)據(jù)結(jié)構(gòu)——二叉搜索樹
本章代碼:二叉搜索樹二叉搜索樹又叫二叉排序樹，它具有以下性質(zhì)：若左子樹不為空，則左子樹上所有結(jié)點的值都小于根結(jié)點的值若右子樹不為空，則右子樹上所有結(jié)點的值都大于根結(jié)點的值它的左右子樹也分別為二叉搜索樹這個結(jié)構(gòu)的時間復(fù)雜度為一般人會以為是 O(
2024年02月12日
瀏覽(17)
數(shù)據(jù)結(jié)構(gòu)---二叉搜索樹
二叉搜索樹(Binary Search Tree 簡稱BST)又稱二叉排序樹，是一種二叉樹的特殊形式，它在每個節(jié)點上存儲的鍵值滿足以下性質(zhì)：若它的左子樹不為空，則左子樹上的所有節(jié)點的值都小于根節(jié)點的值若它的右子樹不為空，則右子樹上所有節(jié)點的值都大于根節(jié)點的值它的左右子樹也
2024年02月07日
瀏覽(20)
【數(shù)據(jù)結(jié)構(gòu)】二叉搜索樹
二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質(zhì)的二叉樹：若它的左子樹不為空，則左子樹上所有節(jié)點的值都小于根節(jié)點的值若它的右子樹不為空，則右子樹上所有節(jié)點的值都大于根節(jié)點的值它的左右子樹也分別為二叉搜索樹兩種情況：樹為空，則
2024年01月19日
瀏覽(21)
[數(shù)據(jù)結(jié)構(gòu)]-二叉搜索樹
前言作者：小蝸牛向前沖名言：我可以接受失敗，但我不能接受放棄 ? 如果覺的博主的文章還不錯的話，還請點贊，收藏，關(guān)注??支持博主。如果發(fā)現(xiàn)有問題的地方歡迎?大家在評論區(qū)指正。目錄一、二叉搜索樹的基本知識 1、什么是二叉搜索樹 2、二叉搜索樹的性能
2024年02月08日
瀏覽(17)