C++实现二叉搜索树

#pragma once

 
template
struct BSTreeNode
{
	BSTreeNode(const K& key)
	:left(nullptr)
	, right(nullptr)
	, _key(key)
	{}

	BSTreeNode* left;
	BSTreeNode* right;
	K _key;
};

template
struct BSTree
{

	typedef BSTreeNode Node;	

public:
	BSTree()
		:_root(nullptr)
	{}


	//插入
	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			parent = cur;
			if (cur->_key > key)
			{
				cur = cur->left;
			}
			else if (cur->_key < key)
			{
				cur = cur->right;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(key);
		if (parent->_key > key)
		{
			parent->left = cur;
		}
		else
		{
			parent->right = cur;
		}
		return true;
	}

	
	//删除
	bool Earse(const K& key)
	{
		//1.找到要删的节点
		Node* parent = nullptr;
		Node* cur = _root;
		while(cur)
		{
			if (cur->_key > key)
			{
				parent = cur; 
				cur = cur->left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->right;
			}
			else
			{
				//找到了，进行删除。	
				//（1）有一个字节点或者没有子节点
				if (cur->left == nullptr)
				{
					if (parent == nullptr)
					{
						_root = cur->right;
						return true;
					}

					Node* child = cur->right;
					if (parent->left == cur)
					{
						parent->left = child;
					}
					else
					{
						parent->right = child;
					}

					//记住一定要delete掉cur这个节点
					delete cur;
				}
				else if (cur->right == nullptr)
				{
					if (parent == nullptr)
					{
						_root = cur->left;
						return true;
					}

					Node* child = cur->left;
					if (parent->left == cur)
					{
						parent->left = child;
					}
					else
					{
						parent->right = child;
					}
					//记住一定要delete掉cur这个节点
					delete cur;
				}
				//(2)左孩子右孩子都有
				else
				{
					//1.先找到右子树的最小节点或者左子树的最大节点
					//（我这里找的是右子树的最小节点）
					//必须要有父亲才能删除
					Node* Min_parent = cur;
					Node* Min_right = cur->right;
					while (Min_right->left)
					{
						Min_parent = Min_right;
						Min_right = Min_right->left;
					}
					
					//2.进行替换
					cur->_key = Min_right->_key;

					//3.删除被替换的节点（一定是叶子节点或者只有一个子节点的节点)
					//为什么要判断呢？
					//因为有可能Min_Parent就是cur
					if (Min_parent->left == Min_right)
					{
						Min_parent->left = Min_right->right;
					}
					else
					{
						Min_parent->right = Min_right->right;
					}
					delete Min_right; 
				}

				return true;
			}
		}
		//没有这个值，删除失败
		return false;
	}

	//中序遍历,为什么写一个子程序？
	 //因为外面调用不到private的_root
	void InOrder()
	{
		_InOrder(_root);
	}

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

		_InOrder(root->left);
		cout << root->_key << " ";
		_InOrder(root->right);
	}

	//查找
	bool Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key == key)
			{
				return true;
			}
			else if (cur->_key > key)
			{
				cur = cur->left;
			}
			else
			{
				cur = cur->right;
			}
		}
		return false;
	}

	//递归版本
	//设置子函数的原因还有一样，外界无法访问到_root

	//1.插入
	bool InsertR(const K& key)
	{
		_InsertR(key, _root);
		return true;
	}

	//这里的引用用的很巧妙。
	//因为这里的root就是这棵树的节点，遇到空了就是可以进行插入了
	//直接进行new就完成了插入操作。
	bool _InsertR(const K& key, Node*& root)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}

		if (root->_key > key)
		{
			return _InsertR(key, root->left);
		}
		else if (root->_key < key)
		{
			return _InsertR(key, root->right);
		}
		else
		{
			return false;
		}

		
	}

	//2.查找
	Node* FindR(const K& key)
	{
		return _FindR(key, _root);
	}

	Node* _FindR(const K& key, Node* root) 
	{
		if (key == root->_key || key == nullptr)
		{
			return root;
		}

		if (root->_key > key)
		{
			_FindR(key, root->left);
		}

		if (root->_key < key)
		{
			_FindR(key, root->right);
		}
	}


	//3.删除
	bool EarseR(const K& key)
	{
		return _EarseR(key, _root);
	}

	//这里的参数也是引用很巧妙
	bool _EarseR(const K& key, Node*& root)
	{
		if (root == nullptr)
		{
			return false;
		}

		//先找到要删除的节点
		if (root->_key > key)
		{
			_EarseR(key, root->left);
		}
		else if (root->_key < key)
		{
			_EarseR(key, root->right);
		}
		else
		{
			//进行删除
			//先记录要删除的节点
			Node* del = root;
			if (root->left == nullptr)
			{
				//很巧妙，直接将root换成了另外一个不为空或者可能为空的子树。
				root = root->right;
				delete del;
			}
			else if (root->right == nullptr)
			{
				root = root->left;
				delete del;
			}
			
			//要删除节点的有两个的时候
			else
			{
				//
				Node* min_right = root->right;
				while (min_right->left)
				{
					min_right = min_right->left;
				}

				//交换两个节点的的值
				swap(root->_key, min_right->_key);

				//当交换之后，整颗树就不是二叉搜索树了，
				//所以我们要在这个节点的右节点去删除这个值的节点就是很巧妙
				_EarseR(key, root->right);

			}
		}
	}


private:
	Node* _root;

};


void TestBSTree()
{
	BSTree b;
	int a[] = { 5, 3, 6, 2, 4, 7 };
	for (auto e : a)
	{
		b.InsertR(e);
	}
	
	b.EarseR(7);

	b.InOrder();

}