中文字幕日韩精品一区二区免费_精品一区二区三区国产精品无卡在_国精品无码专区一区二区三区_国产αv三级中文在线

搜索二叉樹(shù)

    二叉查找樹(shù)（Binary Search Tree）,也稱(chēng)有序二叉樹(shù)（ordered binary tree）,排序二叉樹(shù)（sorted binary tree），是指一顆空樹(shù)或者具有下列性質(zhì)的二叉樹(shù)：

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

    （1）每個(gè)節(jié)點(diǎn)都有一個(gè)作為搜索依據(jù)的關(guān)鍵碼（key），所有的節(jié)點(diǎn)的關(guān)鍵碼互不相同。

    （2）左子樹(shù)上所有的關(guān)鍵碼（key）都小于根節(jié)點(diǎn)點(diǎn)的關(guān)鍵碼（key）。

    （3）右子樹(shù)上所有的關(guān)鍵碼（key）都大于根節(jié)點(diǎn)的關(guān)鍵碼（key）。

    （4）左右子樹(shù)都是二叉搜索樹(shù)。

代碼實(shí)現(xiàn)如下：

#include<iostream>
using namespace std;

template<class K,class V>
struct BSTreeNode{
	BSTreeNode<K, V>* _left;
	BSTreeNode<K, V>* _right;
	K _key;
	V _value;
	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 (_root == NULL)
		{
			_root = new Node(key,value);
			return true;
		}
		Node* parent = _root;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		if (parent->_key>key)
		{
			parent->_left = new Node(key,value);
		}
		else
		{
			parent->_right = new Node(key, value);
		}
		return true;
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	Node* Find(const K& key)
	{
		if (_root == NULL)
		{
			return NULL;
		}
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}
		return NULL;
	}

	bool Remove(const K& key)
	{
		if (_root == NULL)
		{
			return false;
		}
		Node* parent = NULL;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
				break;
		}
		if (cur == NULL)
			return false;

		Node* del;
		//刪除節(jié)點(diǎn)的左為空
		if (cur->_left == NULL)
		{
			del = cur;
			if (parent == NULL)
			{
				_root = cur->_right;
			}
			else
			{
				if (parent->_left == cur)
				{
					parent->_left = cur->_right;
				}
				else
				{
					parent->_right = cur->_right;
				}
			}
			delete del;
		}
		//刪除節(jié)點(diǎn)的右為空
		else if (cur->_right == NULL)
		{
			del = cur;
			if (parent == NULL)
			{
				_root = cur->_left;
			}
			else
			{
				if (parent->_left == cur)
				{
					parent->_left = cur->_left;
				}
				else
				{
					parent->_right = cur->_left;
				}
			}
			delete del;
		}
		//刪除節(jié)點(diǎn)的左右都不為空
		else
		{	//找右樹(shù)的最左節(jié)點(diǎn)，也就是右邊最小的數(shù)
			parent = cur;
			Node* left = cur->_right;
			while (left->_left)
			{
				parent = left;
				left = left->_left;
			}
			del = left;

			cur->_key = left->_key;
			cur->_value = left->_value;

			if (parent->_left == left)
			{
				parent->_left = left->_right;
			}
			else
			{
				parent->_right = left->_right;
			}
			delete del;
		}
		return true;
	}

	//遞歸
	Node* FindR(const K& key)
	{
		return _FindR(_root,key);
	}
	bool InsertR(const K& key, const V& value)
	{
		return _InsertR(_root,key,value);
	}
	bool RemoveR(const K& key)
	{
		return _RemoveR(_root,key);
	}
protected:
	void _InOrder(Node* root)
	{
		if (root != NULL)
		{
			_InOrder(root->_left);
			cout << root->_key << " ";
			_InOrder(root->_right);
		}
	}
	Node* _FindR(Node* root,const K& key)
	{
		if (root == NULL)
		{
			return NULL;
		}
		if (root->_key == key)
		{
			return root;
		}
		if (root->_key > key)
		{
			return _FindR(root->_left,key);
		}
		else
		{
			return _FindR(root->_right,key);
		}
		return NULL;
	}
	bool _InsertR(Node*& root, const K& key, const V& value)
	{
		if (root == NULL)
		{
			root = new Node(key,value);
			return true;
		}
		if (root->_key > key)
		{
			return _InsertR(root->_left,key,value);
		}
		else
		{
			return _InsertR(root->_right,key,value);
		}
		return false;
	}
	bool _RemoveR(Node*& root, const K& key)
	{
		if (root == NULL)
		{
			return false;
		}
		if (root->_key > key)
		{
			return _RemoveR(root->_left,key);
		}
		else if (root->_key < key)
		{
			return _RemoveR(root->_right,key);
		}
		else
		{
			//刪除的節(jié)點(diǎn)的左為空
			if (root->_left == NULL)
			{
				root = root->_right;
			}
			//刪除節(jié)點(diǎn)的右為空
			else if (root->_right == NULL)
			{
				root = root->_left;
			}
			else
			{		//找右邊最左的節(jié)點(diǎn)（即右邊最小的節(jié)點(diǎn)）替換刪除的該節(jié)點(diǎn)（下面程序采用的）。
					//或者找左邊最右的節(jié)點(diǎn)（即左邊最大的節(jié)點(diǎn)）替換刪除的該節(jié)點(diǎn)
				Node* parent = root;
				Node* left = root->_right;
				while (left->_left)
				{
					parent = left;
					left = left->_left;
				}
				root->_key = left->_key;
				root->_value = left->_value;
				if (parent->_left == left)
				{
					parent->_left = left->_right;
				}
				else
				{
					parent->_right = left->_right;
				}
			}
			return true;
		}
		return false;
	}
protected:
	Node* _root;
};


#include "BSTree.h"

void Test1()
{
	int arr[10] = { 0, 1, 3, 5, 4, 2, 7, 8, 6, 9};
	BSTree<int, int> bst;
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i)
	{
		bst.Insert(arr[i],i);
	}
	bst.InOrder();
	BSTreeNode<int, int>* ret1=bst.Find(8);
	if (ret1)
	{
		cout << ret1->_key << ":" << ret1->_value << endl;
	}
	else
		cout << "沒(méi)有找到ret1" << endl;

	BSTreeNode<int, int>* ret2=bst.Find(22);
	if (ret2)
	{
		cout << ret2->_key << ":" << ret2->_value << endl;
	}
	else
		cout << "沒(méi)有找到ret2" << endl;

	bst.Remove(9);
	bst.Remove(7);
	bst.Remove(8);
	bst.InOrder();

	bst.Remove(0);
	bst.Remove(1);
	bst.Remove(2);
	bst.Remove(3);
	bst.Remove(4);
	bst.Remove(5);
	bst.Remove(6);
	bst.Remove(7);
	bst.Remove(8);
	bst.Remove(9);
	bst.InOrder();

}
void Test2()
{
	int arr[10] = { 0, 1, 3, 5, 4, 2, 7, 8, 6, 9 };
	BSTree<int, int> bst;
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i)
	{
		bst.InsertR(arr[i], i);
	}
	bst.InOrder();

	BSTreeNode<int, int>* ret1 = bst.Find(7);
	if (ret1)
	{
		cout << ret1->_key << ":" << ret1->_value << endl;
	}
	else
		cout << "沒(méi)有找到ret1" << endl;

	BSTreeNode<int, int>* ret2 = bst.Find(12);
	if (ret2)
	{
		cout << ret2->_key << ":" << ret2->_value << endl;
	}
	else
		cout << "沒(méi)有找到ret2" << endl;
	
	bst.RemoveR(8);
	bst.RemoveR(7);
	cout<<bst.RemoveR(9)<<endl;
	bst.InOrder();

	bst.RemoveR(0);
	bst.RemoveR(1);
	cout << bst.RemoveR(2) << endl;
	bst.RemoveR(3);
	bst.RemoveR(4);
	bst.RemoveR(5);
	bst.RemoveR(6);
	bst.RemoveR(7);
	cout << bst.RemoveR(8) << endl;
	bst.RemoveR(9);
	bst.InOrder();

}
int main()
{
	Test1();
	Test2();
	return 0;
}

運(yùn)行結(jié)果：

搜索二叉樹(shù)

分享名稱(chēng)：搜索二叉樹(shù)
URL鏈接：http://www.rwnh.cn/article6/gpocig.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)網(wǎng)站建設(shè)、軟件開(kāi)發(fā)、搜索引擎優(yōu)化、品牌網(wǎng)站制作、自適應(yīng)網(wǎng)站、定制網(wǎng)站

廣告

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

外貿(mào)網(wǎng)站建設(shè)
离岛区| 和顺县| 佛冈县| 旬阳县| 灵璧县| 华宁县| 苏尼特右旗| 久治县| 湟源县| 准格尔旗| 大城县| 古浪县| 旬阳县| 阳曲县| 荣昌县| 阳东县| 邛崃市| 石阡县| 灵武市| 长宁县| 文水县| 广灵县| 遂昌县| 沭阳县| 洞口县| 徐州市| 吕梁市| 隆化县| 铁力市| 曲麻莱县| 吴江市| 永德县| 巴青县| 丰都县| 枣强县| 邵武市| 锦州市| 明水县| 阿尔山市| 中山市| 新余市|