【C++】二叉搜索树

template <class K>
struct TreeNode
{
	TreeNode(const K& val)
		:_key(val)
		, _left(nullptr)
		, _right(nullptr)
	{}

	K _key;
	TreeNode<K>* _left;
	TreeNode<K>* _right;
};

bool Insert(const K& val)
{
	if (_root == nullptr)
	{
		_root = new Node(val);
		return true;
	}

	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (val > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (val < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
			return false;
	}

	// cur = new Node(val);//让局部指针cur指向新开辟结点有什么用？对搜索树一点影响都没有，你需要改变搜索树的链接关系。
	if (val > parent->_key)
		parent->_right = new Node(val);
	else
		parent->_left = new Node(val);
	return true;
}

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

bool Erase(const K& val)
{
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (val > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (val < cur->_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* minParent = cur;//minParent如果是nullptr，则当cur->_right是最小结点时，会发生空指针访问
				Node* minRight = cur->_right;//找右子树最小结点 或者 左子树最大结点
				while (minRight->_left)
				{
					minParent = minRight;
					minRight = minRight->_left;
				}
				swap(cur->_key, minRight->_key);

				if (minRight == cur->_right)
					minParent->_right = minRight->_right;//右子树最小结点的左节点一定为空，让父节点链接其右结点即可。
				else
					minParent->_left = minRight->_right;

				delete minRight;
			}
			return true;
		}
	}
	return false;
}

	void InOrder()
	{
		return _InOrder(_root);
	}
private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;

		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);

	}
	Node* _root = nullptr;

	bool InsertR(const K& val)
	{
		return _InsertR(_root, val);
	}
private:
	bool _InsertR(Node*& root, const K& val)//你如果不用引用，那这里就是临时的形参，栈帧外面什么都影响不了
	{
		if (root == nullptr)
		{
			root = new Node(val);
			return true;
		}

		if (val > root->_key)
			return _InsertR(root->_right, val);
		else if (val < root->_key)
			return _InsertR(root->_left, val);
		else
			return false;

	}
	/*bool _InsertR(Node* root, const K& val)//一个比较不错的思路，但是对于空树不太实用
	{
		if (root == nullptr)
		{

		}
		if (root->_key == val)
			return false;
		if (val > root->_key)
		{
			if (root->_right == nullptr)
			{
				root->_right = new Node(val);
				return true;
			}
			else
			{
				_InsertR(root->_right, val);
			}
		}
		else
		{
			if (root->_left == nullptr)
			{
				root->_left = new Node(val);
				return true;
			}
			else
			{
				_InsertR(root->_left, val);
			}
		}
	}*/

	bool FindR(const K& val)
	{
		return _FindR(_root, val);
	}
private:
	bool _FindR(Node* root, const K& val)
	{
		if (root == nullptr)
			return false;

		if (root->_key == val)
			return true;
		else if (root->_key < val)
			return _FindR(root->_right, val);
		else
			return _FindR(root->_left, val);
		//return _FindR(root->_left, val) || _FindR(root->_right, val);//暴力查找就完事了
	}

	bool EraseR(const K& val)
	{
		return _EraseR(_root, val);
	}
private:
	bool _EraseR(Node*& root, const K& val)
	{
		if (root == nullptr)
			return false;
	
		if (val > root->_key)
		{
			return _EraseR(root->_right, val);
		}
		else if (val < root->_key)
		{
			return _EraseR(root->_left, val);
		}
		else
		{
			if (root->_left == nullptr)//用引用删除单链的根节点时，不用去找父亲，直接修改当前结点就可以
			{
				Node* tmp = root;
				root = root->_right;
				delete tmp;
			}
			else if (root->_right == nullptr)
			{
				Node* tmp = root;
				root = root->_left;
				delete tmp;
			}
			else
			{
				//这里的解决方法有两种，一种是直接cv上面的解决方式，一种是通过递归将问题转换为直接删除。
				Node* minRight = root->_right;//找右子树最小结点 或者 左子树最大结点
				while (minRight->_left)
				{
					minRight = minRight->_left;
				}
				swap(root->_key, minRight->_key);
	
				_EraseR(root->_right, val);//虽然整体不是搜索树了，但是root的右子树在交换之后还是搜索树，可以用直接删除。
	
			}
			return true;
		}
	}

template <class K>
class BSTree
{
	typedef TreeNode<K> Node;
public:
	BSTree()
		:_root(nullptr)
	{}
	//BSTree(const BSTree<K>& t)//树的拷贝构造，类型是自定义类型
	//{
		//可以层序遍历，然后将遍历到的数Insert构建一棵新的树。

		//_root = Copy(t._root);

	//}
private:
	Node* _root = nullptr;
};		

~BSTree()
{
	Destroy(_root);
	_root = nullptr;
}
void Destroy(Node* root)
{
	if (root == nullptr)
		return;
	Destroy(root->_left);
	Destroy(root->_right);
	delete root;
}

BSTree(const BSTree<K>& t)//树的拷贝构造，类型是自定义类型
{
	//可以层序遍历，然后将遍历到的数Insert构建一棵新的树。

	_root = Copy(t._root);

}
Node* Copy(Node* root)
{
	if (root == nullptr)
	{
		return nullptr;
	}

	//构建根，然后构建左子树，再构建右子树，构建之后还要将其链接在一起
	Node* newRoot = new Node(root->_key);
	newRoot->_left = Copy(root->_left);
	newRoot->_right = Copy(root->_right);

	return newRoot;
}

BSTree<K>& operator=(const BSTree<K> t)
{

	swap(_root, t._root);

	// 交换之后，不用担心内存泄漏，因为形参对象离开函数栈帧，会自动调用其析构函数，析构的是原来this指向的旧对象
	//拷贝构造出来的新内容已经交换到this手上了，不用担心内存泄漏。
	return *this;
}

namespace KV
{
	template <class K, class V>
	struct TreeNode
	{
		TreeNode(const K& key, const V&value)//每一个结点里面既有_key又有_value
			:_key(key)
			,_value(value)
			, _left(nullptr)
			, _right(nullptr)
		{}

		K _key;
		V _value;
		TreeNode<K,V>* _left;
		TreeNode<K,V>* _right;
	};
	//BSTree<string, vector<string>> bookInfo
	template <class K, class V>
	class BSTree
	{
		typedef TreeNode<K, V> Node;
	public:

		bool Insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				return true;
			}

			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
					return false;
			}

			// cur = new Node(val);//让局部指针cur指向新开辟结点有什么用？对搜索树一点影响都没有，你需要改变搜索树的链接关系。
			if (key > parent->_key)
				parent->_right = new Node(key, value);
			else
				parent->_left = new Node(key, value);
			return true;

		}
		Node* Find(const K& key)//返回树的结点，结点里面有key和value
		{
			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;
		}
		void InOrder()
		{
			_InOrder(_root);
		}
	private:
		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;
			_InOrder(root->_left);
			cout << root->_key << ":" << root->_value << endl;
			_InOrder(root->_right);
		}
		Node* _root = nullptr;
	};
}

void TestBSTree4()//测试KV模型
{
	// 将词库中的单词都放进这棵搜索树中，单词string之间是可以比较大小的，只要单词合法则一定能在搜索树中找到对应的string。
	// Key模型，判断在不在？
	// 场景：检查单词拼写是否正确/车库出入系统/……
	//K::BSTree<string> dict;

	//Key/Value的搜索模型，通过Key查找或修改Value
	
	// 场景1：经典的英汉互译
	KV::BSTree<string, string> dict;//value还可以是一颗搜索树，但如果数据量特别小的话，没必要用搜索树存，用vector就够了
	dict.Insert("apple", "苹果");
	dict.Insert("banana", "香蕉");
	dict.Insert("pear", "鸭梨");
	dict.Insert("watermelon", "西瓜");

	string str;
	while (cin>>str)
	{
		//KV::TreeNode<string, string>* ret = dict.Find(str);
		auto ret = dict.Find(str);
		if (ret)
			cout << ret->_value << endl;
		else
			cout << "无此单词" << endl;
	}
	// 场景2：统计水果出现的次数
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
				"苹果", "香蕉", "苹果", "香蕉" ,"草莓"};
	//统计次数这样的场景非常适合二叉搜索树或者哈希的方式来解决。尤其是你想通过一个值去找另一个值都可以用key value模型解决
	KV::BSTree<string, int> countT;
	for (auto e : arr)
	{
		auto* cur = countT.Find(e);//没有找到返回nullptr
		if (cur == nullptr)
			countT.Insert(e, 1);
		else
			cur->_value++;
	}
	countT.InOrder();
}