搜索二叉树

    二叉查找树（Binary Search Tree）,也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一颗空树或者具有下列性质的二叉树：

    （1）每个节点都有一个作为搜索依据的关键码（key），所有的节点的关键码互不相同。

    （2）左子树上所有的关键码（key）都小于根节点点的关键码（key）。

    （3）右子树上所有的关键码（key）都大于根节点的关键码（key）。

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

代码实现如下：

#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;
		//删除节点的左为空
		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;
		}
		//删除节点的右为空
		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;
		}
		//删除节点的左右都不为空
		else
		{	//找右树的最左节点，也就是右边最小的数
			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
		{
			//删除的节点的左为空
			if (root->_left == NULL)
			{
				root = root->_right;
			}
			//删除节点的右为空
			else if (root->_right == NULL)
			{
				root = root->_left;
			}
			else
			{		//找右边最左的节点（即右边最小的节点）替换删除的该节点（下面程序采用的）。
					//或者找左边最右的节点（即左边最大的节点）替换删除的该节点
				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 << "没有找到ret1" << endl;

	BSTreeNode<int, int>* 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<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 << "没有找到ret1" << endl;

	BSTreeNode<int, int>* ret2 = bst.Find(12);
	if (ret2)
	{
		cout << ret2->_key << ":" << ret2->_value << endl;
	}
	else
		cout << "没有找到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;
}

运行结果：