#include<iostream>
using namespace std;

template<typename T>
struct TreeNode {
	T val;
	TreeNode* left;
	TreeNode* right;
	TreeNode() :val(0), left(NULL), right(NULL) {}
	TreeNode(T x) :val(x), left(NULL), right(NULL) {}
};

template<typename T>
class BinarySearchTree {
private:
	TreeNode<T>* root;//树的根节点
	TreeNode<T>* insertNode(TreeNode<T>* node, T value);//从node节点开始插，传入值为value的节点
	TreeNode<T>* removeNode(TreeNode<T>* node, T value);//以node节点为根的节点，删除值为value的节点
	bool searchNode(TreeNode<T>* node, T value);//以node节点为根的树里去查找有没有值为value的节点
	void inOrder(TreeNode<T>* node);//中序遍历，因为二叉搜索树的中序遍历是一个递增序列，可以检查我们的二叉搜索树是否正确

public:
	BinarySearchTree() : root(NULL) {}
	~BinarySearchTree();

	void insert(T value) {
		root = insertNode(root, value);//插完之后树的根节点可能会变，要再赋值给根
	}
	void remove(T value) {
		root = removeNode(root, value);
	}
	bool search(T value) {
		return searchNode(root, value);
	}
	void inOrderTraversal() {
		inOrder(root);
		cout << endl;
	}
};
template<typename T>
BinarySearchTree<T>::~BinarySearchTree() {
	while (root) {
		remove(root->val);
	}
}
template<typename T>
TreeNode<T>* BinarySearchTree<T>::insertNode(TreeNode<T>* node, T value) {
	if (node == NULL) {
		return new TreeNode<T>(value);//如果遇到空节点就新建一个新的节点
	}
	if (value < node->val) {
		node->left = insertNode(node->left, value);//value小于当前节点的value，就往左子树插value
		//node->left为空的时候，返回的新节点，需要node->left来承接；
	}
	else if (value > node->val) {
		node->right = insertNode(node->right, value);//value大于当前节点的value，就往右子树插value
	}
	return node;//如果等于就返回节点，结束递归。
}
template<typename T>
TreeNode<T>* BinarySearchTree<T>::removeNode(TreeNode<T>* node, T value) {
	if (node == NULL) {
		return NULL;
	}
	if (value < node->val) {
		node->left = removeNode(node->left, value);//如果value小于node的值，则去删除左子树
	}
	else if (value > node->val) {
		node->right = removeNode(node->right, value);//如果value大于node的值，则去删除右子树
	}
	else {
		//如果value等于node的值,那么这个节点就是我们要删的值

		//如果是叶子节点
		if (node->left == NULL && node->right == NULL) {
			delete node;//则删除该节点即可
			return NULL;
		}else if(node->left==NULL){
			TreeNode<T>* rightChild = node->right;
			delete node;
			return rightChild;
		}
		else if (node->right == NULL) {
			TreeNode<T>* leftChild = node->left;
			delete node;
			return leftChild;
		}
		else {
			//如果左右子树都有
			TreeNode<T>* replacement = node->right;
			while (replacement->left) {
				replacement = replacement->left;//找到右子树中最小的节点，来接替当前删掉的元素。
			}
			//找到最小值后
			node->val = replacement->val;//将当前值替换成replacement的值
			node->right = removeNode(node->right, replacement->val);//我再把右子树这个用来替换的节点删掉
		}
	}
	return node;
}
template<typename T>
bool BinarySearchTree<T>::searchNode(TreeNode<T>* node, T value) {
	if (node == NULL) {
		return false;//如果node为空则没有该值，返回false
	}
	if (value < node->val) {
		return searchNode(node->left,value);//如果value小于node的值，则搜索左子树
	}
	else if (value > node->val) {
		return searchNode(node->right, value);//如果value大于node的值，则搜索右子树
	}
	return true;//如果value等于node的值，则返回true
}
template<typename T>
void BinarySearchTree<T>::inOrder(TreeNode<T>* node) {
	if (node) {
		inOrder(node->left);
		cout << node->val << ',';
		inOrder(node->right);
	}
}
int main() {
	BinarySearchTree<int>bst;
	bst.insert(50);
	bst.insert(30);
	bst.insert(70);
	bst.insert(40);
	bst.insert(80);
	bst.insert(80);
	bst.insert(80);
	bst.insert(60);
	bst.insert(100);

	bst.inOrderTraversal();

	cout << bst.search(9090) << endl;;
	cout << bst.search(100) << endl;
	bst.remove(70);
	bst.inOrderTraversal();
	bst.insert(65);
	bst.inOrderTraversal();

}