二叉树进阶之二叉搜索树

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

template<class K>
struct BSTreeNode
{
	BSTreeNode<K> _left;
	BSTreeNode<K> _right;
	K _key;
	BSTreeNode(const K& key)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
	{}
};

bool Insert(const K& key)
{
	//空树时直接令根节点为插入节点的_key为key
	if (_root == nullptr)
	{
		_root = new Node(key);
		return true;
	}
	//否则就需要向下找合适的地方
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		//最后parent这个节点就是需要插入节点的父节点
		parent = cur;
		//如果cur的_key小于key，那么cur就向他的右子树向下查找
		if (cur->_key < key)
		{
			cur = cur->_right;
		}
		//向左子树向下查找
		if (cur->_key > key)
		{
			cur = cur->_left;
		}
		//如果相等就不能插入，返回false
		else
		{
			return false;
		}
	}
	//将cur节点填入key，如果parent父节点的值小于key，则将cur放在parent的右边，大于则反之
	cur = new Node(key);
	if (parent->_key < key)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	//最后记得返回true
	return true;
}

bool Find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		if (cur->_key > key)
		{
			cur = cur->_left;
		}
		if (cur->_key < key)
		{
			cur = cur->_right;
		}
		//相等就返回true
		else
		{
			return true;
		}
	}
	return false;
}

//左为空
if (cur->_left == nullptr)
{
				if (cur == _root)
				{
					_root = cur->_right;
				}
				else
				{
					if (cur == parent->_left)
					{
						parent->_left = cur->_right;
					}
					else
					{
						parent->_right = cur->_right;
					}
				}
				delete cur;
}

//右为空
else if (cur->_right == nullptr)
{
				if (cur == _root)
				{
					_root = cur->_left;
				}
				else
				{
					if (cur == parent->_left)
					{
						parent->_left = cur->_left;
					}
					else
					{
						parent->_right = cur->_left;
					}
				}
				delete cur;
}

//左右都不为空
else
{
				//寻找右子树的最小节点（也就是左子树的最左一个节点）
				Node* parent = cur;
				Node* subLeft = cur->_right;
				//subLeft再遍历完成后就是右子树的最小节点
				while (subLeft->_left)
				{
					parent = subLeft;
					subLeft = subLeft->_left;
				}
				//cur就是你要删除的节点，将subleft的_key和cur的_key交换
				swap(cur->_key, subLeft->_key);
				//将subLeft的右节点直接链接到parent
				if (subLeft == parent->_left)
				{
					parent->_left = subLeft->_right;
				}
				else
				{
					parent->_right = subLeft->_right;
				}
				//最后删除subleft，替代删除了原本cur内的_key
				delete subLeft;
}

bool Erase(const K& key)
{
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		//找_key为key的节点
		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)
				{
					_root = cur->_right;
				}
				else
				{
					if (cur == parent->_left)
					{
						parent->_left = cur->_right;
					}
					else
					{
						parent->_right = cur->_right;
					}
				}
				delete cur;
			}
			//右为空
			else if (cur->_right == nullptr)
			{
				if (cur == _root)
				{
					_root = cur->_left;
				}
				else
				{
					if (cur == parent->_left)
					{
						parent->_left = cur->_left;
					}
					else
					{
						parent->_right = cur->_left;
					}
				}
				delete cur;
			}
			//左右都不为空
			else
			{
				//寻找右子树的最小节点（也就是左子树的最左一个节点）
				Node* parent = cur;
				Node* subLeft = cur->_right;
				//subLeft再遍历完成后就是右子树的最小节点
				while (subLeft->_left)
				{
					parent = subLeft;
					subLeft = subLeft->_left;
				}
				//cur就是你要删除的节点，将subleft的_key和cur的_key交换
				swap(cur->_key, subLeft->_key);
				//将subLeft的右节点直接链接到parent
				if (subLeft == parent->_left)
				{
					parent->_left = subLeft->_right;
				}
				else
				{
					parent->_right = subLeft->_right;
				}
				//最后删除subleft，替代删除了原本cur内的_key
				delete subLeft;
			}
			return true;
		}
	}
	return false;
}

// 改造二叉搜索树为KV结构
template<class K, class V>
struct BSTNode
{
	BSTNode(const K& key = K(), const V& value = V())
		: _pLeft(nullptr), _pRight(nullptr), _key(key), _Value(value)
	{}
	BSTNode<T>* _pLeft;
	BSTNode<T>* _pRight;
	K _key;
	V _value
};
template<class K, class V>
class BSTree
{
	typedef BSTNode<K, V> Node;
	typedef Node* PNode;
public:
	BSTree() : _pRoot(nullptr) {}
	PNode Find(const K& key);
	bool Insert(const K& key, const V& value)
		bool Erase(const K& key)
private:
	PNode _pRoot;
};
void TestBSTree3()
{
	// 输入单词，查找单词对应的中文翻译
	BSTree<string, string> dict;
	dict.Insert("string", "字符串");
	dict.Insert("tree", "树");
	dict.Insert("left", "左边、剩余");
	dict.Insert("right", "右边");
	dict.Insert("sort", "排序");
	// 插入词库中所有单词
	string str;
	while (cin >> str)
	{
		BSTreeNode<string, string>* ret = dict.Find(str);
		if (ret == nullptr)
		{
			cout << "单词拼写错误，词库中没有这个单词:" << str << endl;
		}
		else
		{
			cout << str << "中文翻译:" << ret->_value << endl;
		}
	}
}
void TestBSTree4()
{
	// 统计水果出现的次数
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
   "苹果", "香蕉", "苹果", "香蕉" };
	BSTree<string, int> countTree;
	for (const auto& str : arr)
	{
		// 先查找水果在不在搜索树中
		// 1、不在，说明水果第一次出现，则插入<水果, 1>
		// 2、在，则查找到的节点中水果对应的次数++
		//BSTreeNode<string, int>* ret = countTree.Find(str);
		auto ret = countTree.Find(str);
		if (ret == NULL)
		{
			countTree.Insert(str, 1);
		}
		else
		{
			ret->_value++;
		}
	}
	countTree.InOrder();
}