真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

成都創(chuàng)新互聯(lián)網(wǎng)站制作重慶分公司

搜索二叉樹及其實(shí)現(xiàn)(迭代和遞歸實(shí)現(xiàn))-創(chuàng)新互聯(lián)

二叉搜索樹

二叉樹搜索樹又叫二叉排序樹,它還有可能為一個(gè)空樹。搜索二叉樹的性質(zhì)有

目前創(chuàng)新互聯(lián)已為數(shù)千家的企業(yè)提供了網(wǎng)站建設(shè)、域名、虛擬空間、網(wǎng)站托管維護(hù)、企業(yè)網(wǎng)站設(shè)計(jì)、太和網(wǎng)站維護(hù)等服務(wù),公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略,正道將秉承"和諧、參與、激情"的文化,與客戶和合作伙伴齊心協(xié)力一起成長(zhǎng),共同發(fā)展。
  1. 若他的左子樹不為空,則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)。
  2. 若他的右子樹不為空,則右子樹上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)。
  3. 他的左右子樹均為二叉搜索樹
    在這里插入圖片描述
迭代實(shí)現(xiàn)
templatestruct BSTreeNode
{BSTreeNode* _left;
	BSTreeNode* _right;
	k _key;

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

templatestruct BSTree
{typedef BSTreeNodeNode;
public:
	BSTree()
		:_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->_left = cur;
		}
		else
		{	parent->_right = cur;
		}
		return true;
	}

	bool Find(const k& key)
	{if (_root == nullptr)
		{	return false;
		}
		Node* cur = _root;
		while (cur)
		{	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* pertent = nullptr;
		Node* cur = _root;
	    //先找到要?jiǎng)h除的
		while (cur)
		{	if (cur->_key >key)
			{		pertent = cur;
				cur = cur->_left;
			}
			else if (cur->_key< key)
			{		pertent = cur;
				cur = cur->_right;
			}
			//找到了
			else
			{		//開始刪除
				//左為空,托孤右
				if (cur->_left == nullptr)
				{if (pertent == nullptr)
					{_root = cur->_right;
					}
					else
					{if (pertent->_left == cur)
						{	pertent->left = cur->_right;
						}
						else
						{	pertent->_right = cur->_right
						}
					}

					delete cur;
				}
				//右為空,托孤左
				else if (cur->_right == nullptr)
				{if (pertent == nullptr)
					{_root->_left;
					}
					else
					{if (pertent->_left == cur)
						{	pertent->left = cur->_left;
						}
						else
						{	pertent->_right = cur->_left;
						}
					}
					delete cur;
				}
				//左右均不為空,替換法刪除
				else
				{//左子樹的最右節(jié)點(diǎn)
					Node* minpertent = cur;
					Node* min = cur->_left;
					while (min->right)
					{minpertent = min;
						min = min->_right;
					}
					cur->_key = min->_key;//交換
					if (minpertent->_left == min)
					{minpertent->_left = min->_left;
					}
					else
					{minpertent->_right = min->_left;
					}
					delete min;
				}
			}
		}

		return false;
	}


	void Inorder()
	{_Inorder(_root);
	}
	void _Inorder(Node* root)
	{if (root == nullptr)
		{	return;
		}
		_Inorder(root->_left);
		cout<< root->_key<< " ";
		_Inorder(root->_right);
	}
private:
	Node* _root;
};
插入

要是插入key比這個(gè)根要大,那么就去根的右樹,比根要小,那么就去左樹。直到找到一個(gè)空位置。

查找

要是查找key比這個(gè)根要大,那么就去根的右樹,比根要小,那么就去左樹。直到找到,要是找不到就沒有這個(gè)值。

刪除

這里的刪除才是最難的,在刪除的時(shí)候我們可以大概分為三種方式

  1. 刪除沒有孩子的節(jié)點(diǎn)。
  2. 刪除只有一個(gè)孩子的節(jié)點(diǎn)。
  3. 刪除有兩個(gè)孩子的節(jié)點(diǎn)。
    對(duì)于第一第二種情況,我們可以采用直接刪除法,要是沒有孩子就直接釋放掉要?jiǎng)h的節(jié)點(diǎn),要是有一個(gè)孩子我們直接將孩子托孤給該節(jié)點(diǎn)的父親,再釋放掉該節(jié)點(diǎn)。
    對(duì)于有兩個(gè)孩子的節(jié)點(diǎn),我們采用替換法刪除,就是將要?jiǎng)h除的節(jié)點(diǎn)和左邊大右邊最小的葉子節(jié)點(diǎn)進(jìn)行替換之后然后刪除葉子節(jié)點(diǎn)。
遞歸實(shí)現(xiàn)
templatestruct BSTreeNode
{BSTreeNode* _left;
	BSTreeNode* _right;
	k _key;


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

templatestruct BSTree
{typedef BSTreeNodeNode;
public:
	bool InsertR(const K& key)
	{return _InsertR(_root, key);
	}

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

	Node* EraseR(const K& key)
	{return _EraseR(_root, key);
	}
private:
	bool _InsertR(Node*& root, const K& key)
	{if (root == nullptr)
		{	root = new Node(key);
			return true;
		}
		if (root->_key >key)
		{	_InsertR(root->_left, key);
		}
		if (root->_key< key)
		{	_InsertR(root->_right, key);
		}
		return false;
	}
	Node* _FindR(Node* root, const K& key)
	{if (root == nullptr)
		{	return nullptr;
		}
		if (root->_key >key)
		{	_FindR(root->_left, key);
		}
		else if (root->_key< key)
		{	_FindR(root->_right, key);
		}
		else
		{	return root;
		}
	}
	bool _EraseR(Node*& root, const K& key)
	{if (root == nullptr)
		{	return false;
		}
		if (root->_key >key)
		{	_EraseR(root->_left, key);
		}
		else if(root->_key< key)
		{	_EraseR(root->_right, key);
		}
		else
		{	Node* del = root;
			if (root->_left == nullptr)
			{		root = root->_right;
			}
			else if (root->_right == nullptr)
			{		root = root->_left;
			}
			else
			{		Node* min = root->_right;
				while (min->_left)
				{min = min->_left;
				}

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

				// 遞歸到右子樹去刪除
				return _EraseR(root->_right, key);
			}
		}
		delete min;
		return true;
	}

private:
	Node* _root;
};

雖然遞歸刪除查找插入比較簡(jiǎn)單,但是僅僅在代碼量上,要是深度太深時(shí)候還是迭代比較好,不然棧幀就要爆了。

你是否還在尋找穩(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)查看詳情吧


當(dāng)前文章:搜索二叉樹及其實(shí)現(xiàn)(迭代和遞歸實(shí)現(xiàn))-創(chuàng)新互聯(lián)
網(wǎng)頁(yè)地址:http://weahome.cn/article/ddccod.html

其他資訊

在線咨詢

微信咨詢

電話咨詢

028-86922220(工作日)

18980820575(7×24)

提交需求

返回頂部