二叉搜索树（相关函数实现）

1.节点结构

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

	BSNode(K key,V value)
		:_key(key)
		,_value(value)
		, _left(nullptr)
		, _right(nullptr)
	{}
};

二叉树_left,_value分别指向自己的左右孩子。根据_key大小判断新节点放到左边还是右边。

_value非必须，用来存对应的相关信息。

2.查找

template<class K,class V>
class BSTree
{
	typedef BSNode<K,V> Node;
public:
	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 nullptr;
	}
private:
	Node* _root = nullptr;
};

key>_key就去左子树找，key<_key就去右子树找，找到返回对应节点。

3.插入

bool Insert(const K& key,const V& value)
{
	if (_root == nullptr)
	{
		_root = new Node(key,value);
		return true;
	}
	Node* PNode = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (key > cur->_key)
		{
			PNode = cur;
			cur = cur->_right;
		}
		else if (key < cur->_key)
		{
			PNode = cur;
			cur = cur->_left;
		}
		else return false;
	}
	cur = new Node(key,value);
	if (cur->_key > PNode->_key) PNode->_right = cur;
	else PNode->_left = cur;
	return true;
}

和查找类似，找对应位置的空节点，如果在这之前找到key相等的节点就返回false。

如果根节点为空，就直接插入。（防止PNode->_key出现空指针访问）

4.删除

	bool Erase(const K& key)
	{
		if (_root == nullptr) return false;
		Node* PNode = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (key > cur->_key)
			{
				PNode = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key)
			{
				PNode = cur;
				cur = cur->_left;
			}
			//找到要删节点cur
			else
			{
				//cur只有1or0个孩子
                //1.左孩子不存在
				if (cur->_left == nullptr)
				{
					if (cur == _root)
						_root = _root->_right;
					else
					{
						if (PNode->_left == cur)
							PNode->_left = cur->_right;
						else // (PNode->_right == cur)
							PNode->_right = cur->_right;
					}
					delete cur;
					return true;
				}
                //2.右孩子不存在
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
						_root = _root->_left;
					else
					{
						if (PNode->_left == cur)
							PNode->_left = cur->_left;
						else // (PNode->_right == cur)
							PNode->_right = cur->_left;
					}
					delete cur;
					return true;
				}
				//cur有两个孩子 
				else
				{
					Node* rightP = cur;
					Node* rightMin = cur->_right;
					//找右子树最左边节点（右子树最小值）
					while (rightMin->_left)
					{
						rightP = rightMin;
						rightMin = rightMin->_left;
					}
					//被删除节点值 和 右子树最小值交换
					cur->_key = rightMin->_key;
                    //父母节点继承它剩余孩子
					if (rightP->_left == rightMin)
					{
						rightP->_left = rightMin->_right;
					}
					   //while循环一次也没进入，被删除节点的右子树跟节点就是最小值
					else // (rightP->_right == rightMin)
					{
						rightP->_right = rightMin->_right;
					}
					delete rightMin;
					return true;
				}
			}
		}
		return false;
	}

删除节点分为两种情况，1.被删除节点有0/1个孩子，2.有2个孩子。

1.有0/1个孩子，它是右孩子那么剩余孩子就连在父母节点的右边，反之左边。

如果被删除节点是左孩子，那么它的孩子不管是右还是左孩子都比被删除节点的父母节点值小，所以剩余节点连在父母节点PNode的左边。反之右边。

（如果被删除的是根节点，它是没有父母节点的，删除根节点后就让剩余子树的第一个孩子当根节点（最值））

2.有2个孩子，那么我们可以让左子树的最右节点（左子树最大值）或者右子树的最左节点（右子树最小值）代替被删节点，此时仍满足左子树值都小于根节点，右子树值都大于根节点。

假设我们找右子树的最左节点（右子树最小值），我们找到最左节点是没有左孩子的，如果它有右孩子，那么是连在父母节点的左边还是右？

同理，这就需要看它是父母节点的左孩子还是右孩子，如果被删除节点右子树根节点没有左孩子那么根节点就是最小值，位于父母节点右边。如果有左孩子，那么至少进入一次while循环，位于父母节点左边。

5.中序遍历

public:
void InOrder ()
{
	_InOrder(_root);
	cout << endl;
}
private:
void _InOrder(Node* root)
{
	if (root == nullptr) return;
	_InOrder(root->_left);
	cout << root->_key << "->"<<root->_value<<' ';
	_InOrder(root->_right);
}

因为在类外不能访问根节点,也就不能进行传参，因此需要包一层函数间接调用。

key/value二叉树可以用来解决像查找英文单词对应的汉语。

void TestBSTree()
{
	BSTree<string, string> dict;
	dict.Insert("insert", "插入");
	dict.Insert("erase", "删除");
	dict.Insert("left", "左边");
	dict.Insert("string", "字符串");
	string str;
	while (cin >> str)
	{
		auto cur = dict.Find(str);
		if (cur == nullptr) cout << "no" << endl;
		else cout <<cur->_key<<':' << cur->_value << endl;
	}
}

判断出现次数

void TestBSTree2()
{
	string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };
	BSTree<string, int> count;
	for (auto& str : strs)
	{
		auto cur = count.Find(str);
		if (cur == nullptr)
		{
			count.Insert(str, 1);
		}
		else cur->_value++;
	}
	count.InOrder();
}