zx

#include <iostream>
#include <algorithm>
using namespace std;

struct Node
{
	int data;

	Node* left=NULL;
	Node* right=NULL;

};

typedef Node* Tree;

void ktcay(Tree &t) {
	t = NULL;
}

void ThemNodevaocay(Tree& t, int x) {

	if (t == NULL) {
		Node* p = new Node;
		p->data = x;
		t = p;
	}
	else
	{
		if (x < t->data) {
			ThemNodevaocay(t->left, x);
		}
		else if (x > t->data) {
			ThemNodevaocay(t->right, x);

		}
	}
}
void duyetcay(Tree& t) {
	if (t != NULL) {
		cout << t->data << "\t";
		duyetcay(t->left);
		duyetcay(t->right);
	}
}

Node* tk(Tree t,int x) {
	if (t == NULL)return NULL;
	else
	{
		if (x < t->data) {
			tk(t->left,x);
		}else if (x > t->data) {
			tk(t->right,x);
		}
		else
		{
			return t;
		}
	}
}

int highTree(Tree t) {
	if (t == NULL)
		return 0;
	else {
		int left_height = highTree(t->left);
		int right_height = highTree(t->right);

		return max(left_height, right_height) + 1;
	}
}


void XuatNode2con(Tree t) {
	if (t != NULL) {
		if (t->left != NULL && t->right != NULL)
			cout << t->data;

		XuatNode2con(t->left);
		XuatNode2con(t->right);

	}
} // tuong tu 1 con va la


// tim max 

int timmax(Tree t) {	
	if (t->right == NULL) return t->data;
	return timmax(t->right);


}

//
void ditimnodethemang(Tree &x,Tree &y) {
	if (y->left != NULL) {
		ditimnodethemang(x, y->left);
	}
	else
	{
		x->data = y->data;
		x = y;
		y = y->right;
	}

}

void XoaNode(Tree &t, int data) {
	if (t == NULL) return ;
	else {
		if (t->data > data) {
			XoaNode(t->left, data);
		}
		else if (t->data < data) {
			XoaNode(t->right, data);
		}
		else {
			Node* x = t;
			if (t->left == NULL) {
				t = t->right;
			}
			else if(t->right == NULL)
			{
				t = t->left;

			}
			else {
				ditimnodethemang(x, t->right);

			}
			delete x;
		}
	}

}

void Menu(Tree& t) {
	while (true) {
		system("cls");
		cout << "-------menu---------\n";
		cout << "-1.Nhap\n";
		cout << "-2.Xuat\n";
		cout << "-3.tk\n";
		cout << "-4.tim max\n";
		cout << "-5.xoa node bat ki\n";
		cout << "-6.tim chieu cao\n";



		cout << "-0. return\n";
		cout << "----------------\n";
		int lc; cin >> lc;
		if (lc == 1) {
			cout << "Nhap so gia tri muon nhap vao node:\n";
			int n; cin >> n;
			for (int i = 0; i < n; i++)
			{
				int x;
				cout << "Nhap gia tri thu " << i + 1 << endl;
				cin >> x;
				ThemNodevaocay(t, x);
			}

			system("pause");

		}
		else if (lc == 2)
		{
			duyetcay(t);
			system("pause");

		}
		else if (lc == 3)
		{
			cout << "Nhap gia tri muon timf kiem\n"; int x; cin >> x;
			Node* temp = tk(t, x);
			if (temp == NULL) {
				cout << "X khong ton tai trong cay\n"; return;
			}
			cout << "X co ton tai trong cay\n"; 
			system("pause");



		}
		else if (lc == 4)
		{
			cout << "max la: " << timmax(t);
			system("pause");

		}
		else if (lc == 5)
		{
			cout << "Nhap gia tri node muon xoa:\n";
			int data; cin >> data;
			XoaNode(t,data);
			system("pause");


		}
		if (lc == 6)
		{
			cout << "Chieu cao cua cay la: "<< highTree(t);
			system("pause");

		

		}
		else if (lc == 0)
		{
			return;

		}
	}





}



int main() {
	Tree t;
	ktcay(t);
	Menu(t);


	return 0;
}