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

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

C++------利用C++實現(xiàn)二叉搜索樹【數(shù)據(jù)結(jié)構(gòu)】

2年前作者：ljp_nan分類：Toy博客閱讀(20)違法舉報

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

二叉搜索樹

概念

什么是二叉搜索樹，二叉搜索樹就是指左孩子永遠(yuǎn)比根小右孩子永遠(yuǎn)比根大。這個規(guī)則適用于所有的子樹。
C++------利用C++實現(xiàn)二叉搜索樹【數(shù)據(jù)結(jié)構(gòu)】,C++,數(shù)據(jù)結(jié)構(gòu),c++,數(shù)據(jù)結(jié)構(gòu)
上面的就是一棵二叉搜索樹，我們還可以發(fā)現(xiàn)這棵樹走一個中序遍歷序列是有序的，所以它又被稱為二叉排序樹。

二叉搜索樹的操作

二叉搜索樹的操作主要分為以下幾點，查找， 插入，刪除。

查找

算法思想：二叉搜索樹的查找算法是這樣的，從根的地方開始找，如果要找的key比根大就到右子樹去找，如果比根小就到左子樹找。時間復(fù)雜度最差為O(N)最優(yōu)為O(logn)，如果一棵樹走完了還沒有找到說明這個數(shù)字不在這棵樹內(nèi)。
O(N)時間復(fù)雜度是下面這棵樹的查找產(chǎn)生的。
C++------利用C++實現(xiàn)二叉搜索樹【數(shù)據(jù)結(jié)構(gòu)】,C++,數(shù)據(jù)結(jié)構(gòu),c++,數(shù)據(jù)結(jié)構(gòu)
我們要使樹的高度保持為logN就必須引入平衡二叉搜索樹的概念，這個部分我們在后面的AVL和紅黑樹部分講解。
非遞歸算法：

	bool Find(const K& key)
		{
			Node* cur = _root;
			while (cur != nullptr)
			{
				if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else
				{
					return true;
				}
			}
			return false;
		}

遞歸算法：
key小于就遞歸找左樹，大于就遞歸找右樹

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

插入

插入分為兩種情況：
1、如果樹為空，則直接新增節(jié)點，賦值給_root指針。
2、樹不為空，按二叉搜索樹性質(zhì)查找插入位置，插入新節(jié)點。
C++------利用C++實現(xiàn)二叉搜索樹【數(shù)據(jù)結(jié)構(gòu)】,C++,數(shù)據(jù)結(jié)構(gòu),c++,數(shù)據(jù)結(jié)構(gòu)
非遞歸算法

bool Insert(const K& key)
		{
			if (_root == nullptr)
			{
				_root = new Node(key);
				return true;
			}

			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
				{
					return false;
				}
			}
			cur = new Node(key);
			if (parent->_key < 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;
			}
			if (root->_key > key)
			{
				return _InsertR(root->_left, key);
			}
			else if (root->_key < key)
			{
				return _InsertR(root->_right, key);
			}
			else
			{
				return false;
			}
		}

刪除

首先查找元素是否在二叉搜索樹中，如果不存在，則返回，否則要刪除的節(jié)點可能分下面四種情況：
a.要刪除的節(jié)點無孩子節(jié)點
b.要刪除的節(jié)點只有左孩子節(jié)點
c.要刪除的節(jié)點只有右孩子節(jié)點
d.要刪除的節(jié)點有左右孩子節(jié)點
情況b，c可以合成一個情況，那就是只有一個孩子節(jié)點。
情況b：刪除該節(jié)點且是被刪除節(jié)點的雙親節(jié)點指向被刪除節(jié)點的左孩子節(jié)點—直接刪除
C++------利用C++實現(xiàn)二叉搜索樹【數(shù)據(jù)結(jié)構(gòu)】,C++,數(shù)據(jù)結(jié)構(gòu),c++,數(shù)據(jù)結(jié)構(gòu)

情況c：刪除該節(jié)點且是被刪除節(jié)點的雙親節(jié)點指向被刪除節(jié)點的右孩子節(jié)點—直接刪除
C++------利用C++實現(xiàn)二叉搜索樹【數(shù)據(jù)結(jié)構(gòu)】,C++,數(shù)據(jù)結(jié)構(gòu),c++,數(shù)據(jù)結(jié)構(gòu)

情況d：在它的左子樹中尋找最大節(jié)點，用它的值填補到被刪除節(jié)點中，再來處理該節(jié)點的刪除問題—替換法刪除。
C++------利用C++實現(xiàn)二叉搜索樹【數(shù)據(jù)結(jié)構(gòu)】,C++,數(shù)據(jù)結(jié)構(gòu),c++,數(shù)據(jù)結(jié)構(gòu)
非遞歸算法：

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

			while (cur)
			{
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					//左邊為空
					if (cur->_left == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_right == cur)
							{
								parent->_right = cur->_right;
							}
							else
							{
								parent->_left = cur->_right;
							}
						}
					}
					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 = _root->_left;
						while (leftmax->_right != nullptr)
						{
							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;
		}

非遞歸算法：

//Node*& 引用是關(guān)鍵，沒有引用就不會鏈接起來，不用引用也可以用二級指針。
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;
				//1、左為空
				//2、右為空
				//3、左右都不為空

				if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else
				{
					Node* leftMax = root->_left;
					while (leftMax->_left)
					{
						leftMax = leftMax->_right;
					}
					swap(root->_key, leftMax->_key);

					return _EraseR(root->_left, key);
				}
				delete del;
				return true;
			}
		}

完整代碼

namespace name
{
	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:
		//構(gòu)造函數(shù)
		BSTree()
			:_root(nullptr)
		{}
		BSTree(const BSTree<K>& t)
		{
			_root = Copy(t._root);
		}
		BSTree<K>& operator=(BSTree<K> t)
		{
			swap(_root, t._root);
			return *this;
		}
		~BSTree()
		{
			Destory(_root);
		}
		bool Insert(const K& key)
		{
			if (_root == nullptr)
			{
				_root = new Node(key);
				return true;
			}

			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
				{
					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 != nullptr)
			{
				if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else
				{
					return true;
				}
			}
			return false;
		}
		bool Erase(const K& key)
		{
			Node* cur = _root;
			Node* parent = nullptr;

			while (cur)
			{
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					//左邊為空
					if (cur->_left == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_right == cur)
							{
								parent->_right = cur->_right;
							}
							else
							{
								parent->_left = cur->_right;
							}
						}
					}
					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 = _root->_left;
						while (leftmax->_right != nullptr)
						{
							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;
		}
		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);
		}
	private:
		void Destory(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}

			Destory(root->_left);
			Destory(root->_right);
			delete root;
			root = nullptr;
		}
		Node* Copy(Node* root)
		{
			if (root == nullptr)
			{
				return nullptr;
			}
			Node* copyroot = new Node(root->_key);
			copyroot->_left = Copy(root->_left);
			copyroot->_right = Copy(root->_right);
			return copyroot;
		}
		bool _InsertR(Node*& root, const K& key)
		{
			if (root == nullptr)
			{
				root = new Node(key);
				return true;
			}
			if (root->_key > key)
			{
				return _InsertR(root->_left, key);
			}
			else if (root->_key < key)
			{
				return _InsertR(root->_right, key);
			}
			else
			{
				return false;
			}
		}
		bool _FindR(Node* root, const K& key)
		{
			if (root == nullptr)
			{
				return false;
			}
			if (root->_key < key)
			{
				_FindR(root->_right, key);
			}
			else if (root->_key > key)
			{
				_FindR(root->_left, key);
			}
			else
			{
				return true;
			}
		}
		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;
				//1、左為空
				//2、右為空
				//3、左右都不為空

				if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else
				{
					Node* leftMax = root->_left;
					while (leftMax->_left)
					{
						leftMax = leftMax->_right;
					}
					swap(root->_key, leftMax->_key);

					return _EraseR(root->_left, key);
				}
				delete del;
				return true;
			}
		}
		void _Inorder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_Inorder(root->_left);
			cout << root->_key << " ";
			_Inorder(root->_right);
		}
		Node* _root;
	};
}

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

應(yīng)用主要是分為了K模型和KV模型，后面的set為K模型，map為KV模型，具體是這樣的：

  1. K模型：K模型即只有key作為關(guān)鍵碼，結(jié)構(gòu)中只需要存儲Key即可，關(guān)鍵碼即為需要搜索到 的值。 比如：給一個單詞word，判斷該單詞是否拼寫正確，具體方式如下： 以詞庫中所有單詞集合中的每個單詞作為key，構(gòu)建一棵二叉搜索樹
    在二叉搜索樹中檢索該單詞是否存在，存在則拼寫正確，不存在則拼寫錯誤。
  2. KV模型：每一個關(guān)鍵碼key，都有與之對應(yīng)的值Value，即<Key, Value>的鍵值對。該種方式在現(xiàn)實生活中非常常見： 比如英漢詞典就是英文與中文的對應(yīng)關(guān)系，通過英文可以快速找到與其對應(yīng)的中文，英 文單詞與其對應(yīng)的中文<word,chinese>就構(gòu)成一種鍵值對； 再比如統(tǒng)計單詞次數(shù)，統(tǒng)計成功后，給定單詞就可快速找到其出現(xiàn)的次數(shù)，單詞與其出現(xiàn)次數(shù)就是<word,count>就構(gòu)成一種鍵值對。
    上面的代碼時K模型的，下面的代碼時KV模型的。
namespace name1
{
	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:
		//構(gòu)造函數(shù)
		BSTree()
			:_root(nullptr)
		{}
		BSTree(const BSTree<K,V>& t)
		{
			_root = Copy(t._root);
		}
		BSTree<K,V>& operator=(BSTree<K,V> t)
		{
			swap(_root, t._root);
			return *this;
		}
		~BSTree()
		{
			Destory(_root);
		}
		void Inorder()
		{
			_Inorder(_root);
			cout << endl;
		}
		Node* FindR(const K& key)
		{
			return _FindR(_root,key);
		}
		bool InsertR(const K& key,const V& value)
		{
			return _InsertR(_root, key,value);
		}
		bool EraseR(const K& key)
		{
			return _EraseR(_root, key);
		}
	private:
		void Destory(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}

			Destory(root->_left);
			Destory(root->_right);
			delete root;
			root = nullptr;
		}
		Node* Copy(Node* root)
		{
			if (root == nullptr)
			{
				return nullptr;
			}
			Node* copyroot = new Node(root->_key);
			copyroot->_left = Copy(root->_left);
			copyroot->_right = Copy(root->_right);
			return copyroot;
		}
		bool _InsertR(Node*& root,const K& key,const V& value)
		{
			if (root == nullptr)
			{
				root = new Node(key,value);
				return true;
			}
			if (root->_key > key)
			{
				return _InsertR(root->_left, key, value);
			}
			else if (root->_key < key)
			{
				return _InsertR(root->_right, key, value);
			}
			else
			{
				return false;
			}
		}
		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;
			}
		}
		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;
				//1、左為空
				//2、右為空
				//3、左右都不為空
				
				if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else
				{
					Node* leftMax = root->_left;
					while (leftMax->_left)
					{
						leftMax = leftMax->_right;
					}
					swap(root->_key, leftMax->_key);

					return _EraseR(root->_left, key);
				}
				delete del;
				return true;
			}
		}
		void _Inorder(Node* root)
		{
			if (root==nullptr)
			{
				return;
			}
			_Inorder(root->_left);
			cout << root->_key << ":" << root->_value << endl;
			_Inorder(root->_right);
		}
		Node* _root;
	};
}

KV模型的測試：

void Test_BSTree7()
{
	string arr[] = { "西瓜", "西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜", "蘋果", "香蕉", "蘋果", "香蕉" };
	name1::BSTree<string, int> countTree;
	for (auto& str : arr)
	{
		//沒有找到證明是第一次出現(xiàn)
		auto ret = countTree.FindR(str);
		if (ret == nullptr)
		{
			countTree.InsertR(str, 1);
		}
		else
		{
			ret->_value++;
		}
	}
	countTree.Inorder();
}
int main()
{
	//Test_BSTree();
	//Test_BSTree1();
	//Test_BSTree2();
	//Test_BSTree3();
	//Test_BSTree4();
	//Test_BSTree5();
	//Test_BSTree6();
	Test_BSTree7();
	return 0;
}

C++------利用C++實現(xiàn)二叉搜索樹【數(shù)據(jù)結(jié)構(gòu)】,C++,數(shù)據(jù)結(jié)構(gòu),c++,數(shù)據(jù)結(jié)構(gòu)
好的我們下一篇再見！文章來源地址http://www.zghlxwxcb.cn/news/detail-667417.html

到了這里，關(guān)于C++------利用C++實現(xià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īng)查實，立即刪除！

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

相關(guān)文章

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請作者喝杯咖啡吧~博客贊助

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

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包