＜C++＞手撕搜索二叉樹-創(chuàng)新互聯(lián)

創(chuàng)新互聯(lián)建站是網(wǎng)站建設(shè)技術(shù)企業(yè)，為成都企業(yè)提供專業(yè)的網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計，網(wǎng)站設(shè)計，網(wǎng)站制作，網(wǎng)站改版等技術(shù)服務(wù)。擁有10多年豐富建站經(jīng)驗和眾多成功案例，為您定制適合企業(yè)的網(wǎng)站。10多年品質(zhì)，值得信賴！

一、搜索二叉樹的性質(zhì)

二、搜索二叉樹的結(jié)構(gòu)定義

三、手撕搜索二叉樹非遞歸

1）Insert()

2）Find()

3）Erase()

4）InOder()

5）BSTree(const BSTree& t) 拷貝構(gòu)造

6）~BSTree()析構(gòu)函數(shù)

四、手撕搜索二叉樹遞歸

1）InsertR()

2）FindR()

3）EraseR()

五、搜索二叉樹完整代碼

一、搜索二叉樹的性質(zhì)

左子樹上所有的節(jié)點的值都小于根節(jié)點的值
右子樹上所有節(jié)點的值都大于根節(jié)點的值
它的左右子樹分別為二叉搜索樹

二、搜索二叉樹的結(jié)構(gòu)定義

搜索二叉樹主要實現(xiàn)的是K或K/Value模型，這里我們使用K模型來定義，即可以用O(N)的時間復(fù)雜度來進行K值的搜索。

使用模板來定義

templatestruct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;
	K _key;

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

	}
};

三、手撕搜索二叉樹非遞歸 1）Insert()

插入有兩種情況：

_root == nullptr 根節(jié)點等于空

直接new a Node插入即可

if (_root == nullptr)
{
	_root = new Node(key);
	return true;
}

_root != nullptr 根節(jié)點不等于空

我們需要找到適合key值的空節(jié)點位置，通過搜索二叉樹的性質(zhì)進行排查位置

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

2）Find()

直接通過搜索二叉樹的性質(zhì)就可以進行查找，當key值大于cur->_key的值時，就查找cur的右子樹，key值小于cur->_key的值時，就查找cur的左子樹，直到找到，或者找不到cur == nullptr結(jié)束，即邏輯和Inser中的邏輯大同小異；

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

3）Erase()

刪除分三種情況：

刪除節(jié)點沒有孩子
刪除節(jié)點有一個孩子

有一個左孩子
有一個右孩子

刪除節(jié)點有兩個孩子

前面兩種代碼可以合并處理

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;
					cur = nullptr;
				}
				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;
						}
					}

					delete cur;
					cur = nullptr;
				}
				else
				{
					Node* minParent = cur;
					Node* min = cur->_right;
					while (min->_left)
					{
						minParent = min;
						min = min->_left;
					}

					swap(cur->_key, min->_key);

					if (minParent->_left == min)
					{
						minParent->_left = min->_right;
					}
					else
					{
						minParent->_right = min->_right;
					}

					delete min;
					min = nullptr;
				}

				return true;
			}
		}

		return false;
	}

4）InOder()

使用二叉樹的中序遍歷--midorder?traverse

特點：

中序遍歷后的值排列是有序的

void InOrder()
    {
		_InOrder(_root);
		return;
    }

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

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

5）BSTree(const BSTree& t) 拷貝構(gòu)造

使用前序遍歷構(gòu)造

BSTree(const BSTree& t)
	{
		_Copy(t._root);
	}

    Node* _Copy(Node* root) // 使用前序遍歷構(gòu)造
	{
		if (root == nullptr)
		{
			return;
		}

		Node* copyRoot = new Node(root->_key);
		copyRoot->_left = _Copy(root->_left);
		copyRoot->_left = _Copy(root->_right);
		return copyRoot;
	}

6）~BSTree()析構(gòu)函數(shù)

使用后序銷毀

~BSTree()
	{
		_Destory(_root);
	}

    void _Destory(Node* root) // 使用后序銷毀
	{
		if (root == nullptr)
		{
			return;
		}

		_Destory(root->_left);
		_Destory(root->_right);
		delete root;
		root = nullptr;
	}

四、手撕搜索二叉樹遞歸 1）InsertR()

bool InertR(const K& key)
	{
		return _InsertR(_root, key);
	}
    
    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;
		}
	}

2）FindR()

bool FindR(const K& key)
	{
		return _FindR(_root, key);
	}

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

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

3）EraseR()

bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}

    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
			{
				//找右數(shù)的最左節(jié)點
				Node* min = root->_right;
				while (min->_left)
				{
					min = min->_left;
				}

				swap(root->_key, min->_key);
				return _InserR(root->_right, key);
			}

			delete del;
			return true;
		}
	}

五、搜索二叉樹完整代碼

templatestruct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;
	K _key;

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

	}
};

templateclass BSTree
{
	typedef BSTreeNodeNode;
public:
	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		else
		{
			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;
			}
		}

	}

	void InOrder()
	{
		_InOrder(_root);
		return;
	}

	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
			{
				//開始刪除
				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;
					cur = nullptr;
				}
				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;
						}
					}

					delete cur;
					cur = nullptr;
				}
				else
				{
					Node* minParent = cur;
					Node* min = cur->_right;
					while (min->_left)
					{
						minparnt = min;
						min = min->_left;
					}

					swap(cur->_key, min->_key);

					if (minParent->_left == min)
					{
						minParent->_left = min->_right;
					}
					else
					{
						minParent->_right = min->_right;
					}

					delete min;
					min = nullptr;
				}

				return true;
			}
		}

		return false;
	}

	BSTree() = default;

	BSTree(const BSTree& t)
	{
		_Copy(t._root);
	}

	~BSTree()
	{
		_Destory(_root);
	}


//
	bool FindR(const K& key)
	{
		return _FindR(_root, key);
	}

	bool InertR(const K& key)
	{
		return _InsertR(_root, key);
	}

	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}


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

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

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

		Node* copyRoot = new Node(root->_key);
		copyRoot->_left = _Copy(root->_left);
		copyRoot->_left = _Copy(root->_right);
		return copyRoot;
	}

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

		if (root->_key< key)
		{
			return _FindR(root->_right);
		}
		else if (root->_key >key)
		{
			return _FindR(root->_left);
		}
		else
		{
			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 _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
			{
				//找右數(shù)的最左節(jié)點
				Node* min = root->_right;
				while (min->_left)
				{
					min = min->_left;
				}

				swap(root->_key, min->_key);
				return _InserR(root->_right, key);
			}

			delete del;
			return true;
		}
	}

private:
	Node* _root = nullptr;
};

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

當前文章：＜C++＞手撕搜索二叉樹-創(chuàng)新互聯(lián)
文章分享：http://bm7419.com/article40/ijdho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供電子商務(wù)、建站公司、ChatGPT、動態(tài)網(wǎng)站、微信小程序、外貿(mào)建站

聲明：本網(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)容