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

<center id="l1zwy"></center>

<dfn id="l1zwy"><tt id="l1zwy"><dl id="l1zwy"></dl></tt></dfn>

【C++＆數(shù)據(jù)結(jié)構(gòu)】超詳細一文帶小白輕松全面理解 [ 二叉搜索樹 ]—— [從零實現(xiàn)＆逐過程分析＆代碼演示&簡練易懂]（23）

2年前作者：YY的秘密代碼小屋分類：Toy博客閱讀(23)違法舉報

這篇具有很好參考價值的文章主要介紹了【C++＆數(shù)據(jù)結(jié)構(gòu)】超詳細一文帶小白輕松全面理解 [ 二叉搜索樹 ]—— [從零實現(xiàn)＆逐過程分析＆代碼演示&簡練易懂]（23）。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

前言

大家好吖，歡迎來到 YY 滴數(shù)據(jù)結(jié)構(gòu)系列，熱烈歡迎！本章主要內(nèi)容面向接觸過C++的老鐵
主要內(nèi)容含：

歡迎訂閱 YY滴C++專欄！更多干貨持續(xù)更新！以下是傳送門！

YY的《C++》專欄

YY的《C++11》專欄

YY的《Linux》專欄

YY的《數(shù)據(jù)結(jié)構(gòu)》專欄

YY的《C語言基礎(chǔ)》專欄

YY的《初學(xué)者易錯點》專欄

YY的《小小知識點》專欄

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

二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質(zhì)的二叉樹:

若它的左子樹不為空，則左子樹上所有節(jié)點的值都小于根節(jié)點的值

若它的右子樹不為空，則右子樹上所有節(jié)點的值都大于根節(jié)點的值

它的左右子樹也分別為二叉搜索樹；

二.增刪查改基本操作

//結(jié)點模板
template<class K>
struct BSTreeNode
{
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;

	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};
//在二叉搜索樹模板中
typedef BSTreeNode<K> Node;

1.二叉搜索樹的查找（分析＆代碼演示）

分析

從根開始比較，查找，比根大則往右邊走查找，比根小則往左邊走查找

最多查找高度次 ，走到到空，還沒找到，這個值不存在。

代碼演示

//查找操作
	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;//最多查找高度次 ，走到到空，還沒找到，這個值不存在。
	}

2.二叉搜索樹的插入（分析＆代碼演示）

分析

樹為空，則直接新增節(jié)點，賦值給root指針

樹不空， 按二叉搜索樹性質(zhì)的查找方式（前后指針） 找到插入位置，插入新節(jié)點

代碼演示

//插入操作
	bool Insert(const K& key)
	{
	//樹為空，則直接新增節(jié)點，賦值給root指針
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		
	//樹不空， 按二叉搜索樹性質(zhì)的查找方式（前后指針） 找到插入位置，插入新節(jié)點
		Node* parent = nullptr;//后指針
		Node* cur = _root;//前指針
		while (cur)
		{
			if (cur->_key < key)//比keycur的_key大，往右走
			{
				parent = cur;
				cur = cur->_right;
			}
			else if(cur->_key > key)//比keycur的_key小，往左走
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
//cur走到空了，開始給插入的key值創(chuàng)建結(jié)點，根據(jù)其比后一個結(jié)點（parent）大還是小，決定其是插在左還是右
		cur = new Node(key); 
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		return true;
	}

3.二叉搜索樹的刪除【※核心重點】（分析＆代碼演示）

分析

首先查找元素是否在二叉搜索樹中，如果不存在，則返回

否則要刪除的結(jié)點可能分下面四種情況：

要刪除的結(jié)點無孩子結(jié)點

要刪除的結(jié)點只有左孩子結(jié)點

要刪除的結(jié)點只有右孩子結(jié)點

要刪除的結(jié)點有左、右孩子結(jié)點

對上面四種情況整理后(1與2，3分別結(jié)合)，剩下下面2種情況（直接刪除，替換法），分出3種具體情況（直接刪除占兩種）：

直接刪除情況： 只有左/右/無孩子結(jié)點（無孩子，只有一個孩子）
（雙親結(jié)點指向被刪除節(jié)點的左還是右————取決于被刪除節(jié)點是其雙親節(jié)點的左還是右節(jié)點）

情況1：被刪除節(jié)點是其雙親節(jié)點的左節(jié)點，刪除該結(jié)點且使被刪除節(jié)點的雙親結(jié)點指向被刪除節(jié)點的 左孩子 結(jié)點

情況2：被刪除節(jié)點是其雙親節(jié)點的右節(jié)點，刪除該結(jié)點且使被刪除節(jié)點的雙親結(jié)點指向被刪除結(jié)點的 右孩子 結(jié)點

還要考慮結(jié)點為根結(jié)點情況：

替換法情況：【※核心難點】 （有兩個孩子）

情況3 ：在它的右子樹中尋找中序下的第一個結(jié)點(關(guān)鍵碼最小)，用它的值填補到被刪除節(jié)點中，再來處理該結(jié)點的刪除問題

分析：要 找到左子樹的最大(右)結(jié)點，或者 右子樹的最小(左)結(jié)點（下圖演示中是找到左子樹的最大結(jié)點）

具體過程分析：

設(shè)置前后指針，留一個cur指針指向要刪除結(jié)點，parent指針跟著LeftMax指針向下逐個移動

找到leftMax以后，交換其和cur的數(shù)值，（收完尾后，最后一步再將指針也一同轉(zhuǎn)移）

要分為兩種情況（如下圖所示） (1) leftMax指針的左指針為空，(2) leftMax指針的左指針不為空
（為什么不用討論右指針呢？因為leftMax的右指針必定為空，否則leftMax會繼續(xù)向下移動）

因為采用的是前后指針法，所以這時留下的后指針（parent）就對應(yīng)指向leftMax的左/右結(jié)點

最后將cur指針指向leftMax，leftMax動不動無所謂

代碼演示

//刪除操作
	bool Erase(const K& key)
	{
		Node* parent = nullptr;//后指針
		Node* cur = _root;//前指針

		while (cur)
		{
//通過二叉搜索樹規(guī)則向下查找
			if (cur->_key < key)      
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
//直接刪除情況：只有左/右/無孩子結(jié)點
//（雙親結(jié)點指向被刪除節(jié)點的左還是右————取決于被刪除節(jié)點是其雙親節(jié)點的左還是右節(jié)點） 
			else // 找到了
			{
				 // 左為空      
				if (cur->_left == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_right == cur)//被刪除節(jié)點是其雙親節(jié)點的右節(jié)點   
						{
							parent->_right = cur->_right;//刪除該結(jié)點且使被刪除節(jié)點的雙親結(jié)點指向被刪除結(jié)點的 右孩子 結(jié)點
						}
						else//被刪除節(jié)點是其雙親節(jié)點的左節(jié)點  
						{
							parent->_left = cur->_right;//刪除該結(jié)點且使被刪除節(jié)點的雙親結(jié)點指向被刪除結(jié)點的 左孩子 結(jié)點
						}
					}
				}
				// 右為空    
				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;
						}
					}					
				} 

// 替換法情況：左右都不為空 
				else
				{
					// 找替代節(jié)點
					Node* parent = cur;
					Node* leftMax = cur->_left;
					while (leftMax->_right)
					{
						parent = leftMax;
						leftMax = leftMax->_right;
					}

					swap(cur->_key, leftMax->_key);

					if (parent->_left == leftMax)
					{
						parent->_left = leftMax->_left;
					}
					else
					{
						parent->_right = leftMax->_left;
					}

					cur = leftMax;
				}
				delete cur;
				return true;
			}
		}

		return false;
	}

4.二叉搜索樹的中序遍歷（分析＆代碼演示）

分析

中序遍歷要從通過模板實例化的樹中調(diào)用中序遍歷函數(shù)

需要傳根結(jié)點指針，但是 根結(jié)點指針是在private域中，域外不能直接傳一個根結(jié)點指針 ，所以要引入_InOrder函數(shù)，在二叉搜索樹模板中 再次封裝一層

代碼演示

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

	t.InOrder();  //需要傳根結(jié)點指針，但是根結(jié)點指針是在private域中，域外不能直接傳一個根結(jié)點指針，
	              //所以要引入_InOrder函數(shù)，在二叉搜索樹模板中再次封裝一層
}

//中序遍歷——————————————————————————————————————————為了解決中序要傳入根節(jié)點的問題，引入_InOrder函數(shù)
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

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

三.二叉搜索樹的性能問題：需要AVL樹…紅黑樹…

插入和刪除操作都必須先查找，查找效率代表了二叉搜索樹中各個操作的性能

當(dāng)二叉搜索樹 退化為單支時，其效率為O(N)，二叉搜索樹的性能就失去了

對二叉搜索樹進行改進后，得到的AVL樹紅黑樹效率為 Log(N)

四.二叉搜索樹的完整實現(xiàn)代碼演示

//結(jié)點模板
template<class K>
struct BSTreeNode
{
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;

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

//二叉搜索樹類模板
template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:

//初始化列表
	BSTree()
		:_root(nullptr)
	{}
	

//查找操作
	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 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->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		return true;
	}


//刪除操作
	bool Erase(const K& key)
	{
		Node* parent = nullptr;//后指針
		Node* cur = _root;//前指針

		while (cur)
		{
//通過二叉搜索樹規(guī)則向下查找
			if (cur->_key < key)      
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
//直接刪除情況：只有左/右/無孩子結(jié)點
//（雙親結(jié)點指向被刪除節(jié)點的左還是右————取決于被刪除節(jié)點是其雙親節(jié)點的左還是右節(jié)點） 
			else // 找到了
			{
				 // 左為空      
				if (cur->_left == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_right == cur)//被刪除節(jié)點是其雙親節(jié)點的右節(jié)點   
						{
							parent->_right = cur->_right;//刪除該結(jié)點且使被刪除節(jié)點的雙親結(jié)點指向被刪除結(jié)點的 右孩子 結(jié)點
						}
						else//被刪除節(jié)點是其雙親節(jié)點的左節(jié)點  
						{
							parent->_left = cur->_right;//刪除該結(jié)點且使被刪除節(jié)點的雙親結(jié)點指向被刪除結(jié)點的 左孩子 結(jié)點
						}
					}
				}
				// 右為空    
				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;
						}
					}					
				} 

// 替換法情況：左右都不為空 
				else
				{
					// 找替代節(jié)點
					Node* parent = cur;
					Node* leftMax = cur->_left;
					while (leftMax->_right)
					{
						parent = leftMax;
						leftMax = leftMax->_right;
					}

					swap(cur->_key, leftMax->_key);

					if (parent->_left == leftMax)
					{
						parent->_left = leftMax->_left;
					}
					else
					{
						parent->_right = leftMax->_left;
					}

					cur = leftMax;
				}

				delete cur;
				return true;
			}
		}

		return false;
	}


//中序遍歷——————————————————————————————————————————為了解決中序要傳入根節(jié)點的問題，引入_InOrder函數(shù)
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

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


private:
	Node* _root;
};


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

	t.InOrder();

	t.Erase(4);
	t.InOrder();

	t.Erase(6);
	t.InOrder();

	t.Erase(7);
	t.InOrder();

	t.Erase(3);
	t.InOrder();

	for (auto e : a)
	{
		t.Erase(e);
	}
	t.InOrder();
}

五.進階二叉樹習(xí)題傳送門

進階二叉樹習(xí)題傳送門文章來源地址http://www.zghlxwxcb.cn/news/detail-755349.html

到了這里，關(guān)于【C++＆數(shù)據(jù)結(jié)構(gòu)】超詳細一文帶小白輕松全面理解 [ 二叉搜索樹 ]—— [從零實現(xiàn)＆逐過程分析＆代碼演示&簡練易懂]（23）的文章就介紹完了。如果您還想了解更多內(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īng)查實，立即刪除！

分享到：

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

【數(shù)據(jù)結(jié)構(gòu)】——單鏈表超詳細介紹（獨家介紹，小白必看?。。。?/a>
被滑走別滑走，我這一萬字的文章，寫的真的很痛苦的，希望能得到一點點支持 ?。。?重點內(nèi)容和易錯點都用彩筆標注了，干貨滿滿，耐心看完，我真的真的有在認真更新o(╥﹏╥)o 上一篇文章介紹完順序表后，我們就要開始學(xué)習(xí)鏈表了，鏈表的種類有很多，比如說
2024年02月02日
瀏覽(53)
【數(shù)據(jù)結(jié)構(gòu)】順序表---C語言版（數(shù)據(jù)結(jié)構(gòu)開篇小菜，全網(wǎng)最詳細！小白看一遍就學(xué)會?。。。?/a>
停更了一個月限時返場啦??從本篇文章開始就進入了我們數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)嘍！本篇文章也是《數(shù)據(jù)結(jié)構(gòu)與算法》專欄的第一篇文章，本篇的內(nèi)容是順序表的學(xué)習(xí)，也是數(shù)據(jù)結(jié)構(gòu)的開胃小菜，希望烙鐵們可以理解消化哦???。?！在我們學(xué)習(xí) 順序表之前呢，我們大家肯定會有
2024年02月06日
瀏覽(22)
【數(shù)據(jù)結(jié)構(gòu)】二叉樹遍歷的實現(xiàn)（超詳細解析，小白必看系列）
目錄一、前言 ??為何使用鏈式二叉樹? ???何為鏈式二叉樹 ???二叉樹的構(gòu)建 ??創(chuàng)建二叉鏈結(jié)構(gòu) ??手動構(gòu)建一顆樹? ??二叉樹的遍歷（重點） ??前序遍歷 ???中序遍歷 ???后續(xù)遍歷 ???二叉樹的經(jīng)典問題（重點） ??二叉樹節(jié)點個數(shù) ???二叉樹葉子節(jié)點的個數(shù) ???
2024年02月02日
瀏覽(19)
小白也能學(xué)會的鏈表 | C++ | 算法與數(shù)據(jù)結(jié)構(gòu) （新手村）
本質(zhì)：找到兩個有序數(shù)據(jù)段中的第一個相同數(shù)據(jù) 解題：利用set的不重復(fù)性，首先把headA都塞到set中，再遍歷headB找有沒有已經(jīng)出現(xiàn)在set中的節(jié)點即可。注意！ set的數(shù)據(jù)是ListNode* 不是 int。如果是int可能出現(xiàn)節(jié)點不同但是var相同的情況，而ListNode* 就不會。時間復(fù)雜度：O（2n）
2024年02月14日
瀏覽(21)
【數(shù)據(jù)結(jié)構(gòu)——9大基礎(chǔ)排序】一文掌握九大經(jīng)典排序（配有詳細圖文說明！?。。?/a>
算法基本思想：（從大到小排序）在一個非遞減的有序數(shù)組中，要新增一個元素 x ，有兩個方法： 1.從數(shù)組的頭部開始向后遍歷，尋找第一個比x 大的元素 y ，從y元素開始的所有元素全部向后移動，最后將x元素插入數(shù)組。（×） 2.從數(shù)組的尾部開始向后向前遍歷，尋找第
2024年02月08日
瀏覽(22)
全面理解鏈表數(shù)據(jù)結(jié)構(gòu)：各種節(jié)點操作、做題技巧，易錯點分析與題目清單（C++代碼示例，不斷更新）
鏈表是一種線性數(shù)據(jù)結(jié)構(gòu)，它包含的元素并不是物理上連續(xù)的，而是通過指針進行連接。鏈表中的每個元素通常由一個節(jié)點表示，每個節(jié)點包含一個數(shù)據(jù)元素和一個或多個鏈接（指針）。鏈表的主要類型包括：單向鏈表（Singly Linked List）：每個節(jié)點包含一個指向下一個節(jié)點
2024年02月07日
瀏覽(25)
【數(shù)據(jù)結(jié)構(gòu)】—搜索二叉樹（C++實現(xiàn)，超詳細！）
?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??????????????? ?? 慕斯主頁：修仙—別有洞天 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?????????????????? ?? 今日夜電波：消えてしまいそうです—真夜中 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
2024年02月05日
瀏覽(24)
數(shù)據(jù)結(jié)構(gòu)-雙向鏈表(c++)超全超詳細
單鏈表結(jié)點中只有一個指向其后繼的指針，使得單鏈表只能從頭結(jié)點依次順序地向后遍歷。要訪問某個結(jié)點的前驅(qū)結(jié)點（插入，刪除操作時），只能從頭開始遍歷，訪問后繼結(jié)點的時間復(fù)雜度為O(1)，訪問前驅(qū)結(jié)點的時間復(fù)雜度為O(n)。提示：以下是本篇文章正文內(nèi)容，下面案
2023年04月08日
瀏覽(20)
C++數(shù)據(jù)封裝以及定義結(jié)構(gòu)的詳細講解鴨~
名字：阿玥的小東東 ? 博客主頁：阿玥的小東東的博客_CSDN博客-pythonc++高級知識,過年必備,C/C++知識講解領(lǐng)域博主目錄定義結(jié)構(gòu) 訪問結(jié)構(gòu)成員結(jié)構(gòu)作為函數(shù)參數(shù)
2024年02月04日
瀏覽(23)
利用C++超詳細解釋數(shù)據(jù)結(jié)構(gòu)中的鏈表
鏈表（Linked List）是一種常見的數(shù)據(jù)結(jié)構(gòu)，它可以動態(tài)地插入和刪除元素，不需要像數(shù)組那樣預(yù)先分配固定大小的內(nèi)存。鏈表中的每個元素稱為節(jié)點（Node），每個節(jié)點包含一個數(shù)據(jù)值和一個指向下一個節(jié)點的指針。本教學(xué)將涵蓋以下知識點：單向鏈表（Singly Linked List）雙向
2024年02月04日
瀏覽(27)

<ul id="9edqj"></ul>

<address id="9edqj"><blockquote id="9edqj"></blockquote></address>

<blockquote id="9edqj"><mark id="9edqj"></mark></blockquote>

<strike id="9edqj"></strike>