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

  1. Toy模板網(wǎng)首頁(yè)
  2. >Toy博客

【C++練級(jí)之路】【Lv.14】二叉搜索樹(shù)（進(jìn)化的二叉樹(shù)——BST）

2年前作者：快樂(lè)的流暢分類：Toy博客閱讀(27)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了【C++練級(jí)之路】【Lv.14】二叉搜索樹(shù)（進(jìn)化的二叉樹(shù)——BST）。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。


【C++練級(jí)之路】【Lv.14】二叉搜索樹(shù)（進(jìn)化的二叉樹(shù)——BST）,進(jìn)擊的C++,數(shù)據(jù)結(jié)構(gòu)世界,c++,數(shù)據(jù)結(jié)構(gòu),深度優(yōu)先

快樂(lè)的流暢：個(gè)人主頁(yè)
個(gè)人專欄：《C語(yǔ)言》《數(shù)據(jù)結(jié)構(gòu)世界》《進(jìn)擊的C++》
遠(yuǎn)方有一堆篝火，在為久候之人燃燒！

引言

二叉樹(shù)在之前的數(shù)據(jù)結(jié)構(gòu)章節(jié)講解過(guò)，當(dāng)時(shí)使用C來(lái)實(shí)現(xiàn)。而如今學(xué)習(xí)的二叉搜索樹(shù)，便是二叉樹(shù)的進(jìn)階，也更適合使用C++來(lái)實(shí)現(xiàn)。

一、二叉搜索樹(shù)介紹

二叉搜索樹(shù)（BST，Binary Search Tree），又稱為二叉排序樹(shù)。

它滿足以下性質(zhì)：

  • 非空左子樹(shù)的所有鍵值小于其根結(jié)點(diǎn)的鍵值
  • 非空右子樹(shù)的所有鍵值大于其根結(jié)點(diǎn)的鍵值
  • 左右子樹(shù)均為二叉搜索樹(shù)

【C++練級(jí)之路】【Lv.14】二叉搜索樹(shù)（進(jìn)化的二叉樹(shù)——BST）,進(jìn)擊的C++,數(shù)據(jù)結(jié)構(gòu)世界,c++,數(shù)據(jù)結(jié)構(gòu),深度優(yōu)先

二、二叉搜索樹(shù)的模擬實(shí)現(xiàn)

2.1 結(jié)點(diǎn)

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

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

細(xì)節(jié)：在二叉搜索樹(shù)中，一般更喜歡用K作為模板參數(shù)，用key作為數(shù)據(jù)，稱為鍵值。

2.2 成員變量

template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
protected:
	Node* _root = nullptr;
};

2.3 默認(rèn)成員函數(shù)

2.3.1 constructor

//寫(xiě)法一
BSTree()
	: _root(nullptr)
{}
//寫(xiě)法二
BSTree() = default;//強(qiáng)制生產(chǎn)默認(rèn)構(gòu)造

2.3.2 copy constructor

BSTree(const BSTree<K>& t)
{
	_root = Copy(t._root);
}

Node* Copy(Node* root)
{
	if (root == nullptr)
	{
		return nullptr;
	}

	Node* newRoot = new Node(root->_key);
	newRoot->_left = Copy(root->_left);
	newRoot->_right = Copy(root->_right);
	return newRoot;
}

細(xì)節(jié)：寫(xiě)一個(gè)子函數(shù)Copy，進(jìn)行前序遍歷遞歸拷貝

2.3.3 operator=

BSTree<K>& operator=(BSTree<K> t)
{
	swap(_root, t._root);
	return *this;
}

細(xì)節(jié)：現(xiàn)代寫(xiě)法，直接拷貝完交換

2.3.4 destructor

~BSTree()
{
	Destroy(_root);
}

void Destroy(Node*& root)
{
	if (root == nullptr)
	{
		return;
	}

	Destroy(root->_left);
	Destroy(root->_right);
	delete root;
	root = nullptr;
}

細(xì)節(jié)：

  1. 寫(xiě)一個(gè)子函數(shù)Destroy，進(jìn)行后序遍歷遞歸釋放
  2. 參數(shù)為Node*&，這樣就可以在函數(shù)內(nèi)置空根節(jié)點(diǎn)

2.4 中序遍歷

為什么只介紹中序遍歷呢？二叉搜索樹(shù)，之所以又稱為二叉排序樹(shù)，是因?yàn)樵谥行虮闅v時(shí)，便能將數(shù)據(jù)按升序遍歷。

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

void _InOrder(Node* root)
{
	if (root == nullptr)
	{
		return;
	}

	_InOrder(root->_left);
	cout << root->_key << " ";
	_InOrder(root->_right);
}

細(xì)節(jié)：同樣，一般要遞歸寫(xiě)一個(gè)子函數(shù)，再進(jìn)行傳參控制

2.5 查找

二叉搜索樹(shù)，其最大優(yōu)勢(shì)肯定是在于搜索！

2.5.1 迭代實(shí)現(xià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;
		}
	}
	return false;
}

細(xì)節(jié)：

  1. 查找的key比當(dāng)前結(jié)點(diǎn)的_key大，則往右查找
  2. 查找的key比當(dāng)前結(jié)點(diǎn)的_key小，則往左查找
  3. 找到返回true，走到空找不到返回false

2.5.2 遞歸實(shí)現(xiàn)

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 _FindR(root->_right, key);
	}
	else if (root->_key > key)
	{
		return _FindR(root->_left, key);
	}
	else
	{
		return true;
	}
}

2.6 插入

2.6.1 迭代實(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;
		}
	}

	cur = new Node(key);
	if (parent->_key < key)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	return true;
}

細(xì)節(jié)：

  1. 若根為空，直接創(chuàng)建結(jié)點(diǎn)，返回true
  2. 設(shè)置parent變量，記錄父節(jié)點(diǎn)，以便在cur走到空時(shí)進(jìn)行插入
  3. 插入前，要判斷用左指針還是右指針鏈接

2.6.2 遞歸實(shí)現(xiàn)

bool InsertR(const K& key)
{
	return _InsertR(_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;
	}
}

細(xì)節(jié)：參數(shù)為Node*&，使得當(dāng)前root為空，卻可以直接創(chuàng)建節(jié)點(diǎn)鏈接（因?yàn)榇藭r(shí)root是其父節(jié)點(diǎn)左右指針的引用）

2.7 刪除

2.7.1 迭代實(shí)現(xiàn)

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->_right == nullptr)//右子樹(shù)為空
			{
				if (cur == _root)
				{
					_root = _root->_left;
				}
				else
				{
					if (parent->_right == cur)
					{
						parent->_right = cur->_left;
					}
					else
					{
						parent->_left = cur->_left;
					}
				}
				delete cur;
			}
			else if (cur->_left == nullptr)//左子樹(shù)為空
			{
				if (cur == _root)
				{
					_root = _root->_right;
				}
				else
				{
					if (parent->_left == cur)
					{
						parent->_left = cur->_right;
					}
					else
					{
						parent->_right = cur->_right;
					}
				}
				delete cur;
			}
			else//左右子樹(shù)均不為空
			{
				//這里選擇找右子樹(shù)的最左節(jié)點(diǎn)
				Node* pminRight = cur;
				Node* minRight = cur->_right;
				while (minRight->_left)
				{
					pminRight = minRight;
					minRight = minRight->_left;
				}

				cur->_key = minRight->_key;

				if (pminRight->_right == minRight)
				{
					pminRight->_right = minRight->_right;
				}
				else
				{
					pminRight->_left = minRight->_right;
				}

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

細(xì)節(jié)：

  1. 首先依然要parent記錄父節(jié)點(diǎn)，進(jìn)行查找
  2. 找到了，分三種刪除情況：
    • 右子樹(shù)為空
    • 左子樹(shù)為空
    • 左右子樹(shù)均不為空
  3. 左右子樹(shù)一邊為空時(shí)，先判斷parent是否為空，如果為空，代表cur為_(kāi)root，需要移動(dòng)_root；如果不為空，則再判斷左右指針鏈接
  4. 左右子樹(shù)均不為空時(shí)，尋找右子樹(shù)的最左結(jié)點(diǎn)minRight（也可以是左子樹(shù)的最右結(jié)點(diǎn)）來(lái)替代cur，注意minRight可能有孩子，還要設(shè)置pminRight記錄其父節(jié)點(diǎn)位置，判斷左右指針鏈接

2.7.2 遞歸實(shí)現(xiàn)

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->_right == nullptr)//右子樹(shù)為空
		{
			root = root->_left;
		}
		else if (root->_left == nullptr)//左子樹(shù)為空
		{
			root = root->_right;
		}
		else
		{
			Node* minRight = root->_right;
			while (minRight->_left)
			{
				minRight = minRight->_left;
			}

			swap(root->_key, minRight->_key);
			return _EraseR(root->_right, key);
		}
		delete del;
		return true;
	}
}

細(xì)節(jié)：

  1. 參數(shù)為Node*&，使得左右子樹(shù)一邊為空時(shí)，不用判斷，直接鏈接（將兩種情況一并處理了）
  2. 左右子樹(shù)均不為空時(shí)，交換待刪除root和minRight的鍵值key，再遞歸其右子樹(shù)刪除

三、二叉搜索樹(shù)的應(yīng)用

K模型：K模型即只有key作為關(guān)鍵碼，結(jié)構(gòu)中只需要存儲(chǔ)Key即可，關(guān)鍵碼即為需要搜索到的值。

  • 比如：給一個(gè)單詞word，判斷該單詞是否拼寫(xiě)正確，具體方式如下：
    以詞庫(kù)中所有單詞集合中的每個(gè)單詞作為key，構(gòu)建一棵二叉搜索樹(shù)
    在二叉搜索樹(shù)中檢索該單詞是否存在，存在則拼寫(xiě)正確，不存在則拼寫(xiě)錯(cuò)誤。

KV模型：每一個(gè)關(guān)鍵碼key，都有與之對(duì)應(yīng)的值Value，即<Key, Value>的鍵值對(duì)。該種方式在現(xiàn)實(shí)生活中非常常見(jiàn)：

  • 比如英漢詞典就是英文與中文的對(duì)應(yīng)關(guān)系，通過(guò)英文可以快速找到與其對(duì)應(yīng)的中文，英文單詞與其對(duì)應(yīng)的中文<word, chinese>就構(gòu)成一種鍵值對(duì)；

  • 再比如統(tǒng)計(jì)單詞次數(shù)，統(tǒng)計(jì)成功后，給定單詞就可快速找到其出現(xiàn)的次數(shù)，單詞與其出現(xiàn)次數(shù)就是<word, count>就構(gòu)成一種鍵值對(duì)。

四、二叉樹(shù)進(jìn)階面試題

二叉樹(shù)進(jìn)階面試題

一、根據(jù)二叉樹(shù)創(chuàng)建字符串
二、二叉樹(shù)的層序遍歷
三、二叉樹(shù)的最近公共祖先
四、二叉搜索樹(shù)轉(zhuǎn)換雙向鏈表
五、構(gòu)造二叉樹(shù)
5.1 前序與中序
5.2 中序與后序
六、二叉樹(shù)的前中后序遍歷（非遞歸）
6.1 前序
6.2 中序
6.3 后序


【C++練級(jí)之路】【Lv.14】二叉搜索樹(shù)（進(jìn)化的二叉樹(shù)——BST）,進(jìn)擊的C++,數(shù)據(jù)結(jié)構(gòu)世界,c++,數(shù)據(jù)結(jié)構(gòu),深度優(yōu)先文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-842536.html

真誠(chéng)點(diǎn)贊，手有余香

到了這里，關(guān)于【C++練級(jí)之路】【Lv.14】二叉搜索樹(shù)（進(jìn)化的二叉樹(shù)——BST）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

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

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

相關(guān)文章

覺(jué)得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請(qǐng)作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包