本篇內(nèi)容介紹了“C++中如何實(shí)現(xiàn)搜索二叉樹”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

成都創(chuàng)新互聯(lián)專注于襄汾網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠(chéng)為您提供襄汾營(yíng)銷型網(wǎng)站建設(shè)，襄汾網(wǎng)站制作、襄汾網(wǎng)頁(yè)設(shè)計(jì)、襄汾網(wǎng)站官網(wǎng)定制、成都微信小程序服務(wù)，打造襄汾網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供襄汾網(wǎng)站排名全網(wǎng)營(yíng)銷落地服務(wù)。

    二叉查找樹（英語(yǔ)：Binary Search Tree），也稱二叉搜索樹、有序二叉樹（英語(yǔ)：ordered binary tree），排序二叉樹（英語(yǔ)：sorted binary tree），是指一棵空樹或者具有下列性質(zhì)的二叉樹：

• 任意節(jié)點(diǎn)的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；

• 任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；

• 任意節(jié)點(diǎn)的左、右子樹也分別為二叉查找樹；

• 沒有鍵值相等的節(jié)點(diǎn)。

#pragma once

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

	BSTreeNode(const K& key, const V& value)
		:_key(key)
		,_value(value)
		,_left(NULL)
		,_right(NULL)
	{}
};

template<class K, class V>
class BSTree
{
	typedef BSTreeNode<K, V> Node;
public:
	BSTree()
		:_root(NULL)
	{}

	bool Insert(const K& key, const V& value)
	{
		if (NULL == _root)//若為空樹
		{
			_root = new Node(key, value);
			return true;
		}

		Node* parent = NULL;
		Node* cur = _root;

		//確定插入節(jié)點(diǎn)的位置
		while (cur)
		{
			if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else//已經(jīng)存在key
			{
				return false;
			}
		}

		//插入節(jié)點(diǎn)
		if (key > parent->_key)
			parent->_right = new Node(key, value);
		else
			parent->_left = new Node(key, value);
	}

	//Insert遞歸寫法
	bool InsertR(const K& key, const V& value)
	{
		return _InsertR(_root, key, value);
	}

	bool _InsertR(Node*& root, const K& key, const V& value)
	{
		if (NULL == root)
		{
			root = new Node(key, value);
			return true;
		}

		if (key > root->_key)
			return _InsertR(root->_right, key, value);
		else if (key < root->_key)
			return _InsertR(root->_left, key, value);
		else
			return false;
	}

	Node* Find(const K& key)
	{
		Node* cur = _root;

		while (cur)
		{
			if (key > cur->_key)
				cur = cur->_right;
			else if (key < cur->_key)
				cur = cur->_left;
			else
				return cur;
		}

		return NULL;
	}

	//Find遞歸寫法
	Node* FindR(const K& key)
	{
		return _FindR(_root, key);
	}

	Node* _FindR(Node* root, const K& key)
	{
		if (NULL == root)
			return NULL;

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

	bool Remove(const K& key)
	{
		Node* parent = NULL;
		Node* cur = _root;

		//確定刪除節(jié)點(diǎn)的位置
		while (cur)
		{
			if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				break;
			}
		}

		if (NULL == cur)//沒有該節(jié)點(diǎn)
		{
			return false;
		}

		Node* del;
		if (NULL == cur->_left)//刪除節(jié)點(diǎn)的左孩子為空
		{
			del = cur;

			//刪除的節(jié)點(diǎn)為根節(jié)點(diǎn)
			if (NULL == parent)
			{
				_root = _root->_right;
			}
			else
			{
				if (cur == parent->_left)
					parent->_left = cur->_right;
				else
					parent->_right = cur->_right;
			}
		}
		else if (NULL == cur->_right)//刪除節(jié)點(diǎn)的右孩子為空
		{
			del = cur;

			if (NULL == parent)
			{
				_root = _root->_left;
			}
			else
			{
				if (cur == parent->_left)
					parent->_left = cur->_right;
				else
					parent->_right = cur->_left;
			}
		}
		else//刪除節(jié)點(diǎn)的左右孩子都不為空，找右子樹最左節(jié)點(diǎn)代替該節(jié)點(diǎn)刪除
		{
			parent = cur;

			Node* leftmost = cur->_right;
			while (leftmost->_left)
			{
				parent = leftmost;
				leftmost = leftmost->_left;
			}

			del = leftmost;

			cur->_key = leftmost->_key;
			cur->_value = leftmost->_value;

			if (leftmost == parent->_left)
				parent->_left = leftmost->_right;
			else
				parent->_right = leftmost->_right;
		}

		return true;
	}

	//Remove遞歸寫法
	bool RemoveR(const K& key)
	{
		return _RemoveR(_root, key);
	}
	
	bool _RemoveR(Node*& root, const K& key)
	{
		if (NULL == root)
			return false;
		
		if (key > root->_key)
		{
			return _RemoveR(root->_right, key);
		}
		else if (key < root->_key)
		{
			return _RemoveR(root->_left, key);
		}
		else
		{
			Node* del = root;

			if (NULL == root->_left)
			{
				root = root->_right;
			}
			else if (NULL == root->_right)
			{
				root = root->_left;
			}
			else
			{
				Node* leftmost = root->_right;
				while (leftmost->_left)
				{
					leftmost = leftmost->_left;
				}

				swap(root->_key, leftmost->_key);
				swap(root->_value, leftmost->_value);

				return _RemoveR(root->_right, key);
			}

			delete del;
		}

		return true;
	}

	//中序遍歷遞歸寫法
	void InOrder()
	{
		_InOrder(_root);
	}

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

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

protected:
	Node* _root;
};


void Test()
{
	BSTree<int, int> t;
	int a[] = {5, 3, 4, 1, 7, 8, 2, 6, 0, 9};
	for (size_t i = 0; i < sizeof(a)/sizeof(a[0]);++i)
	{
		t.InsertR(a[i], i);
	}

	cout<<t.FindR(8)->_key<<endl;
	cout<<t.FindR(5)->_key<<endl;
	cout<<t.FindR(9)->_key<<endl;

	t.RemoveR(8);
	t.RemoveR(7);
	t.RemoveR(9);
	t.RemoveR(6);
	t.RemoveR(5);
	t.RemoveR(3);
	t.RemoveR(1);
	t.RemoveR(4);
	t.RemoveR(0);
	t.RemoveR(2);

	t.InOrder();
}

“C++中如何實(shí)現(xiàn)搜索二叉樹”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！

分享標(biāo)題：C++中如何實(shí)現(xiàn)搜索二叉樹-創(chuàng)新互聯(lián)
標(biāo)題來(lái)源：http://m.rwnh.cn/article20/dsdjco.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供移動(dòng)網(wǎng)站建設(shè)、標(biāo)簽優(yōu)化、App開發(fā)、做網(wǎng)站、搜索引擎優(yōu)化、虛擬主機(jī)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(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)