#include "iostream"
#include "stdio.h"
#include "conio.h"
#include "math.h"
using namespace std;
//---------------- Câu 1 ------------------------
typedef struct tagTNode
{
	int key;
	struct tagTNode *pLeft;
	struct tagTNode *pRight;
}TNode;
typedef TNode *Tree;
void CreateTree(Tree &T)
{
	T = NULL;
}
TNode *CreateTNode(int x)
{
	TNode *p;
	p = new TNode;
	if (p == NULL)exit(1);
	else
	{
		p->key = x;
		p->pLeft = NULL;
		p->pRight = NULL;
	}
	return p;
}
int InsertNode(Tree &T, int x)
{
	if (T)
	{
		if (T->key == x)return 0;
		if (T->key<x) return InsertNode(T->pRight, x);
		else if (T->key>x) return InsertNode(T->pLeft, x);
	}
	T = new TNode;
	if (T == NULL) return -1;
	T->key = x;
	T->pLeft = T->pRight = NULL;
	return 1;
}
void InsertTree(Tree &T)
{
	int n = 11;
	int A[11] = { 50,31,71,20,45,60,90,10,55,65,100};
	for (int i = 0; i < n; i++)
		InsertNode(T, A[i]);
}
// ------------------- Câu 2 -------------------
void LNR(Tree T)
{
	if (T != NULL)
	{
		LNR(T->pLeft);
		cout << T->key << " ";
		LNR(T->pRight);
	}
}
void NLR(Tree T)
{
	if (T != NULL)
	{
		cout << T->key << " ";
		NLR(T->pLeft);
		NLR(T->pRight);
	}
}
void RNL(Tree T)
{
	if (T != NULL)
	{
		RNL(T->pRight);
		cout << T->key << " ";
		RNL(T->pLeft);
	}
}
//------------------- Câu 3 ----------------------
TNode *SearchNode(Tree T, int x)
{
	if (T != NULL)
	{
		if (T->key == x)return T;
		else if (T->key>x) return SearchNode(T->pLeft, x);
		else return SearchNode(T->pRight, x);
	}return NULL;
}
//-------------------- Câu 5-----------------------
void demla(Tree T, int &la)
{
	if (T)
	{
		if ((T->pLeft == NULL) && (T->pRight == NULL))la++;
		demla(T->pLeft, la);
		demla(T->pRight, la);
	}
}
void demtrai(Tree T, int &left)
{
	if (T)
	{
		if ((T->pLeft != NULL) && (T->pRight == NULL))left++;
		demtrai(T->pLeft, left);
		demtrai(T->pRight, left);
	}
}
void demphai(Tree T, int &right)
{
	if (T)
	{
		if ((T->pLeft == NULL) && (T->pRight != NULL))right++;
		demphai(T->pLeft, right);
		demphai(T->pRight, right);
	}
}
void demhaicon(Tree T, int &haicon)
{
	if (T)
	{
		if ((T->pLeft != NULL) && (T->pRight != NULL))haicon++;
		demhaicon(T->pLeft, haicon);
		demhaicon(T->pRight, haicon);
	}
}
int nguyento(int n)
{
	if (n == 1) return 0;
	float t = sqrt(float(n));
	for (int i = 2; i <= t; i++) if (n%i == 0)return 0;
	return 1;
}
void demsnt(Tree T, int &snt)
{
	if (T)
	{
		if (nguyento(T->key) == 1)snt++;
		demsnt(T->pLeft, snt);
		demsnt(T->pRight, snt);
	}
}
//------------------- Câu 7 ------------------------------
void thaythe(Tree &p, Tree&T)
{
	if (T->pLeft != NULL) thaythe(p, T->pLeft);
	else
	{
		p->key = T->key;
		p = T;
		T = T->pRight;
	}
}
void deleteNode(Tree &T, int x)
{
	if (T != NULL)
	{
		if (T->key<x)deleteNode(T->pRight, x);
		else
		{
			if (T->key>x)deleteNode(T->pLeft, x);
			else
			{
				TNode *p;
				p = T;
				if (T->pLeft == NULL)T = T->pRight;
				else
				{
					if (T->pRight == NULL)T = T->pLeft;
					else thaythe(p, T->pRight);
				}
				delete p;
			}
		}
	}
	else cout << "Khong tim thay node K de xoa";

}
void menu()
{
	cout << "\n\n---------------";
	cout << "\n0: Exit";
	cout << "\n1: Duyet NLR";
	cout << "\n2: Duyet LNR";
	cout << "\n3: Duyet RNL";
	cout << "\n4: Tim phan tu co khoa K tren cay";
	cout << "\n5: Dem cac nut la";
	cout << "\n6: Dem so node chi co cay con trai";
	cout << "\n7: Dem so node chi co cay con phai";
	cout << "\n8: Dem so node co 2 con";
	cout << "\n9: Dem cac so nguyen to trong cay";
	cout << "\n10: Xoa not K trong cay";
}
void main()
{
	Tree T;
	int x;
	CreateTree(T);
	InsertTree(T);
	do
	{
		int c;
		menu();
		cout << "\n\nNhap lua chon: ";
		cin >> c;
		switch (c)
		{
		case 0: exit(1);
		case 1: {NLR(T); break; }
		case 2: {LNR(T); break; }
		case 3: {RNL(T); break; }
		case 4:
		{
			cout << "Nhap K can tim: ";
			cin >> x;
			if (SearchNode(T, x) != NULL)cout << "Co phan tu K trong cay";
			else cout << "Khong ton tai phan tu K trong cay";
			break;
		}
		case 5:
		{
			int la = 0;
			demla(T, la);
			cout << "So nut la trong cay la: " << la; break;
		}
		case 6:
		{
			int left = 0;
			demtrai(T, left);
			cout << "So nut la chi co cay con trai trong cay la: " << left; break;
		}
		case 7:
		{
			int right = 0;
			demtrai(T, right);
			cout << "So nut la chi co cay con phai trong cay la: " << right; break;
		}
		case 8:
		{
			int haicon = 0;
			demhaicon(T, haicon);
			cout << " So nut co 2 con trong cay la: " << haicon; break;
		}
		case 9:
		{
			int snt = 0;
			demsnt(T, snt);
			cout << "So node la so nguyen to trong cay la: " << snt;
			break;
		}
		case 10:
		{
			int x;
			cout << "Nhap gia tri node K can xoa: ";
			cin >> x;
			deleteNode(T, x);
			LNR(T);
			break;
		}
		}
	} while (1);
	_getch();
}