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

成都創(chuàng)新互聯(lián)公司服務(wù)項(xiàng)目包括綏棱網(wǎng)站建設(shè)、綏棱網(wǎng)站制作、綏棱網(wǎng)頁制作以及綏棱網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，綏棱網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到綏棱省份的部分城市，未來相信會繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

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

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

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

    （4）左右子樹都是二叉搜索樹。

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

#include
using namespace std;

template
struct BSTreeNode{
	BSTreeNode* _left;
	BSTreeNode* _right;
	K _key;
	V _value;
	BSTreeNode(const K& key,const V& value)
		:_key(key)
		, _value(value)
		, _left(NULL)
		, _right(NULL)
	{}
};
template
class BSTree{
	typedef BSTreeNode 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
		{	//找右樹的最左節(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 bst;
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i)
	{
		bst.Insert(arr[i],i);
	}
	bst.InOrder();
	BSTreeNode* ret1=bst.Find(8);
	if (ret1)
	{
		cout << ret1->_key << ":" << ret1->_value << endl;
	}
	else
		cout << "沒有找到ret1" << endl;

	BSTreeNode* ret2=bst.Find(22);
	if (ret2)
	{
		cout << ret2->_key << ":" << ret2->_value << endl;
	}
	else
		cout << "沒有找到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 bst;
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i)
	{
		bst.InsertR(arr[i], i);
	}
	bst.InOrder();

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

	BSTreeNode* ret2 = bst.Find(12);
	if (ret2)
	{
		cout << ret2->_key << ":" << ret2->_value << endl;
	}
	else
		cout << "沒有找到ret2" << endl;
	
	bst.RemoveR(8);
	bst.RemoveR(7);
	cout<
運(yùn)行結(jié)果：
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
            

            當(dāng)前題目：搜索二叉樹-創(chuàng)新互聯(lián)            

            瀏覽地址：http://weahome.cn/article/dcioej.html