C++二叉搜索樹的操作有哪些

本文小編為大家詳細(xì)介紹“C++二叉搜索樹的操作有哪些”，內(nèi)容詳細(xì)，步驟清晰，細(xì)節(jié)處理妥當(dāng)，希望這篇“C++二叉搜索樹的操作有哪些”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來(lái)學(xué)習(xí)新知識(shí)吧。

二叉搜索樹概念與操作

二叉搜索樹的概念

二叉搜索樹又稱二叉排序樹，若它的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值；若它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值，它的左右子樹也分別未二叉搜索樹。也可以是一顆空樹。

int a[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };

二叉搜索樹的操作

查找

迭代：

	Node* 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 cur;
			}
		}

		return nullptr;
	}

遞歸：

	Node* _FindR(Node* root, const K& key)
	{
		if (root == nullptr)
			return nullptr;

		if (root->_key < key)
			return _FindR(root->_right, key);
		else if (root->_key > key)
			return _FindR(root->_left, key);
		else
			return root;
	}

插入

樹為空，則直接插入

樹不為空，按二叉搜索樹性質(zhì)查找插入位置，插入新節(jié)點(diǎ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 < cur->_key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		return true;
	}

遞歸：

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

刪除

首先查找元素是否在二叉搜索樹中，如果不存在，則返回，否則要?jiǎng)h除的結(jié)點(diǎn)可能分下面四種情況：

• 要?jiǎng)h除的結(jié)點(diǎn)無(wú)孩子結(jié)點(diǎn)

• 要?jiǎng)h除的結(jié)點(diǎn)只有左孩子結(jié)點(diǎn)

• 要?jiǎng)h除的結(jié)點(diǎn)只有右孩子結(jié)點(diǎn)

• 要?jiǎng)h除的結(jié)點(diǎn)只有左、右結(jié)點(diǎn)

實(shí)際情況中1和2或3可以合并，因此真正的刪除過(guò)程如下：

• 刪除該結(jié)點(diǎn)且使被刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除結(jié)點(diǎn)的左孩子結(jié)點(diǎn)

• 刪除該結(jié)點(diǎn)且使被刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除結(jié)點(diǎn)的右孩子結(jié)點(diǎn)

• 替代法。在它的右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn)（關(guān)鍵碼最?。盟闹堤钛a(bǔ)到被刪除結(jié)點(diǎn)中，再來(lái)處理該結(jié)點(diǎ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->_left == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
					}
					delete cur;
				}
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}
				}
				else
				{
					//找到右樹最小節(jié)點(diǎn)去替代刪除
					Node* minRightParent = cur;
					Node* minRight = cur->_right;
					while (minRight->_left)
					{
						minRightParent = minRight;
						minRight = minRight->_left;
					}

					cur->_key = minRight->_key;

					if (minRight == minRightParent->_left)
						minRightParent->_left = minRight->_right;
					else
						minRightParent->_right = minRight->_right;

					delete minRight;
				}

				return true;
			}
		}

		return false;
	}

遞歸：

	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* minRight = root->_right;
				while (minRight->_left)
				{
					minRight = minRight->_left;
				}

				root->_key = minRight->_key;

				//轉(zhuǎn)換成遞歸在右子樹中刪除最小節(jié)點(diǎn)
				return _EraseR(root->_right, minRight->_key);
			}

			delete del;
			return true;
		}
	}

二叉搜索樹的應(yīng)用

1.K模型：K模型即只有key作為關(guān)鍵碼，結(jié)構(gòu)中只需要存儲(chǔ)key即可，關(guān)鍵碼即為需要搜索到的值。比如：給一個(gè)單詞word，判斷該單詞是否拼寫正確。具體方法如下：1.以單詞集合中的每個(gè)單詞作為key，構(gòu)建一棵二叉搜索樹。2.在二叉搜索樹中檢索該單詞是否存在，存在則拼寫正確，不存在則拼寫錯(cuò)誤。

2.KV模型：每一個(gè)關(guān)鍵碼key，都有與之對(duì)應(yīng)的值Value，即<Key, Value>的鍵值對(duì)。該種方式在現(xiàn)實(shí)生活中非常常見：比如英漢詞典就是英語(yǔ)與中文的對(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í)現(xiàn)一個(gè)簡(jiǎn)單的英漢詞典dict，可以通過(guò)英文找到與其對(duì)應(yīng)的中文，具體實(shí)現(xiàn)方式如下：1.<單詞，中文含義>為鍵值對(duì)構(gòu)造二叉搜索樹，注意：二叉搜索樹需要比較，鍵值對(duì)比較時(shí)只比較Key。2.查詢英文單詞時(shí)，只需要給出英文單詞，就可快速找到與其對(duì)應(yīng)的Key。

namespace KEY_VALUE {
	template<class K, class V>
	struct BSTreeNode
	{
		BSTreeNode<K, V>* _left;
		BSTreeNode<K, V>* _right;
		K _key;
		V _value;

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

	template<class K, class V>
	class BSTree {
		typedef BSTreeNode<K, V> Node;
	public:
		V& operator[](const K& key)
		{
			pair<Node*, bool> ret = Insert(key, V());
			return ret.first->_value;
		}

		pair<Node*, bool> Insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				return make_pair(_root, 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 make_pair(cur, false);
				}
			}

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

			return make_pair(cur, true);
		}

		Node* 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 cur;
				}
			}

			return nullptr;
		}

		bool Erase(const K& key)
		{
			Node* cur = _root;
			Node* parent = nullptr;

			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;
						}
						else
						{
							if (cur == parent->_left)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}

						delete cur;
					}
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (cur == parent->_left)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}

						delete cur;
					}
					else
					{
						//找到右樹最小結(jié)點(diǎn)去替代刪除
						Node* minRightParent = cur;
						Node* minRight = cur->_left;
						while (minRight->_left)
						{
							minRightParent = minRight;
							minRight = minRight->_left;
						}

						cur->_key = minRight->_key;

						if (minRight = minRightParent->_left)
							minRightParent->_left = minRight->right;
						else
							minRightParent->_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 << ":" << root->_value << endl;
			_InOrder(root->_right);
		}
	private:
		Node* _root = nullptr;
	};
}

void Test2()
{
	KEY_VALUE::BSTree<string, string> dict;
	dict.Insert("sort", "排序");
	dict.Insert("insert", "插入");
	dict.Insert("tree", "樹");
	dict.Insert("right", "右邊");

	string str;
	while (cin >> str)
	{
		if (str == "q")
		{
			break;
		}
		else
		{
			auto ret = dict.Find(str);
			if (ret == nullptr)
			{
				cout << "拼寫錯(cuò)誤，請(qǐng)檢查你的單詞" << endl;
			}
			else
			{
				cout << ret->_key <<"->"<< ret->_value << endl;
			}
		}
	}
}

void Test3()
{
	//統(tǒng)計(jì)字符串出現(xiàn)次數(shù)，也是經(jīng)典key/value
	string str[] = { "sort", "sort", "tree", "insert", "sort", "tree", "sort", "test", "sort" };
	KEY_VALUE::BSTree<string, int> countTree;
	//for (auto& e : str)
	//{
	//	auto ret = countTree.Find(e);
	//	if (ret == nullptr)
	//	{
	//		countTree.Insert(e, 1);
	//	}
	//	else
	//	{
	//		ret->_value++;
	//	}
	//}

	for (auto& e : str)
	{
		countTree[e]++;
	}

	countTree.InOrder();
}

二叉樹的性能分析

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

對(duì)有n個(gè)結(jié)點(diǎn)的二叉搜索樹，若每個(gè)元素查找的概率相等，則二叉搜索樹平均查找長(zhǎng)度是結(jié)點(diǎn)在二叉搜索樹的深度的函數(shù)，即結(jié)點(diǎn)越深，比較的次數(shù)越多。

但對(duì)于同一個(gè)關(guān)鍵碼集合，如果關(guān)鍵碼插入的次序不同，可能得到不同結(jié)構(gòu)的二叉搜索樹

最優(yōu)情況下，二叉搜索樹為完全二叉樹，其平均比較次數(shù)為：logN

最差情況下，二叉搜索樹退化為單支樹，其平均比較次數(shù)為：N/2

讀到這里，這篇“C++二叉搜索樹的操作有哪些”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識(shí)點(diǎn)還需要大家自己動(dòng)手實(shí)踐使用過(guò)才能領(lǐng)會(huì)，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注億速云行業(yè)資訊頻道。