【搜索二叉树】—— 我与C++的不解之缘（二十一）

//二叉搜索树
//节点
template<class T>
struct BSTreeNode
{
	T _val;
	BSTreeNode* _left;
	BSTreeNode* _right;
	BSTreeNode(const T& x)
		:_key(x)
		, _left(nullptr)
		, _right(nullptr)
	{}
};

//BSTree
template<class T>
class BSTree
{
	typedef BSTreeNode<T> Node;
public:
	//默认构造
	BSTree()
		:_root(nullptr)
	{}
	//插入
	bool insert(const T& x)
	{
		if (_root == nullptr)
		{
			_root = new Node(x);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (x > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (x < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		Node* newnode = new Node(x);
		if (x < parent->_key)
		{
			parent->_left = newnode;
		}
		else if (x > parent->_key)
		{
			parent->_right = newnode;
		}
		return true;
	}
private:
	Node* _root;
};

//查找
bool find(const T& x)
{
	Node* cur = _root;
	while (cur)
	{
		if (x > cur->_key)
		{
			cur = cur->_right;
		}
		else if (x < cur->_key)
		{
			cur = cur->_left;
		}
		else
		{
			return true;
		}
	}
	return false;
}

//删除
bool erase(const T& x)
{
	Node* parent = _root;
	Node* cur = _root;
	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)//左孩子为空或者左右孩子都为空
			{
				Node* del = cur;
				if (cur == parent->_left)
				{
					parent->_left = cur->_right;
				}
				else
				{
					parent->_right = cur->_right;
				}
				delete del;
			}
			else if (cur->_right == nullptr) //右孩子为空
			{
				Node* del = cur;
				if (cur == parent->_left)
				{
					parent->_left = cur->_left;
				}
				else
				{
					parent->_right = cur->_left;
				}
				delete del;
			}
			else //左右孩子都不为空
			{
				//在左子树中找最大的
				Node* left_max = cur->_left;
				Node* left_max_p = cur;

				while (left_max->_right)
				{
					left_max_p = left_max;
					left_max = left_max->_right;
				}
				//赋值
				cur->_key = left_max->_key;
				//然后删除left_max
				if (left_max_p->_left == left_max)
				{
					left_max_p->_left = left_max->_left;
				}
				else
				{
					left_max_p->_right = left_max->_left;
				}
				delete left_max;
			}
			return true;
		}
	}
	return false;
}