c++-第15節(jié)-二叉樹進階-創(chuàng)新互聯(lián)

1. 二叉搜索樹 1.1.二叉搜索樹概念

二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質(zhì)的二叉樹: $\bullet$ 若它的左子樹不為空，則左子樹上所有節(jié)點的值都小于根節(jié)點的值 $\bullet$ 若它的右子樹不為空，則右子樹上所有節(jié)點的值都大于根節(jié)點的值 $\bullet$ 它的左右子樹也分別為二叉搜索樹也就是說，搜索二叉樹的任意一個子樹都需要滿足，左子樹的值<根<右子樹的值
成都創(chuàng)新互聯(lián)公司主要從事網(wǎng)站制作、網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)浦口,十多年網(wǎng)站建設(shè)經(jīng)驗,價格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):13518219792
注：
1.搜索二叉樹數(shù)據(jù)的查找效率為O(N)，當搜索二叉樹接近完全時，數(shù)據(jù)的查找效率較高，接近 $log_{2}^{N}$ 。
2.當使用中序遍歷遍歷搜索二叉樹時，遍歷出來的數(shù)據(jù)是增序的。

1.2.二叉搜索樹的實現(xiàn)

二叉搜索樹普通實現(xiàn)版本

BinarySearchTree.h文件：

#pragma once

templatestruct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;

	K _key;

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

templateclass BSTree
{
	typedef BSTreeNodeNode;
private:
	void DestoryTree(Node* root)
	{
		if (root == nullptr)
			return;

		DestoryTree(root->_left);
		DestoryTree(root->_right);
		delete root;
	}

	Node* CopyTree(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		Node* copyNode = new Node(root->_key);
		copyNode->_left = CopyTree(root->_left);
		copyNode->_right = CopyTree(root->_right);

		return copyNode;
	}
public:
	// 強制編譯器自己生成構(gòu)造
	// C++11
	BSTree() = default;

	BSTree(const BSTree& t)
	{
		_root = CopyTree(t._root);
	}

	// t1 = t2
	BSTree& operator=(BSTreet)
	{
		swap(_root, t._root);
		return *this;
	}

	~BSTree()
	{
		DestoryTree(_root);
		_root = nullptr;
	}

	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;
	}

	//const Node* Find(const K& key)
	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* 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
			{
				// 一個孩子--左為空 or 右為空
				// 兩個孩子 -- 替換法
				if (cur->_left == nullptr)
				{
					//if (parent == 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 (parent == nullptr)
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}

					delete cur;
				}
				else // 兩個孩子都不為空
				{
					// 右子樹的最小節(jié)點替代
					Node* minParent = cur;
					Node* minRight = cur->_right;
					while (minRight->_left)
					{
						minParent = minRight;
						minRight = minRight->_left;
					}

					swap(minRight->_key, cur->_key);
					//cur->_key = minRight->_key;
					if (minParent->_left == minRight)
					{
						minParent->_left = minRight->_right;
					}
					else
					{
						minParent->_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<< " ";
		_InOrder(root->_right);
	}
private:
	Node* _root = nullptr;
};

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

	t.Insert(16);
	t.Insert(9);

	t.InOrder();
}

void TestBSTree2()
{
	BSTreet;
	int a[] = { 8, 7, 9, 12, 5, 19, 20, 30,7,12 };
	for (auto e : a)
	{
		t.Insert(e);
	}
	t.InOrder();
}

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

	t.Erase(3);
	t.Erase(8);

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

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

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

	BSTreecopy = t;
	copy.InOrder();
}

test.cpp文件：

#define _CRT_SECURE_NO_WARNINGS 1
#includeusing namespace std;

#include "BinarySearchTree.h"

int main()
{
	TestBSTree3();

	return 0;
}

注：

1. 二叉搜索樹的查找介紹 a.從根開始比較，查找，比根大則往右邊走查找，比根小則往左邊走查找。 b.最多查找高度次，走到到空，還沒找到，這個值不存在。 2. 二叉搜索樹的插入介紹插入的具體過程如下： a.樹為空，則直接新增節(jié)點，賦值給root指針 b.樹不空，按二叉搜索樹性質(zhì)查找插入位置，插入新節(jié)點具體思路為：定義兩個指針parent和cur，cur查找插入位置，parent記錄cur上一個位置，當cur找到插入位置時（cur為空時），開辟節(jié)點給cur并和parent進行鏈接。

注：

（1）搜索二叉樹一般不允許插入和里面數(shù)據(jù)相同的數(shù)據(jù)，會造成冗余。

（2）搜索二叉樹數(shù)據(jù)插入的順序不同，樹的形狀一般也不同，當以近似有序的數(shù)據(jù)順序依次插入，那么二叉樹的形狀近似一個鏈表，搜索的時間復雜度接近O(N)

3. 二叉搜索樹的刪除介紹??

首先查找元素是否在二叉搜索樹中，如果不存在，則返回, 否則要刪除的結(jié)點可能分下面四種情況： a. 要刪除的結(jié)點無孩子結(jié)點 b. 要刪除的結(jié)點只有左孩子結(jié)點 c. 要刪除的結(jié)點只有右孩子結(jié)點 d. 要刪除的結(jié)點有左、右孩子結(jié)點看起來有待刪除節(jié)點有4中情況，實際情況a可以與情況b或者c合并起來，因此真正的刪除過程如下：情況b：刪除該結(jié)點且使被刪除節(jié)點的雙親結(jié)點指向被刪除節(jié)點的左孩子結(jié)點--直接刪除情況c：刪除該結(jié)點且使被刪除節(jié)點的雙親結(jié)點指向被刪除結(jié)點的右孩子結(jié)點--直接刪除情況d：在刪除結(jié)點的左子樹中尋找大值結(jié)點（左子樹中序下的最后一個結(jié)點），或者刪除結(jié)點的右子樹中尋找最小值結(jié)點（右子樹中序下的第一個結(jié)點），用左子樹大值結(jié)點的值或右子樹最小值結(jié)點的值填補到被刪除節(jié)點中，再來處理左子樹大值結(jié)點或右子樹最小值結(jié)點的刪除問題--替換法刪除

情況b和情況c的實現(xiàn)代碼（情況a融合在情況b中）如果如下圖一所示，那么是有BUG的，如下圖二所示的搜索樹要刪除根節(jié)點，此時parent指針指向空指針，parent->left或者parent->right會訪問空指針，程序報錯。解決方法是讓搜索樹的_root成員變量指向根結(jié)點的那個孩子結(jié)點即可，如下圖三所示。

情況d的代碼實現(xiàn)如果如下圖一所示，那么是錯誤的，因為Swap交換之后該樹不再是一個搜索二叉樹，交換之后再遞歸調(diào)用Erase函數(shù)刪除key是找不到key值結(jié)點并返回false的，所以我們應(yīng)該手動去刪除。

我們利用minRight指針找到右子樹最小值結(jié)點，minParent指針指向minRight指針指向結(jié)點的父節(jié)點，然后將minRight指針指向結(jié)點的值（右子樹最小值）賦值給cur指針指向的結(jié)點值，minParent指針指向結(jié)點的_left指針和minRight指針指向結(jié)點的_right指針鏈接（此時一定是minParent指針指向結(jié)點的_left指針指向minRight指針指向的結(jié)點，minRight指針指向結(jié)點的_left指針一定是NULL，_right指針可能為空可能指向其他結(jié)點，所以要刪除minRight指針指向結(jié)點直接將minParent指針指向結(jié)點的_left指針指向minRight指針指向結(jié)點的_right指針指向的地址，然后釋放minRight指針指向結(jié)點即可），釋放minRight指針指向的結(jié)點，如下圖三所示。

上面圖三所示的代碼是有BUG的，因為有可能刪除結(jié)點的右子樹的根就是最小結(jié)點，如下圖一所示，要刪除值為8的結(jié)點（根節(jié)點），此時該節(jié)點右子樹的根（值為10的結(jié)點）就是最小結(jié)點。開始minRight指向值為10的結(jié)點，while循環(huán)判斷條件為假不進入循環(huán)，minRight最終指向值為10的結(jié)點，也就是右子樹的最小結(jié)點，而minParent指針為空，minParent指針應(yīng)該為值為8的結(jié)點，所以應(yīng)該用cur對minParent指針初始化。并且此時minParent指針指向結(jié)點的_right指針和minRight指針指向結(jié)點的_right指針鏈接（此時一定是minParent指針指向結(jié)點的_right指針指向minRight指針指向的結(jié)點，minRight指針指向結(jié)點的_left指針一定是NULL，_right指針可能為空可能指向其他結(jié)點，所以要刪除minRight指針指向結(jié)點直接將minParent指針指向結(jié)點的_right指針指向minRight指針指向結(jié)點的_right指針指向的地址，然后釋放minRight指針指向結(jié)點即可），釋放minRight指針指向的結(jié)點。代碼中，因為最后minRight指針指向結(jié)點既有可能是minParent指針指向結(jié)點的左節(jié)點也有可能是minParent指針指向結(jié)點的右節(jié)點，因此需要進行判斷，如下圖二所示。

4.搜索二叉樹上面這種結(jié)構(gòu)允許增刪查功能，不允許改，修改一個節(jié)點的數(shù)值那么這個樹很可能不再是搜索二叉樹。

5.搜索二叉樹的拷貝構(gòu)造函數(shù)和賦值運算符重載函數(shù)需要進行深拷貝，這里深拷貝不能復用insert插入函數(shù)，因為插入的順序不同搜索二叉樹也不同。我們寫一個CopyTree函數(shù)來遞歸創(chuàng)建一個相同的樹，如下圖一所示，然后搜索二叉樹的拷貝構(gòu)造函數(shù)復用CopyTree函數(shù)即可，如下圖二所示

如果寫了構(gòu)造函數(shù)，那么系統(tǒng)自動生成的默認構(gòu)造函數(shù)就不會再自動生成了，拷貝構(gòu)造函數(shù)也是構(gòu)造函數(shù)，如果我們寫了拷貝構(gòu)造函數(shù)，系統(tǒng)自動生成的默認構(gòu)造函數(shù)不再生成，我們需要自己去顯式的寫構(gòu)造函數(shù)。在c++11中，可以使用default關(guān)鍵字強制編譯器自己生成默認構(gòu)造函數(shù)，如下圖所示

搜索二叉樹的賦值運算符重載函數(shù)可以復用拷貝構(gòu)造函數(shù)來進行現(xiàn)代寫法的代碼實現(xiàn)，如下圖所示

搜索二叉樹的析構(gòu)函數(shù)，我們寫一個DestoryTree函數(shù)來銷毀釋放樹，如下圖一所示，然后二叉樹的析構(gòu)函數(shù)復用DestoryTree函數(shù)即可，如下圖二所示

二叉搜索樹遞歸實現(xiàn)版本

BinarySearchTree.h文件：

#pragma once

template//struct BinarySearchTreeNode
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;

	K _key;

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

templateclass BSTree
{
	typedef BSTreeNodeNode;
private:
	void DestoryTree(Node* root)
	{
		if (root == nullptr)
			return;

		DestoryTree(root->_left);
		DestoryTree(root->_right);
		delete root;
	}

	Node* CopyTree(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		Node* copyNode = new Node(root->_key);
		copyNode->_left = CopyTree(root->_left);
		copyNode->_right = CopyTree(root->_right);

		return copyNode;
	}
public:
	// 強制編譯器自己生成構(gòu)造
	// C++11
	BSTree() = default;

	BSTree(const BSTree& t)
	{
		_root = CopyTree(t._root);
	}

	// t1 = t2
	BSTree& operator=(BSTreet)
	{
		swap(_root, t._root);
		return *this;
	}

	~BSTree()
	{
		DestoryTree(_root);
		_root = nullptr;
	}

	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:
	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;
				}

				swap(root->_key, minRight->_key);

				return _EraseR(root->_right, 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;
	}

	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;
		}
	}

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

		_InOrder(root->_left);
		cout<< root->_key<< " ";
		_InOrder(root->_right);
	}
private:
	Node* _root = nullptr;
};

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

	t.InsertR(9);

	BSTreecopy = t;
	copy.InOrder();
}

void TestBSTree2()
{
	BSTreet;
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	for (auto e : a)
	{
		t.InsertR(e);
	}
	t.InOrder();
	t.EraseR(3);
	t.EraseR(8);

	t.InOrder();
	t.EraseR(14);
	t.EraseR(7);
	t.InOrder();

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

test.cpp文件：

#define _CRT_SECURE_NO_WARNINGS 1
#includeusing namespace std;

#include "BinarySearchTree.h"

int main()
{
	TestBSTree2();

	return 0;
}

注：

1.搜索二叉樹插入函數(shù)的遞歸實現(xiàn)，用要插入的值和根結(jié)點值進行比較，如果要插入的值大于根結(jié)點值，則轉(zhuǎn)換成根節(jié)點的右子樹插入該值，如果要插入的值小于根結(jié)點值，則轉(zhuǎn)換成根節(jié)點的左子樹插入該值，要刪除的值等于根結(jié)點值則返回false（搜索二叉樹內(nèi)不允許有相同數(shù)值的結(jié)點），如果根節(jié)點為空，則創(chuàng)建一個值為要插入值的結(jié)點，然后和父親結(jié)點進行鏈接即可，但是如何和父親結(jié)點進行鏈接呢？

方法一：可以給_InsertR函數(shù)加一個parent指針參數(shù)，如下圖所示，每次調(diào)用_InsertR函數(shù)的時候除了將root的左子樹和右子樹傳過去也將root傳過去，那么每次parent指針指向的都是本次root結(jié)點的父結(jié)點，最后如果根節(jié)點為空，則創(chuàng)建一個值為要插入值的結(jié)點，然后和parent指針指向的結(jié)點進行鏈接即可。

方法二：可以給_InsertR函數(shù)的root參數(shù)加上引用，如下圖所示，這樣如果根節(jié)點為空時，則創(chuàng)建一個值為要插入值的結(jié)點，將結(jié)點指針賦值給root，因為這里root是上一層父節(jié)點的_left或_right的引用，那么賦值的時候就已經(jīng)和父結(jié)點進行了鏈接。

因為方法二的實現(xiàn)更加簡潔，我們使用方法二的思路來實現(xiàn)遞歸版本的插入函數(shù)，如下圖所示

2.如下圖所示是搜索二叉樹刪除函數(shù)的遞歸實現(xiàn)，用要刪除入的值和根結(jié)點值進行比較，如果要刪除的值大于根結(jié)點值，則轉(zhuǎn)換成根節(jié)點的右子樹刪除該值，如果要刪除的值小于根結(jié)點值，則轉(zhuǎn)換成根節(jié)點的左子樹刪除該值，如果要刪除的值等于根結(jié)點值，則和普通搜索二叉樹刪除函數(shù)一樣，需要分三種情況（要刪除的結(jié)點無孩子結(jié)點的情況融合在要刪除的結(jié)點只有左孩子結(jié)點的情況內(nèi)）

（1）要刪除的結(jié)點只有左孩子結(jié)點，遞歸找到要刪除的結(jié)點，此時root指向要刪除的結(jié)點，那么需要將root指針指向結(jié)點的_left指針指向結(jié)點和root指針指向結(jié)點的父節(jié)點進行鏈接，然后釋放root指針指向的結(jié)點，這里直接將root->_left賦值給root就可以完成除釋放結(jié)點以外的其他工作，因為這里root是上一層父節(jié)點的_left或_right的引用，那么賦值的時候就已經(jīng)將root指針指向結(jié)點的_left指針指向結(jié)點和root的父結(jié)點進行了鏈接。（2）要刪除的結(jié)點只有右孩子結(jié)點，遞歸找到要刪除的結(jié)點，此時root指向要刪除的結(jié)點，那么需要將root指針指向結(jié)點的_right指針指向結(jié)點和root指針指向結(jié)點的父節(jié)點進行鏈接，然后釋放root指針指向的結(jié)點，這里直接將root->_right賦值給root就可以完成除釋放結(jié)點以外的其他工作，因為這里root是上一層父節(jié)點的_left或_right的引用，那么賦值的時候就已經(jīng)將root指針指向結(jié)點的_right指針指向結(jié)點和root的父結(jié)點進行了鏈接。（3）要刪除的結(jié)點有左、右孩子結(jié)點，與普通搜索二叉樹那里一樣，遞歸找到要刪除的結(jié)點，此時root指向要刪除的結(jié)點，使用minRight指針找到要刪除結(jié)點的右子樹最小值結(jié)點（找左子樹大值結(jié)點也行，這里以右子樹最小值結(jié)點為例），將minRight指針指向的右子樹最小值結(jié)點的值與root指向的要刪除結(jié)點的值交換，然后釋放minRight指針指向的結(jié)點即可。釋放minRight指針指向的結(jié)點有兩種方式。一種方式和普通搜索二叉樹那里一樣，使用minParent指針來找到要刪除結(jié)點右子樹最小值結(jié)點的父節(jié)點，將該父節(jié)點和右子樹最小值結(jié)點的子節(jié)點進行鏈接然后釋放minRight指針指向的右子樹最小值結(jié)點。另一種方式是調(diào)用遞歸刪除函數(shù)，刪除root指向的要刪除結(jié)點右子樹中的要刪除的值（因為原本要刪除結(jié)點的右子樹最小值結(jié)點交換后此時存的值是要刪除的值）（交換后root指向的要刪除結(jié)點右子樹依然是一顆搜索樹）

注：先使用del指針將root指針的內(nèi)容保存起來，那么del指針和root指針此時指向相同的結(jié)點，最后要釋放root指針指向結(jié)點的時候，此時root指針已經(jīng)被修改，delete del就釋放了原root指針指向的結(jié)點

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

1.K模型：K模型即只有key作為關(guān)鍵碼，結(jié)構(gòu)中只需要存儲Key即可，關(guān)鍵碼即為需要搜索到的值。 $\bullet$ 比如：給一個單詞word，判斷該單詞是否拼寫正確，具體方式是以詞庫中所有單詞集合中的每個單詞作為key，構(gòu)建一棵二叉搜索樹 ?。在二叉搜索樹中檢索該單詞是否存在，存在則拼寫正確，不存在則拼寫錯誤。 K模型二叉搜索樹代碼實現(xiàn)：

#pragma once

#includenamespace key
{
	template//struct BinarySearchTreeNode
	struct BSTreeNode
	{
		BSTreeNode* _left;
		BSTreeNode* _right;

		K _key;

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

	templateclass BSTree
	{
		typedef BSTreeNodeNode;
	private:
		void DestoryTree(Node* root)
		{
			if (root == nullptr)
				return;

			DestoryTree(root->_left);
			DestoryTree(root->_right);
			delete root;
		}

		Node* CopyTree(Node* root)
		{
			if (root == nullptr)
				return nullptr;

			Node* copyNode = new Node(root->_key);
			copyNode->_left = CopyTree(root->_left);
			copyNode->_right = CopyTree(root->_right);

			return copyNode;
		}
	public:
		// 強制編譯器自己生成構(gòu)造
		// C++11
		BSTree() = default;

		BSTree(const BSTree& t)
		{
			_root = CopyTree(t._root);
		}

		// t1 = t2
		BSTree& operator=(BSTreet)
		{
			swap(_root, t._root);
			return *this;
		}

		~BSTree()
		{
			DestoryTree(_root);
			_root = nullptr;
		}

		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:
		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;
					}

					swap(root->_key, minRight->_key);

					return _EraseR(root->_right, 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;
		}

		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;
			}
		}

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

			_InOrder(root->_left);
			cout<< root->_key<< " ";
			_InOrder(root->_right);
		}
	private:
		Node* _root = nullptr;
	};

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

		t.InsertR(9);

		BSTreecopy = t;
		copy.InOrder();
	}

	void TestBSTree2()
	{
		BSTreet;
		int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
		for (auto e : a)
		{
			t.InsertR(e);
		}
		t.InOrder();
		t.EraseR(3);
		t.EraseR(8);

		t.InOrder();
		t.EraseR(14);
		t.EraseR(7);
		t.InOrder();

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

}

2.KV模型：每一個關(guān)鍵碼key，都有與之對應(yīng)的值Value，即的鍵值對。該種方式在現(xiàn)實生活中非常常見： $\bullet$ 比如：英漢詞典就是英文與中文的對應(yīng)關(guān)系，通過英文可以快速找到與其對應(yīng)的中文，英文單詞與其對應(yīng)的中文就構(gòu)成一種鍵值對。 $\bullet$ 比如：統(tǒng)計單詞次數(shù)，統(tǒng)計成功后，給定單詞就可快速找到其出現(xiàn)的次數(shù)，單詞與其出現(xiàn)次數(shù)就是就構(gòu)成一種鍵值對。 KV模型二叉搜索樹代碼實現(xiàn)：
#pragma once #includenamespace key_value { #pragma once templatestruct BSTreeNode { BSTreeNode* _left; BSTreeNode* _right; const K _key; V _value; BSTreeNode(const K& key, const V& value) :_left(nullptr) , _right(nullptr) , _key(key) , _value(value) {} }; templateclass BSTree { typedef BSTreeNodeNode; public: 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: 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; } swap(root->_key, minRight->_key); return _EraseR(root->_right, key); } delete del; return true; } } 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->_right, key, value); else if (root->_key >key) return _InsertR(root->_left, 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; } } 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 TestBSTree1() { BSTreeECDict; ECDict.InsertR("root", "根"); ECDict.InsertR("string", "字符串"); ECDict.InsertR("left", "左邊"); ECDict.InsertR("insert", "插入"); //... string str; while (cin >>str) //while (scanf() != EOF) { //BSTreeNode* ret = ECDict.FindR(str); auto ret = ECDict.FindR(str); if (ret != nullptr) { cout<< "對應(yīng)的中文:"<< ret->_value<< endl; } else { cout<< "無此單詞，請重新輸入"<< endl; } } } void TestBSTree2() { string arr[] = { "蘋果", "西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜", "蘋果", "香蕉", "蘋果", "香蕉" }; // 水果出現(xiàn)的次數(shù) BSTreecountTree; for (const auto& str : arr) { auto ret = countTree.FindR(str); if (ret == nullptr) { countTree.InsertR(str, 1); } else { ret->_value++; // 修改value } } countTree.InOrder(); } }
注：
1.在KV模型的搜索二叉樹中插入、查找、刪除函數(shù)仍然都是以key為依據(jù)進行的操作的。 2.KV模型的搜索二叉樹中，每個節(jié)點的value值可能相同，每個節(jié)點的key值都不相同 3.與K模型搜索二叉樹不同的是，KV模型在_FindR搜索函數(shù)中返回值應(yīng)該為找到的結(jié)點指針。K模型搜索二叉樹_FindR搜索函數(shù)不返回結(jié)點指針的原因是不能修改key的值，否則很可能不再是一個搜索樹，KV模型搜索二叉樹_FindR搜索函數(shù)返回結(jié)點指針的原因是key的值不能修改，但是可以修改value值，因此找到對應(yīng)結(jié)點后需要返回結(jié)點的指針，為了保證返回結(jié)點指針后key值不被修改，將結(jié)點的_key成員變量用const修飾，這樣建立結(jié)點的時候可以對key值進行初始化，后面無法再被修改，如下圖所示。 4.代碼while (cin >>str)和代碼while (scanf() != EOF)的功能相同，都是持續(xù)輸入輸出內(nèi)容。當scanf函數(shù)讀取控制臺數(shù)據(jù)時遇到文件結(jié)束/文件讀取失敗標志EOF時會返回EOF；string類里面重載的operator>>流提取函數(shù)返回的是cin，如下圖一所示，cin是istream類的對象。 ios類中有兩個函數(shù)c++98中的operator void* ()和c++11中的operator bool()如下圖一二所示，這兩個函數(shù)的功能是判斷是否提取到文件結(jié)束/文件讀取失敗標志EOF，提取到EOF則返回真，沒有提取到EOF則返回假。 istream類是繼承ios類的，因此istream類的對象cin也有operator void* ()和operator bool()兩個函數(shù)。當cin >>str代碼返回cin進行while循環(huán)條件判斷的時候，c++98中cin對象會進行隱式類型轉(zhuǎn)換，會cin.operator void*調(diào)用operator void* ()函數(shù)，該函數(shù)判斷是否遇見文件結(jié)束/文件讀取失敗標志EOF，如果是EOF標志就返回空指針，如果不是EOF就返回非空指針；c++11中cin對象會進行隱式類型轉(zhuǎn)換，會cin.operator bool調(diào)用operator bool()函數(shù)，該函數(shù)判斷是否遇見文件結(jié)束/文件讀取失敗標志EOF，如果是EOF標志就返回0，如果不是EOF就返回1。
如果想手動輸入EOF標志來退出持續(xù)輸入輸出狀態(tài)可以使用Ctrl+z，Ctrl z控制臺就會輸入EOF，然后回車讓scanf或>>進行讀取即可。
ctrl+c也可以退出持續(xù)輸入輸出狀態(tài)，ctrl c的功能是直接結(jié)束進程。
下圖一所示的代碼與上面while (cin >>str)部分的原理類似，while的判斷部分是A類的對象a，在判斷的時候?qū)ο骯會進行隱式類型轉(zhuǎn)換，自動去調(diào)用對象a里面的operator bool函數(shù)，operator bool函數(shù)的返回值作為while循環(huán)的判斷條件。其中代碼while(a)與while(a.operator bool)是等價的。
如下圖二所示，這里while(a)中a對象的隱式類型轉(zhuǎn)換和A aa = 10中的隱式類型轉(zhuǎn)換相同。A aa = 10代碼因為類型不同，會先調(diào)用A類的構(gòu)造函數(shù)構(gòu)造成員變量_a為10的對象，此時類型相同，再拷貝構(gòu)造給aa（編譯器優(yōu)化成直接用10對aa對象調(diào)用構(gòu)造函數(shù)進行構(gòu)造）；while(a)代碼因為對象a和真假判斷的bool類型不同，會先調(diào)用A類的operator bool函數(shù)，operator bool函數(shù)返回一個bool類型的值，此時類型相同可以進行while循環(huán)的判斷。那么代碼bool ret = a，使用A類型的對象a初始化bool類型的對象ret也是可以的，這里類型不同，發(fā)生隱式類型轉(zhuǎn)換，對象a調(diào)用operator bool函數(shù)返回一個bool類型的值，賦值給ret。
我們發(fā)現(xiàn)庫中的operator bool函數(shù)是用explicit關(guān)鍵字修飾的，如下圖一所示，explicit關(guān)鍵字限制不能使用該函數(shù)進行隱式類型轉(zhuǎn)換，那為什么我們前面使用代碼while (cin >>str)，cin對象還能調(diào)用其operator bool函數(shù)呢？
其實explicit關(guān)鍵字只限制類似A aa = 10和bool ret = a這種調(diào)用explicit所修飾的函數(shù)進行隱式類型轉(zhuǎn)換初始化的情況，而不會去限制while(a)這種的隱式類型轉(zhuǎn)換，如下圖一所示。
其實也可以使用類似operator int()的函數(shù)來滿足類似int y = a和while(a)，將A類型的對象a隱式類型轉(zhuǎn)換成對應(yīng)類型的功能，如下圖二所示。

3.二叉搜索樹具有去重+排序功能。將所有的數(shù)據(jù)依次插入到二叉搜索樹中（去重），然后進行中序遍歷（排序），得到的結(jié)果就是對數(shù)據(jù)集去重排序后的結(jié)果，整個去重排序的效率可以達到 $N\times log_{2}^{N}$ （搜索樹是完全二叉樹的情況）。

注：
1.搜索二叉樹如果插入順序不同，樹的形狀也不同，如果形狀近似一個完全二叉樹，那么無論是K模型、KV模型的搜索效率還是去重排序的效率都很高，但是如果形狀近似一個鏈表，那么K模型、KV模型的搜索效率和去重排序的效率都很低。
2.我們后面會學到平衡樹，平衡樹是對搜索二叉樹的一種改進，使得插入數(shù)據(jù)后樹的形狀接近完全二叉樹
3.K模型搜索二叉樹對應(yīng)std庫中的數(shù)據(jù)結(jié)構(gòu)是set，KV模型搜索二叉樹對應(yīng)std庫中的數(shù)據(jù)結(jié)構(gòu)是map

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站欄目：c++-第15節(jié)-二叉樹進階-創(chuàng)新互聯(lián)
分享地址：http://www.rwnh.cn/article16/pdodg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供云服務(wù)器、關(guān)鍵詞優(yōu)化、手機網(wǎng)站建設(shè)、搜索引擎優(yōu)化、域名注冊、做網(wǎng)站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

中文字幕日韩精品一区二区免费_精品一区二区三区国产精品无卡在_国精品无码专区一区二区三区_国产αv三级中文在线

c++-第15節(jié)-二叉樹進階-創(chuàng)新互聯(lián)