Untitled

#include <iostream>
//#include <string>

using namespace std;

struct node {
    int data;            // Dữ liệu của node được lưu trữ
    struct node *pLeft;  // node liên kết trái (hay cây con trái)
    struct node *pRight; // node liên kết phải hay cây con phải
};

typedef struct node NODE; // đổi cú pháp struct node thành NODE để tiện sử dụng
typedef NODE *TREE;       // đổi NODE* thành TREE cho dễ sử dụng (bản chất vẫn trỏ về struct node)

int sum_tree; // Biến lưu số lượng node trong cây

// Khởi tạo cây
void init(TREE &t) {
    t = NULL; // cây rỗng
}

// Hàm thêm phần tử x vào cây nhị phân
void add_tree(TREE &t, int x) {
    // Nếu cây rỗng
    if (t == NULL) {
        NODE *p = new NODE; // Khởi tạo 1 node để thêm vào cây
        p->data = x;        // Thêm dữ liệu x vào data
        p->pLeft = p->pRight = NULL;
        t = p; // Node p là node gốc hay x là node gốc
        sum_tree++; // Tăng số lượng node
    }
    else { // Cây có tồn tại phần tử
        if (t->data > x) {
            add_tree(t->pLeft, x); // Thêm vào bên trái
        }
        else if (t->data < x) {
            add_tree(t->pRight, x); // Thêm vào bên phải
        }
        // Nếu phần tử đã tồn tại, không làm gì cả
    }
}

// Hàm tìm kiếm node với giá trị x
bool find_node(TREE &t, int x) {
    if (t == NULL) {
        return 0;
    }
    else {
        if (t->data == x) {
            return 1;
        }
        else if (t->data < x) {
            return find_node(t->pRight, x);
        }
        else {
            return find_node(t->pLeft, x);
        }
    }
}

// Hàm xóa node
int remove_node(TREE &t, int x) {
    if (t == NULL) {
        return 0; // Không tìm thấy
    }
    else if (t->data > x) {
        return remove_node(t->pLeft, x);
    }
    else if (t->data < x) {
        return remove_node(t->pRight, x);
    }
    else { // Tìm thấy node cần xóa
        if (t->pLeft == NULL && t->pRight == NULL) { // Node lá
            delete t;
            t = NULL;
        }
        else if (t->pLeft == NULL) { // Node có 1 con phải
            NODE *tmp = t;
            t = t->pRight;
            delete tmp;
        }
        else if (t->pRight == NULL) { // Node có 1 con trái
            NODE *tmp = t;
            t = t->pLeft;
            delete tmp;
        }
        else { // Node có 2 con
            NODE *tmp = t->pRight;
            while (tmp->pLeft != NULL)
                tmp = tmp->pLeft;
            t->data = tmp->data;
            return remove_node(t->pRight, tmp->data);
        }
        sum_tree--; // Giảm số lượng node
        return 1;
    }
}

int upper_bound(TREE &t, int x)
{
	NODE *tmp = new NODE;
	tmp->data = -10000;
	NODE *tmp1 = t;
	while( tmp1 != NULL)
	{
		if( tmp1->data < x )
		{
			tmp = tmp1;
			tmp1 = tmp1->pRight;
		}
		else
			tmp1 = tmp1->pLeft;
	}
	return tmp->data == -10000 ? 0 : tmp->data;
}

int lower_bound(TREE &t, int x)
{
	NODE *tmp = new NODE;
	tmp->data = 10000;
	NODE *tmp1 = t;
	while( tmp1 != NULL)
	{
		if( tmp1->data >= x )
		{
			tmp = tmp1;
			tmp1 = tmp1->pLeft;
		}
		else
			tmp1 = tmp1->pRight;
	}
	return tmp->data == 10000 ? 0 : tmp->data;
}

int main(int argc, char** argv)
{
	int test_case;
	int T;
	/* 
	The freopen function below opens input.txt in read only mode and 
	sets your standard input to work with the opened file. 
	When you test your code with the sample data, you can use the function
	below to read in from the sample data file instead of the standard input.
	So. you can uncomment the following line for your local test. But you
	have to comment the following line when you submit for your scores.
	*/

	//freopen("Text.txt", "r", stdin);
	cin>>T;

	/*
	Read each test case from standard input.
	*/
	for(test_case = 1; test_case <= T; ++test_case)
	{

		int n;
		cin >> n;
		TREE t;
		sum_tree = 0;
		init(t);
		cout << "#" << test_case << " ";
		for(int i = 0; i < n; i++)
		{
			string lenh;
			cin >> lenh;
			if(lenh != "size")
			{
				int x;
				cin >> x;
				if(lenh == "add")
				{
					add_tree(t,x);
				}
				else if(lenh == "remove")
				{
					remove_node(t,x);
				}
				else if(lenh == "contains")
				{
					bool found = find_node(t,x);
					cout << (found == 1 ? "true" : "false" ) << " ";
				}
				else if(lenh == "lower")
				{
					int tmp = upper_bound(t,x);
					tmp == 0 ? cout << "null " : cout << tmp << " ";
				}
				else
				{
					int tmp = lower_bound(t,x);
					tmp == 0 ? cout << "null " : cout << tmp << " ";
				}
			}
			else
			{
				cout << sum_tree << " ";
			}
		}
		cout << endl;
	}
	return 0;//Your program should return 0 on normal termination.
}