二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
1.若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2.若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3.它的左右子树也分别为二叉搜索树

#pragma once
#include<iostream>
using namespace std;

template<class T>
struct bstnode
{
	T _val;
	bstnode* _left;
	bstnode* _right;
	bstnode(const T& val) :_val(val), _left(nullptr), _right(nullptr)
	{}


	~bstnode()
	{
		_left = nullptr;
		_right = nullptr;
		_val = 0;
	}

};



template<class T>
class BST
{
	
public:
	typedef bstnode<T> bstnode;
	BST() :_node(nullptr)
	{}




	bool push(const T& data)
	{
		bstnode* root = _node;
		bstnode* rootp = nullptr;
		if (_node == nullptr)
		{
			bstnode *temp = new bstnode(data);
			_node = temp;
			return true;
		}
		while (root)
		{
			if (data < root->_val)
			{
				rootp = root;
				root = root->_left;
			}
			else if (data > root->_val)
			{
				rootp = root;
				root = root->_right;
			}
			else
			{
				return false;
			}
		}
		bstnode *newnode = new bstnode(data);
		if (newnode->_val > rootp->_val)
		{
			rootp->_right = newnode;
		}
		else
		{
			rootp->_left = newnode;
		}
		return true;
	}


	bool erase(const T&data)
	{
		bstnode* root = _node;
		bstnode* rootp = nullptr;
		while (root)
		{
			//找节点
			if (data < root->_val)
			{
				rootp = root;
				root = root->_left;
			}
			else if (data > root->_val)
			{
				rootp = root;
				root = root->_right;
			}
			else
				break;
		}
			//如果为空直接返回false
			if (root == nullptr)
				return false;
			if (root == _node)
				rootp = root;
			//如果root左边是空
			if (root->_left == nullptr)
			{
				
				if (rootp->_left == root)
				{
					if (root == _node)
					{
						_node = root->_right;
					}
					else
					{
						rootp->_left = root->_right;
					}
				}
				else
				{
					if (root == _node)
					{
						_node = root->_right;
					}
					else
					{
						rootp->_right = root->_right;
					}
				}
				delete  root;
			}
			//如果右边是空
			else if (rootp->_right == nullptr)
			{
				if (rootp->_left == root)
				{
					rootp->_left = root->_left;
				}
				else
				{
					rootp->_right = root->_left;
				}
				delete root;
			}
			//如果两边都不为空
			else
			{
				bstnode* find = root->_right;
				bstnode* findp = root;
				while (find->_left)
				{
					findp = find;
					find = find->_left;
				}
				root->_val = find->_val;
				if (root == findp)
				{
					findp->_right = find->_right;
				}
				else
				{
					findp->_left = find->_right;
				}
				delete find;
			}
			return true;
	}
	


	bool find(const T& data)
	{
		bstnode* root = _node;
		while (root)
		{
			if (root->_val < data)
			{
				root = root->_left;
			}
			else if (root->_val > data)
			{
				root = root->_right;
			}
			else
			{
				return true;
			}

			return false;
		}
	}


	void print()
	{
		print(_node);
		cout << endl;
	}


private:
	void print(bstnode* root)
	{
		if (root == nullptr)
		{
			return;
		}
		print(root->_left);
		cout << root->_val << " ";
		print(root->_right);
	}
	bstnode* _node;
};