/***
 Bst树
***/
#include <iostream>
#include <vector>
#include <deque>
#include <time.h>

using namespace std;

struct Tree{
	int data;
	Tree *left,*right;
};

class bstTree {

private:
	Tree* root;
	int _size;
	void my_insert (int data, Tree *&tree);
	void my_print (Tree *tree);
	void clear (Tree *&tree);
	Tree*& my_find (int data);
	Tree* findMax (Tree* data);
	Tree* findMin (Tree* data);
	bool my_erase (int data, Tree *&tree);
	

public:

	bstTree (void);
	bstTree (int data);
	~bstTree (void);
	void insert (int data);
	void print ();
	bool find (int data);
	void erase(int data);
	int getSize ();
	void levelPrint (); //层序遍历
};


bstTree::bstTree(void){
	root = NULL;
	_size = 0;
}

bstTree::bstTree(int data){
	root = new Tree () ;
	root->data = data;
	_size = 1;
}

void
bstTree::clear (Tree *&tree){
	if (tree->left != NULL)
		clear (tree->left);
	if (tree->right != NULL)
		clear (tree->right);
	if (tree != NULL){
		delete tree;
		tree = 0;
	}
}

bstTree::~bstTree(void){
	if (root == NULL)
		return;
	clear (root);
}

void 
bstTree::my_insert (int data, Tree *&tree){
	if (tree == 0){
		tree = new Tree ();
		tree->data = data;
		_size ++;
	}
	else if (tree->data <= data){
		my_insert (data, tree->right);
	}
	else
		my_insert (data, tree->left);
}

void 
bstTree::insert (int data){
	my_insert (data, root);
}


//中序遍历
void 
bstTree::my_print (Tree *tree){
	if (tree == NULL)
		return;
	if (tree->left != NULL){
		my_print (tree->left);
	}
//	cout<<tree->data<<endl;
	if (tree->right != NULL)
		my_print (tree->right);
}

void 
bstTree::print (){
	if (root == NULL)
		return;
	my_print (this->root);
}

int 
bstTree::getSize (){
	return _size;
}

bool 
bstTree::find (int data){
	Tree * temp = root;
	while (temp != NULL){
		if (temp->data == data)
			return true;
		else if (temp->data < data)
			temp = temp->right;
		else
			temp = temp->left;
	}
	return false;
}

Tree*& 
bstTree::my_find (int data){
	Tree * temp = root;
	while (temp != NULL){
		if (temp->data == data)
			return temp;
		else if (temp->data < data)
			temp = temp->right;
		else
			temp = temp->left;
	}
	temp = NULL;
	return temp;
}

Tree*
bstTree::findMax (Tree * t){

	if (t != NULL){
		while (t->right){
			t = t->right;
		}
	}
	return t;
}

Tree*
bstTree::findMin (Tree * t){

	if (t != NULL){
		while (t->left){
			t = t->left;
		}
	}
	return t;
}

bool
bstTree::my_erase (int data, Tree *& t){

	if (t == NULL)
		return false;
	if (data < t->data)
		my_erase (data, t->left);
	else if (data > t->data)
		my_erase (data, t->right);
	else {
		//删除,左右节点都不为空的情况.先找到右节点最小的替换自己，然后对每个右节点都如此处理.
		if (t->left != NULL && t->right != NULL){
			t->data = findMin (t->right)->data;
			my_erase (t->data, t->right);
		}
		else {
			Tree * old = t;
			t = (t->left != NULL) ? t->left : t->right;
			delete old;
			old = 0;
		}
		return true;
	}
}
void 
bstTree::erase (int data){
	if (_size == 0)
		return;
	else
		my_erase (data, root) ?_size--:false ;
}

void 
bstTree::levelPrint() {
	if (!root)
		return;
	deque <Tree *> queen;
	queen.push_back (root);

	while (!queen.empty ()){
		Tree * node = queen.front ();
		queen.pop_front ();
		cout<<node->data<<endl;
		if (node->left != NULL)
			queen.push_back (node->left);
		if (node->right != NULL)
			queen.push_back (node->right);
	}
	
}

int main(void){

	bstTree tree ;
	long start,end;
	start= clock();
	for (int i = 0; i < 1000000; i ++){
		int num = rand () % 1000000;
		tree.insert (num);
	}
	end = clock ();
	cout<<"BST树插入100万条语句所用时间为"<<end - start<<"毫秒"<<endl; 


	start= clock();
	tree.print ();
	end = clock ();
	cout<<"BST树遍历100万条语句所用时间为"<<end - start<<"毫秒"<<endl; 

}