C++程序员修炼手册—搜索二叉树实现

二叉树最难处理的函数模块为删除某个元素：
首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种清况：
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：
情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点
情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点
情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，
再来处理该结点的删除问题

具体如代码所示：

#include
using namespace std;
template
struct BSTNode
{
	BSTNode * left;
	BSTNode * right;
	K _key;

	BSTNode(const K& key)
		:left(nullptr)
		, right(nullptr)
		, _key(key)
	{}
};
template
class BStree
{
	typedef BSTNode node;
public:
	BStree()//构造函数
		:_root(nullptr)
	{}
	//拷贝构造
	BStree(const BStree& t)
	{
		_root = _copy(t._root);
	}
	//析构函数
	~BStree()
	{
		destory(_root);
		_root = nullptr;
	}
	//运算符重载
	BStree& operator=(BStree t)
	{
		swap(_root, t._root);
		return *this;
	}
	//插入数据
	bool insert(const K& x)
	{
		if (_root == nullptr)
		{
			_root = new node(x);
			return true;
		}
		node*cur = _root;
		node*parent = nullptr;//防止越界
		while (cur)     //找位置
		{
			if (cur->_key > x)//x小于当前值，向左子树找小于的值,找到节点
			{
				parent = cur;
				cur = cur->left;
			}
			else if (cur->_key < x)
			{
				parent = cur;
				cur = cur->right;
			}
			else
			{
				return false;
			}
		}
		cur = new node(x);
		if (parent->_key < x)  //如果这个值大于parent，放在parent右边
		{
			parent->right = cur;
		}
		else
		{
			parent->left = cur;//如果这个值小于parent，放在parent左边
		}
		return true;
	}
	//查找函数
	node* find(const K& x)
	{
		node*cur = _root;
		while (cur)
		{
			if (x > cur->_key)
			{
				cur = cur->right;
			}
			else if (x < cur->_key)
			{
				cur = cur->left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}
	bool erase(const K& x)
	{
		node*cur = _root;
		node*parent = nullptr;
		while (cur)
		{
			if (x > cur->_key)
			{
				parent = cur;
				cur = cur->right;
			}
			else if (x < cur->_key)
			{
				parent = cur;
				cur = cur->left;
			}
			else//找到了
			{
				if (cur->left == nullptr)//要删除的元素左边为空，右边不为空（或为空）
				{
					if (cur == _root)//cur没有父亲
					{
						_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)//如果树顶是要删除的那个元素
					{
						_root = cur->left;
					}
					else
					{
						if (parent->left = cur)
						{
							parent->left = cur->left;
						}
						else
						{
							parent->right = cur->left;
						}
					}
					delete cur;
					return true;
				}
				else
				{
					//node*minparent = cur;
					//node*minright = cur->right;//右子树找最小值去替换当前cur
					//while (minright->left)
					//{
					//	minparent = minright;
					//	minright = minright->left;
					//}
					找到右树最小节点，替换当前cur'
					//cur->_key = minright->_key;
					删除替换节点
					//if (minparent->left == minright)
					//{
					//	minparent->left = minright->right;
					//}
					//else
					//{
					//	minparent->right = minright->right;
					//}
					//delete minright;
					//return true;
					node*minparent = cur;
					node*minright = cur->right;
					while (minright->left)
					{
						minparent = minright;
						minright = minright->left;
					}
					K min = minright->_key;
					erase(minright->_key);
					cur->_key = min;

				}
			}
			return true;
		}
		return false;
	}

	//递归版本

	void inorder()
	{
		_inorder(_root);
		cout << endl;
	}
	node*_find(const K& x)
	{
		return find_r(_root, x);
	}
	
	void test_erase(const K& x)
	{
		_erase(_root, x);
	}
	bool _insert(const K& x)
	{
		return insert_r(_root, x);
	}

private:
	node* _root;
	bool _erase(node*&root, const K& x)
	{
		if (root == NULL)
		{
			return  false;
		}
		if (x > root->_key)
		{
			return _erase(root->right, x);
		}
		else if (x < root->_key)
		{
			return _erase(root->left, x);
		}
		else
		{
			if (root->left == nullptr)//找到了，root是指向找到元素的指针
			{
				node*del = root;
				root = root->right;
				delete del;
				return true;
			}
			else if (root->right == nullptr)
			{
				node*del = root;
				root = root->left;
				delete del;
				return true;
			}
			else
			{
				node*minright = root->right;
				while (minright->left)
				{
					minright = minright->left;
				}
				//转换成在右子树里面删除最小的那个元素
				K min = minright->_key;//右子树中最小的那个元素
				_erase(root->right, min);
				root->_key = min;
				return true;
			}
		}
		return false;
	}
	void _inorder(node* cur)//中序遍历
	{
		if (cur == nullptr)
		{
			return;
		}
		_inorder(cur->left);
		cout << cur->_key << " ";
		_inorder(cur->right);
	}
	bool insert_r(node*&root, const K&x)//传引用，从而在root->left或root->right上直接连接，非常巧妙
	{
		if (root == nullptr)
		{
			root= new node(x);
			return true;
		}
		if (x > root->_key)
		{
			return insert_r(root->right, x);
		}
		else if (x < root->_key)
		{
			return insert_r(root->left, x);
		}
		else
		{
			return false;
		}
	}
	node*find_r(node*root, const K&x)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		if (x > root->_key)
		{
			return find_r(root->right, x);
		}
		else if (x < root->_key)
		{
			return find_r(root->left, x);
		}
		else
		{
			return root;
		}
	}
	//copy函数
	node*_copy(node*root)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		node*copynode = new node(root->_key);
		copynode->left = _copy(root->left);
		copynode->right = _copy(root->right);
		return copynode;
	}
	//destory
	void destory(node*root)
	{
		if (root == nullptr)
		{
			return;
		}
		destory(root->left);
		destory(root->right);
		delete root;
	}
	
};

 KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。该种方式在现实生活中非常常见：比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文就构成一种键值对；再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是就构成一种键值对。

#include
using namespace std;
template
struct BSTNode
{
	BSTNode * left;
	BSTNode * right;
	K _key;
	V _val;

	BSTNode(const K& key,const V& val)
		:left(nullptr)
		, right(nullptr)
		, _key(key)
		, _val(val)
	{}
};
template
class BStree
{
	typedef BSTNode node;
public:
	BStree()//构造函数
		:_root(nullptr)
	{}
	//拷贝构造
	BStree(const BStree& t)
	{
		_root = _copy(t._root);
	}
	//析构函数
	~BStree()
	{
		destory(_root);
		_root = nullptr;
	}
	//运算符重载
	BStree& operator=(BStree t)
	{
		swap(_root, t._root);
		return *this;
	}
	void inorder()
	{
		_inorder(_root);
		cout << endl;
	}
	node*_find(const K& x)
	{
		return find_r(_root, x);
	}

	void test_erase(const K& x)
	{
		_erase(_root, x);
	}
	bool _insert(const K& x,const V& val)
	{
		return insert_r(_root, x,val);
	}

private:
	node* _root;
	bool _erase(node*&root, const K& x)
	{
		if (root == NULL)
		{
			return  false;
		}
		if (x > root->_key)
		{
			return _erase(root->right, x);
		}
		else if (x < root->_key)
		{
			return _erase(root->left, x);
		}
		else
		{
			if (root->left == nullptr)//找到了，root是指向找到元素的指针
			{
				node*del = root;
				root = root->right;
				delete del;
				return true;
			}
			else if (root->right == nullptr)
			{
				node*del = root;
				root = root->left;
				delete del;
				return true;
			}
			else
			{
				node*minright = root->right;
				while (minright->left)
				{
					minright = minright->left;
				}
				//转换成在右子树里面删除最小的那个元素
				K min = minright->_key;//右子树中最小的那个元素
				_erase(root->right, min);
				root->_key = min;
				return true;
			}
		}
		return false;
	}
	void _inorder(node* cur)//中序遍历
	{
		if (cur == nullptr)
		{
			return;
		}
		_inorder(cur->left);
		cout << cur->_key << " " <_val << endl;;
		_inorder(cur->right);
	}
	bool insert_r(node*&root, const K&x, const V &val)//传引用，从而在root->left或root->right上直接连接，非常巧妙
	{
		if (root == nullptr)
		{
			root = new node(x,val);
			return true;
		}
		if (x > root->_key)
		{
			return insert_r(root->right, x,val);
		}
		else if (x < root->_key)
		{
			return insert_r(root->left, x,val);
		}
		else
		{
			return false;
		}
	}
	node*find_r(node*root, const K&x)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		if (x > root->_key)
		{
			return find_r(root->right, x);
		}
		else if (x < root->_key)
		{
			return find_r(root->left, x);
		}
		else
		{
			return root;
		}
	}
	//copy函数
	node*_copy(node*root)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		node*copynode = new node(root->_key,root->_val);
		copynode->left = _copy(root->left);
		copynode->right = _copy(root->right);
		return copynode;
	}
	//destory
	void destory(node*root)
	{
		if (root == nullptr)
		{
			return;
		}
		destory(root->left);
		destory(root->right);
		delete root;
	}

};

test：

#include"kv.h"
#include
void TestBSTree3()
{
	BStree dict;
	dict._insert("string", "字符串");
	dict._insert("tree", "树");
	dict._insert("left", "左边、剩余");
	dict._insert("right", "右边");
	dict._insert("sort", "排序");
	// ...插入词库中所有单词
	string str;
	while (cin >> str)
	{
		BSTNode* ret = dict._find(str);
		if (ret == nullptr)
		{
			cout << "单词拼写错误，词库中没有这个单词:" << str << endl;
		}
		else
		{
			cout << str << "中文翻译:" << ret->_val << endl;
		}
	}
}
void TestBSTree4()
{
	// 统计水果出现的次数
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
	BStree countTree;
	for (const auto& str : arr)
	{
		// 先查找水果在不在搜索树中
		// 1、不在，说明水果第一次出现，则插入<水果, 1>
		//KV::BSTreeNode* ret = countTree.FindR(str);
		auto ret = countTree._find(str);
		if (ret == NULL)
		{
			countTree._insert(str, 1);
		}
		else
		{
			ret->_val++;
		}
	}

	countTree.inorder();
}
int main()
{
	//TestBSTree3();
	TestBSTree4();
	return 0;
}