#include "stdio.h"
#include "conio.h"
#include <iostream>
#include <fstream>
using namespace std;
struct NODE
{
	char Key;
	int count;
	NODE *pLeft;
	NODE *pRight;
};
void NhapVanBan(FILE* fp)
{
	char c=fgetc(fp);
	//ofstream f;
	fp=fopen("input.txt","rt");
	int i = 0;
	while(!feof(fp))
	{
		c = fgetc(fp);

		while ((c >= 'a' && c <= 'z')||(c>='A' && c<='Z') || (c>='0' && c<='9'))
		{
			c = fgetc(fp);
		}
	}
}
/*void NhapVanBan1()
{
	fstream file;
	char* file_name = (char*)"input.txt";
	FILE* f = fopen(file_name, "r");
	//if (f == NULL) cout<<"file not found"<<endl;
	file.open(f);
	char* a;
	//readFile(f, a);
	if(file.is_open() == false)
	{
		file.close();
		return;
	}

	for(int i=0;; i++)
	{
		file>>a[i];
		if(a[i]=='\0') break;
	}
	file.close();
	cout<<"Khong mo duoc file"<<endl;
}*/

void XuatKetQua()
{
}
void Init(NODE *&TREE)
{
	TREE = NULL;
}
void Insert(NODE *&pRoot, char x)
{
	if (pRoot == NULL)

	{
		NODE *q;
		q = new NODE;
		q->Key = x;
		if (q->count==NULL)
			q->count =1;
		else
			q->count = q->count + 1;
		q->pLeft = q->pRight = NULL;
		pRoot = q;
	}
	else
	{
		if (x < pRoot->Key)
			Insert (pRoot->pLeft, x);
		else if (x > pRoot->Key)
			Insert (pRoot->pRight, x);
	}
}
void CreateTreeFile(NODE *&pRoot, char *a)
{
	int Data;
	int i=0;
	do
	{
		Data = a[i];
		Insert(pRoot, Data);
		i++;
	}
	while (a[i]=='\0');
}
void CreateTree(NODE *&pRoot)
{
	int Data;
	do
	{
		printf("Nhap vao du lieu, -1 de ket thuc: ");
		scanf("%d", &Data);
		if (Data == -1)
			break;
		//for (
		Insert(pRoot, Data);
	}
	while(1);
}
void NLR(NODE* pTree)
{
	if(pTree != NULL)
	{
		printf("%4d", pTree->Key);
		NLR(pTree->pLeft);
		NLR(pTree->pRight);
	}
}
int SumTree(NODE* pTree)
{
	if (pTree!= NULL)
		return 0;
	else
	{
		return (pTree->Key + SumTree(pTree->pLeft) + SumTree(pTree->pRight));
	}
}
int CountNode(NODE* pTree)
{  //Ham nay de dem co bao nhieu nut trong cay
	if(pTree == NULL) return 0;
	else
		return 1+ CountNode(pTree->pLeft) +CountNode(pTree->pRight);
}

int MaxTree(NODE* pTree)
{
	if (pTree->pRight ==NULL)
		return pTree->Key;
	else
		return MaxTree(pTree->pRight);
}
int MinTree(NODE* pTree)
{
	if (pTree->pLeft ==NULL)
		return pTree->Key;
	else
		return MinTree(pTree->pLeft);
}

int DemTree(NODE* Tree, char a)// so luong nut co du lieu bang a
{
	if(Tree == NULL) return 0;
	else
		if(Tree->Key == a)
			return 1;
		else
			return DemTree(Tree->pLeft, a)+DemTree(Tree->pRight, a);
}

NODE* Search(NODE* pRoot, char x)
{
	if(pRoot == NULL)
		return NULL;
	if(x < pRoot->Key)
		Search(pRoot->pLeft, x);
	else
		if(x > pRoot->Key)
			Search(pRoot->pRight, x);
		else
		{
			return pRoot;
		}
}
int Height(NODE* pNode)
{
	if(pNode == NULL)
		return 0;
	int HL, HR;
	HL = Height(pNode->pLeft);
	HR = Height(pNode->pRight);
	if(HL > HR)
		return (1 + HL);
	return (1 + HR);
}
void SearchStandFor(NODE* &Tree, NODE* &q)
{
	if (Tree->pRight)
		SearchStandFor(Tree->pRight,q);
	else
	{
		q->Key = Tree->Key;
		q = Tree;
		Tree = Tree->pLeft;
	}
}
void RemoveNode(NODE* &Tree, char x)
{
	NODE* p;
	if(Tree == NULL)
		printf("%d khong co trong cay", x);
	else
	{
		if (x < Tree->Key)
			RemoveNode(Tree->pLeft,x);
		else
			if (x > Tree->Key)
				RemoveNode(Tree->pRight,x);
			else
			{
				p = Tree;
				if(p->pRight == NULL)
					Tree = p->pLeft;
				else
					if (p->pLeft == NULL)
						Tree = p->pRight;
					else
					{
						SearchStandFor(Tree->pLeft,p);
					}
					delete p;
			}
	}
}
void main()
{
	NODE* pTree, *p;
	char x;
	char a[100];

	char* file_name = (char*)"input.txt";
	FILE* f = fopen(file_name, "r");
	NhapVanBan(f);
	Init(pTree);
	CreateTreeFile(pTree,a);
	NLR(pTree);
	printf("\nNhap vao 1 gia tri de tim: ");
	scanf("%d", &x);
	p = Search(pTree, x);
	if(p != NULL)
	{
		printf ("%d %d co xuat hien trong cay.\n", x, DemTree(p,x));
		printf("Chieu cao cua nut %d la %d\n", x, Height(p));
		RemoveNode(pTree, x);
		NLR(pTree);
	}
	else
		printf("%d khong co trong cay.\n", x);

	//getch();
}