数据结构进阶：二叉搜索树

1、二叉搜索树的实现

        二叉搜索树的拥有很快的查找速度，查找的效率为O（logN)，也就是说如果把全国的人放到二叉搜索树中，最多只需要31次就可以 找到你，这是一种很快的搜索方式，他还有两种模型一种是key模型，还有是key/value模型接下来我将一步一步的带你实现二叉搜索树，以key/value为例，首先是他的结点

	template<class K, class V>
	struct BSTreeNode
	{
		BSTreeNode<K, V>* _left;
		BSTreeNode<K, V>* _right;
		K _key;
		V _value;
		BSTreeNode(const K& n, const V& v)
			:_key(n)
			, _left(nullptr)
			, _right(nullptr)
			, _value(v)
		{}
	};

先把结点定义好，在写插入函数 （注意事项已经写进代码了）

	template<class K, class V>
	class BSTree//Binary Search Tree
	{
		typedef BSTreeNode<K, V> Node;//这里只在内部typedef是怕与外面混淆
	public:
		bool Insert(const K& key, const V& value)
		{
			if (_root == nullptr)//如果二叉树没有创建根节点就创建
			{
				_root = new Node(key, value);
				return true;
			}
			Node* cur = _root;
			Node* parent = nullptr;
			int flag = 0;
            //去找空结点找到就插入，找到相同的就返回
			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
					flag = 1;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
					flag = 0;
				}
				else
				{
					return false;
				}
			}
			cur = new Node(key, value);
			if (flag == 1)//这里是确定标志位，看看要插入的是左节点还是右节点
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			return true;
		}

实现了插入函数以后就是查找函数， 查找函数就是通过key值来查找value

		Node* Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)
					cur = cur->_right;
				else if (cur->_key > key)
					cur = cur->_left;
				else
					return cur;
			}
			return nullptr;
		}

 最难的就是删除了，删除需要注意三个地方，如果左子树为空、如果右子树为空和如果左右子树都不为空。（很抽象，一定要画图！！！）

		bool Erase(const K& key)
		{
			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
				{
					//左边是空结点
					if (cur->_left == nullptr)
					{
						if (cur == _root)//避免parent为nullptr
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_right == cur)
								parent->_right = cur->_right;
							else
								parent->_left = cur->_right;
						}
						delete cur;
						return true;

					}
					else if (cur->_right == nullptr)
					{
						if (cur == _root)//避免parent为nullptr
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_right == cur)
								parent->_right = cur->_left;
							else
								parent->_left = cur->_left;
						}
						delete cur;
						return true;

					}
					else//两边都不为空结点
					{
						Node* rightmin = cur->_right;
						Node* rightminparent = cur;
						while (rightmin->_left)
						{
							rightminparent = rightmin;
							rightmin = rightmin->_left;
						}
						cur->_key = rightmin->_key;
						if (rightminparent->_right == rightmin)
							rightminparent->_right = rightmin->_right;
						else
							rightminparent->_left = rightmin->_right;
						delete rightmin;
						return true;
					}
				}
			}
			return false;
		}

2、二叉搜索树的使用

这里贴一个示例代码

	void test()
	{
		BSTree<string, string> b;
		b.Insert("string", "字符串");
		b.Insert("sort", "排序");
		b.Insert("insert", "插入");
		b.Insert("tree", "树");

		//string str;
		//while (cin >> str)
		//{
		//	BSTreeNode<string, string>*ret = b.Find(str);
		//	if (ret)
		//	{
		//		cout << ret->_value << endl;
		//	}
		//	else
		//	{
		//		cout << "无此单词"<<endl;
		//	}
		//}
		string strArr[] = { "西瓜","西瓜" ,"香蕉","西瓜" ,"西瓜" ,"香蕉","西瓜" ,"西瓜" ,"蜜瓜" ,"西瓜" ,"西瓜","西瓜","西瓜","西瓜","香蕉","香蕉" ,"香蕉" ,"香蕉" };
		BSTree<string,int> countTree;
		for (auto str : strArr)
		{
			BSTreeNode<string, int>* ret = countTree.Find(str);
			if (ret == nullptr)
			{
				countTree.Insert(str, 1);
			}
			else
			{
				ret->_value++;
			}
		}
		countTree.InOrder();
	}

去试试吧