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

1. 二叉搜索樹(shù) 1.1.二叉搜索樹(shù)概念

二叉搜索樹(shù)又稱(chēng)二叉排序樹(shù)，它或者是一棵空樹(shù)，或者是具有以下性質(zhì)的二叉樹(shù): 若它的左子樹(shù)不為空，則左子樹(shù)上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值 若它的右子樹(shù)不為空，則右子樹(shù)上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值 它的左右子樹(shù)也分別為二叉搜索樹(shù) 也就是說(shuō)，搜索二叉樹(shù)的任意一個(gè)子樹(shù)都需要滿(mǎn)足，左子樹(shù)的值<根<右子樹(shù)的值

成都創(chuàng)新互聯(lián)公司主要從事網(wǎng)站制作、網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)浦口,十多年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專(zhuān)業(yè),歡迎來(lái)電咨詢(xún)建站服務(wù):13518219792

注：

1.搜索二叉樹(shù)數(shù)據(jù)的查找效率為O(N)，當(dāng)搜索二叉樹(shù)接近完全時(shí)，數(shù)據(jù)的查找效率較高，接近。

2.當(dāng)使用中序遍歷遍歷搜索二叉樹(shù)時(shí)，遍歷出來(lái)的數(shù)據(jù)是增序的。

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

二叉搜索樹(shù)普通實(shí)現(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:
	// 強(qiáng)制編譯器自己生成構(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
			{
				// 一個(gè)孩子--左為空 or 右為空
				// 兩個(gè)孩子 -- 替換法
				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 // 兩個(gè)孩子都不為空
				{
					// 右子樹(shù)的最小節(jié)點(diǎn)替代
					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. 二叉搜索樹(shù)的查找介紹 a.從根開(kāi)始比較，查找，比根大則往右邊走查找，比根小則往左邊走查找。 b.最多查找高度次，走到到空，還沒(méi)找到，這個(gè)值不存在。 2. 二叉搜索樹(shù)的插入介紹 插入的具體過(guò)程如下： a.樹(shù)為空，則直接新增節(jié)點(diǎn)，賦值給root指針 b.樹(shù)不空，按二叉搜索樹(shù)性質(zhì)查找插入位置，插入新節(jié)點(diǎn) 具體思路為：定義兩個(gè)指針parent和cur，cur查找插入位置，parent記錄cur上一個(gè)位置，當(dāng)cur找到插入位置時(shí)（cur為空時(shí)），開(kāi)辟節(jié)點(diǎn)給cur并和parent進(jìn)行鏈接。

注：

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

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

3. 二叉搜索樹(shù)的刪除介紹??

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

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

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

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

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

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

5.搜索二叉樹(shù)的拷貝構(gòu)造函數(shù)和賦值運(yùn)算符重載函數(shù)需要進(jìn)行深拷貝，這里深拷貝不能復(fù)用insert插入函數(shù)，因?yàn)椴迦氲捻樞虿煌阉鞫鏄?shù)也不同。我們寫(xiě)一個(gè)CopyTree函數(shù)來(lái)遞歸創(chuàng)建一個(gè)相同的樹(shù)，如下圖一所示，然后搜索二叉樹(shù)的拷貝構(gòu)造函數(shù)復(fù)用CopyTree函數(shù)即可，如下圖二所示

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

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

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

二叉搜索樹(shù)遞歸實(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:
	// 強(qiáng)制編譯器自己生成構(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ù)插入函數(shù)的遞歸實(shí)現(xiàn)，用要插入的值和根結(jié)點(diǎn)值進(jìn)行比較，如果要插入的值大于根結(jié)點(diǎn)值，則轉(zhuǎn)換成根節(jié)點(diǎn)的右子樹(shù)插入該值，如果要插入的值小于根結(jié)點(diǎn)值，則轉(zhuǎn)換成根節(jié)點(diǎn)的左子樹(shù)插入該值，要?jiǎng)h除的值等于根結(jié)點(diǎn)值則返回false（搜索二叉樹(shù)內(nèi)不允許有相同數(shù)值的結(jié)點(diǎn)），如果根節(jié)點(diǎn)為空，則創(chuàng)建一個(gè)值為要插入值的結(jié)點(diǎn)，然后和父親結(jié)點(diǎn)進(jìn)行鏈接即可，但是如何和父親結(jié)點(diǎn)進(jìn)行鏈接呢？

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

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

因?yàn)榉椒ǘ膶?shí)現(xiàn)更加簡(jiǎn)潔，我們使用方法二的思路來(lái)實(shí)現(xiàn)遞歸版本的插入函數(shù)，如下圖所示

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

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

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

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

1.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ò)誤。 K模型二叉搜索樹(shù)代碼實(shí)現(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:
		// 強(qiáng)制編譯器自己生成構(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模型：每一個(gè)關(guān)鍵碼key，都有與之對(duì)應(yīng)的值Value，即的鍵值對(duì)。該種方式在現(xiàn)實(shí)生活中非常常見(jiàn)： 比如：英漢詞典就是英文與中文的對(duì)應(yīng)關(guān)系，通過(guò)英文可以快速找到與其對(duì)應(yīng)的中文，英 文單詞與其對(duì)應(yīng)的中文就構(gòu)成一種鍵值對(duì)。 比如：統(tǒng)計(jì)單詞次數(shù)，統(tǒng)計(jì)成功后，給定單詞就可快速找到其出現(xiàn)的次數(shù)，單詞與其出 現(xiàn)次數(shù)就是就構(gòu)成一種鍵值對(duì)。 KV模型二叉搜索樹(shù)代碼實(shí)現(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<< "對(duì)應(yīng)的中文:"<< ret->_value<< endl;
			}
			else
			{
				cout<< "無(wú)此單詞，請(qǐng)重新輸入"<< endl;
			}
		}
	}

	void TestBSTree2()
	{
		string arr[] = { "蘋(píng)果", "西瓜", "蘋(píng)果", "西瓜", "蘋(píng)果", "蘋(píng)果", "西瓜", "蘋(píng)果", "香蕉", "蘋(píng)果", "香蕉" };
		// 水果出現(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ù)中插入、查找、刪除函數(shù)仍然都是以key為依據(jù)進(jìn)行的操作的。 2.KV模型的搜索二叉樹(shù)中，每個(gè)節(jié)點(diǎn)的value值可能相同，每個(gè)節(jié)點(diǎn)的key值都不相同 3.與K模型搜索二叉樹(shù)不同的是，KV模型在_FindR搜索函數(shù)中返回值應(yīng)該為找到的結(jié)點(diǎn)指針。K模型搜索二叉樹(shù)_FindR搜索函數(shù)不返回結(jié)點(diǎn)指針的原因是不能修改key的值，否則很可能不再是一個(gè)搜索樹(shù)，KV模型搜索二叉樹(shù)_FindR搜索函數(shù)返回結(jié)點(diǎn)指針的原因是key的值不能修改，但是可以修改value值，因此找到對(duì)應(yīng)結(jié)點(diǎn)后需要返回結(jié)點(diǎn)的指針，為了保證返回結(jié)點(diǎn)指針后key值不被修改，將結(jié)點(diǎn)的_key成員變量用const修飾，這樣建立結(jié)點(diǎn)的時(shí)候可以對(duì)key值進(jìn)行初始化，后面無(wú)法再被修改，如下圖所示。 4.代碼while (cin >>str)和代碼while (scanf() != EOF)的功能相同，都是持續(xù)輸入輸出內(nèi)容。當(dāng)scanf函數(shù)讀取控制臺(tái)數(shù)據(jù)時(shí)遇到文件結(jié)束/文件讀取失敗標(biāo)志EOF時(shí)會(huì)返回EOF；string類(lèi)里面重載的operator>>流提取函數(shù)返回的是cin，如下圖一所示，cin是istream類(lèi)的對(duì)象。 ios類(lèi)中有兩個(gè)函數(shù)c++98中的operator void* ()和c++11中的operator bool()如下圖一二所示，這兩個(gè)函數(shù)的功能是判斷是否提取到文件結(jié)束/文件讀取失敗標(biāo)志EOF，提取到EOF則返回真，沒(méi)有提取到EOF則返回假。 istream類(lèi)是繼承ios類(lèi)的，因此istream類(lèi)的對(duì)象cin也有operator void* ()和operator bool()兩個(gè)函數(shù)。當(dāng)cin >>str代碼返回cin進(jìn)行while循環(huán)條件判斷的時(shí)候，c++98中cin對(duì)象會(huì)進(jìn)行隱式類(lèi)型轉(zhuǎn)換，會(huì)cin.operator void*調(diào)用operator void* ()函數(shù)，該函數(shù)判斷是否遇見(jiàn)文件結(jié)束/文件讀取失敗標(biāo)志EOF，如果是EOF標(biāo)志就返回空指針，如果不是EOF就返回非空指針；c++11中cin對(duì)象會(huì)進(jìn)行隱式類(lèi)型轉(zhuǎn)換，會(huì)cin.operator bool調(diào)用operator bool()函數(shù)，該函數(shù)判斷是否遇見(jiàn)文件結(jié)束/文件讀取失敗標(biāo)志EOF，如果是EOF標(biāo)志就返回0，如果不是EOF就返回1。

如果想手動(dòng)輸入EOF標(biāo)志來(lái)退出持續(xù)輸入輸出狀態(tài)可以使用Ctrl+z，Ctrl z控制臺(tái)就會(huì)輸入EOF，然后回車(chē)讓scanf或>>進(jìn)行讀取即可。

ctrl+c也可以退出持續(xù)輸入輸出狀態(tài)，ctrl c的功能是直接結(jié)束進(jìn)程。

下圖一所示的代碼與上面while (cin >>str)部分的原理類(lèi)似，while的判斷部分是A類(lèi)的對(duì)象a，在判斷的時(shí)候?qū)ο骯會(huì)進(jìn)行隱式類(lèi)型轉(zhuǎn)換，自動(dòng)去調(diào)用對(duì)象a里面的operator bool函數(shù)，operator bool函數(shù)的返回值作為while循環(huán)的判斷條件。其中代碼while(a)與while(a.operator bool)是等價(jià)的。

如下圖二所示，這里while(a)中a對(duì)象的隱式類(lèi)型轉(zhuǎn)換和A aa = 10中的隱式類(lèi)型轉(zhuǎn)換相同。A aa = 10代碼因?yàn)轭?lèi)型不同，會(huì)先調(diào)用A類(lèi)的構(gòu)造函數(shù)構(gòu)造成員變量_a為10的對(duì)象，此時(shí)類(lèi)型相同，再拷貝構(gòu)造給aa（編譯器優(yōu)化成直接用10對(duì)aa對(duì)象調(diào)用構(gòu)造函數(shù)進(jìn)行構(gòu)造）；while(a)代碼因?yàn)閷?duì)象a和真假判斷的bool類(lèi)型不同，會(huì)先調(diào)用A類(lèi)的operator bool函數(shù)，operator bool函數(shù)返回一個(gè)bool類(lèi)型的值，此時(shí)類(lèi)型相同可以進(jìn)行while循環(huán)的判斷。那么代碼bool ret = a，使用A類(lèi)型的對(duì)象a初始化bool類(lèi)型的對(duì)象ret也是可以的，這里類(lèi)型不同，發(fā)生隱式類(lèi)型轉(zhuǎn)換，對(duì)象a調(diào)用operator bool函數(shù)返回一個(gè)bool類(lèi)型的值，賦值給ret。

我們發(fā)現(xiàn)庫(kù)中的operator bool函數(shù)是用explicit關(guān)鍵字修飾的，如下圖一所示，explicit關(guān)鍵字限制不能使用該函數(shù)進(jìn)行隱式類(lèi)型轉(zhuǎn)換，那為什么我們前面使用代碼while (cin >>str)，cin對(duì)象還能調(diào)用其operator bool函數(shù)呢？

其實(shí)explicit關(guān)鍵字只限制類(lèi)似A aa = 10和bool ret = a這種調(diào)用explicit所修飾的函數(shù)進(jìn)行隱式類(lèi)型轉(zhuǎn)換初始化的情況，而不會(huì)去限制while(a)這種的隱式類(lèi)型轉(zhuǎn)換，如下圖一所示。

其實(shí)也可以使用類(lèi)似operator int()的函數(shù)來(lái)滿(mǎn)足類(lèi)似int y = a和while(a)，將A類(lèi)型的對(duì)象a隱式類(lèi)型轉(zhuǎn)換成對(duì)應(yīng)類(lèi)型的功能，如下圖二所示。

3.二叉搜索樹(shù)具有去重+排序功能。將所有的數(shù)據(jù)依次插入到二叉搜索樹(shù)中（去重），然后進(jìn)行中序遍歷（排序），得到的結(jié)果就是對(duì)數(shù)據(jù)集去重排序后的結(jié)果，整個(gè)去重排序的效率可以達(dá)到（搜索樹(shù)是完全二叉樹(shù)的情況）。

注：

1.搜索二叉樹(shù)如果插入順序不同，樹(shù)的形狀也不同，如果形狀近似一個(gè)完全二叉樹(shù)，那么無(wú)論是K模型、KV模型的搜索效率還是去重排序的效率都很高，但是如果形狀近似一個(gè)鏈表，那么K模型、KV模型的搜索效率和去重排序的效率都很低。

2.我們后面會(huì)學(xué)到平衡樹(shù)，平衡樹(shù)是對(duì)搜索二叉樹(shù)的一種改進(jìn)，使得插入數(shù)據(jù)后樹(shù)的形狀接近完全二叉樹(shù)

3.K模型搜索二叉樹(shù)對(duì)應(yīng)std庫(kù)中的數(shù)據(jù)結(jié)構(gòu)是set，KV模型搜索二叉樹(shù)對(duì)應(yīng)std庫(kù)中的數(shù)據(jù)結(jié)構(gòu)是map

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

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

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

廣告

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