1.內(nèi)容

建議再看這節(jié)之前能對C++有一定了解

二叉樹在前面C的數(shù)據(jù)結(jié)構(gòu)階段時(shí)有出過，現(xiàn)在我們對二叉樹來學(xué)習(xí)一些更復(fù)雜的類型，也為之后C++學(xué)習(xí)的 map 和 set 做鋪墊

• 1. map和set特性需要先鋪墊二叉搜索樹，而二叉搜索樹也是一種樹形結(jié)構(gòu)
• 2. 二叉搜索樹的特性了解，有助于更好的理解map和set的特性
• 3. 有些OJ題使用C語言方式實(shí)現(xiàn)比較麻煩，比如有些地方要返回動(dòng)態(tài)開辟的二維數(shù)組。

因此本節(jié)文章所涉及到的知識(shí)點(diǎn)有很多都會(huì)與C++有關(guān)

2.搜索二叉樹：

??搜索二叉樹的概念：

二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質(zhì)的二叉樹:

• 若它的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值
• 若它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值
• 它的左右子樹也分別為二叉搜索樹

??搜索二叉樹的操作

?int? a[ ] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };

??二叉搜索樹的查找

• 1. 從根開始比較，查找，比根大則往右邊走查找，比根小則往左邊走查找。
• 2. 最多查找高度次，走到到空，還沒找到，這個(gè)值不存在。

??搜索二叉樹的插入：

插入的具體過程如下：

• 1. 樹為空，則直接新增節(jié)點(diǎn)，賦值給root指針
• 2. 樹不空，按二叉搜索樹性質(zhì)查找插入位置，插入新節(jié)點(diǎn)

??搜索二叉樹的刪除

刪除時(shí)搜索二叉樹最復(fù)雜的地方，他只要分為三種情況：

1. 刪除葉子節(jié)點(diǎn)

也就是左右都無孩子的節(jié)點(diǎn)，直接刪除就行

2. 刪除只有一個(gè)孩子的節(jié)點(diǎn)

左孩子為空，或者右孩子為空

這種情況需要將他們的下一個(gè)孩子節(jié)點(diǎn)接到其父節(jié)點(diǎn)上

3.刪除兩邊都有孩子的節(jié)點(diǎn)

如刪除 8 或者 3

這種清空就比較復(fù)雜，我們用替換原則，找左樹的最大節(jié)點(diǎn)或者去找右樹的最小節(jié)點(diǎn)來替換。

比如我們要?jiǎng)h除8，就需要找左樹的最大節(jié)點(diǎn)進(jìn)行替換，左樹的最大節(jié)點(diǎn)是7，我們將其與放到8的位置，將6的右節(jié)點(diǎn)置為空即可

??搜索二叉樹的實(shí)現(xiàn)：

1.創(chuàng)建：

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

	BSTreeNode(const K& key) //初始化列表進(jìn)行初始化
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
	{}
};

2.?插入操作：

   	bool Insert(const K& key)
	{
		// 1.先判斷跟為空
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		// 利用循環(huán)判斷cur節(jié)點(diǎn)的值與插入值的大小，來缺點(diǎn)插入值放到哪
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		// 新創(chuàng)建一個(gè)節(jié)點(diǎn)放入插入值
		cur = new Node(key);
		// 將新節(jié)點(diǎn)進(jìn)行鏈接
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		return true;
	}

3.查找操作：

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

4.打印操作：

	// 利用遞歸打印，因?yàn)轭愅饽貌坏絖root，
    // 所以給遞歸又加了個(gè)嵌套函數(shù)，用該類內(nèi)的函數(shù)去調(diào)_root
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	// 直接寫這個(gè)函數(shù)，在類外面不能調(diào)_root，所以傳參比較困難
    // 因?yàn)開root是私有成員，所以序號再套上面的一層函數(shù)
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
    
    // 中序遍歷的邏輯打印
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}

5.刪除操作

上面所說的刪除葉子節(jié)點(diǎn)的情況，可以直接放到入到第二種情況下一并解決，

在第二種情況的時(shí)候需要注意：

這種情況要去判斷要?jiǎng)h除的節(jié)點(diǎn)是否為根節(jié)點(diǎn)，如果是就直接把下面的孩子節(jié)點(diǎn)換成根節(jié)點(diǎn)就行

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

		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				// 刪除
				// 1、左為空
				// 如果此時(shí)根節(jié)點(diǎn)只有一個(gè)孩子，此時(shí)要?jiǎng)h除根節(jié)點(diǎn)，
				// 就不會(huì)進(jìn)入之前的判斷，會(huì)導(dǎo)致parent為空的空指針問題
                // 可看上圖了解
				if (cur->_left == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}

					}
					delete cur;
				} 
				// 2、右為空
				// 如果此時(shí)根節(jié)點(diǎn)只有一個(gè)孩子，此時(shí)要?jiǎng)h除根節(jié)點(diǎn)，
				// 就不會(huì)進(jìn)入之前的判斷，會(huì)導(dǎo)致parent為空的空指針問題
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}
					delete cur;
				}
				else
				{
					// 找右樹最小節(jié)點(diǎn)替代，也可以是左樹最大節(jié)點(diǎn)替代
                    // 這里我們用的是右數(shù)的最小節(jié)點(diǎn)
					Node* pminRight = cur;	// pminRight是minRight的父節(jié)點(diǎn)
					Node* minRight = cur->_right;
					while (minRight->_left)
					{
						pminRight = minRight;
						minRight = minRight->_left;
					}

					cur->_key = minRight->_key;

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

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

??源代碼如下

#include <iostream>
using namespace std;

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:
    // 插入
	bool Insert(const K& key)
	{
		// 1.先判斷跟為空
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		
		Node* parent = nullptr;
		Node* cur = _root;
		// 利用循環(huán)判斷cur節(jié)點(diǎn)的值與插入值的大小，來缺點(diǎn)插入值放到哪
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		// 新創(chuàng)建一個(gè)節(jié)點(diǎn)放入插入值
		cur = new Node(key);
		// 將新節(jié)點(diǎn)進(jìn)行鏈接
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		return true;
	}

    // 查找
	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 = Find(key);

		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				// 刪除
				// 1、左為空
				// 如果此時(shí)根節(jié)點(diǎn)只有一個(gè)孩子，此時(shí)要?jiǎng)h除根節(jié)點(diǎn)，
				// 就不會(huì)進(jìn)入之前的判斷，會(huì)導(dǎo)致parent為空的空指針問題
				if (cur->_left == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}

					}
					delete cur;
				} 
				// 2、右為空
				// 如果此時(shí)根節(jié)點(diǎn)只有一個(gè)孩子，此時(shí)要?jiǎng)h除根節(jié)點(diǎn)，
				// 就不會(huì)進(jìn)入之前的判斷，會(huì)導(dǎo)致parent為空的空指針問題
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}
					delete cur;
				}
				else
				{
					// 找右樹最小節(jié)點(diǎn)替代，也可以是左樹最大節(jié)點(diǎn)替代
					Node* pminRight = cur;		// pminRight是minRight的父節(jié)點(diǎn)
					Node* minRight = cur->_right;
					while (minRight->_left)
					{
						pminRight = minRight;
						minRight = minRight->_left;
					}

					cur->_key = minRight->_key;

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

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


    // 打印
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;

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

private:
	Node* _root = nullptr;
};




//測試
void TestBSTree()
{
	int a[] = { 8, 3, 1, 6, 4, 7, 10, 14, 13 };
	BSTree<int> t1;

    // 循環(huán)插入
	for (auto e : a)
	{
		t1.Insert(e);
	}

	t1.InOrder();

	t1.Erase(13);
	t1.Erase(14);
	t1.Erase(10);
	t1.Erase(4);
	t1.Erase(6);
	t1.Erase(3);

	t1.InOrder();
}
int main()
{
	TestBSTree();

	return 0;
}

3.搜索二叉樹的性能分析

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

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

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

最優(yōu)情況下，二叉搜索樹為完全二叉樹(或者接近完全二叉樹)，其平均比較次數(shù)為：
最差情況下，二叉搜索樹退化為單支樹(或者類似單支)，其平均比較次數(shù)為：

如果退化成單支樹，二叉搜索樹的性能就失去了。
那能否進(jìn)行改進(jìn)，不論按照什么次序插 入關(guān)鍵碼，二叉搜索樹的性能都能達(dá)到最優(yōu)？

所以我們后面還會(huì)對AVL樹和紅黑樹做為重點(diǎn)學(xué)習(xí)文章來源地址http://www.zghlxwxcb.cn/news/detail-568704.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)_進(jìn)階（1）：搜索二叉樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！