#include <stdio.h>
#include<stdlib.h>
typedef struct Node//khoi tao nut
{
	Node* left;
	Node* right;
	int data;
}Node;
typedef Node* Tree;//tao cay
Node* TaoNode(int x)//tao 1 nut
{
	Node* p = (Node*)malloc(sizeof(Node));
	p->left = NULL;
	p->right = NULL;
	p->data = x;
	return p;
}
void ThemNodeVaoCay(Tree &T, int x)//them nut vao cay
{
	Node* p = TaoNode(x);
	if (T == NULL)
		T = p;
	else
	{
		if (T->data>x) ThemNodeVaoCay(T->left, x);
		else ThemNodeVaoCay(T->right, x);
	}
}
void Nhap(Tree &T)//nhap phan tu vao cay
{
	int x;
	while (1)
	{
		printf("Nhap vao Node: ");
		scanf("%d", &x);
		if (x == 0) break;
		ThemNodeVaoCay(T, x);
	}
}
void Xuat(Tree T)
{
	if (T != NULL)
	{
		printf("%d ", T->data);
		if (T->left != NULL)
			Xuat(T->left);
		if (T->right != NULL)
			Xuat(T->right);
	}
}

int SoLa(Tree T){
	if (T == NULL) return 0;
	else
	if (T->left == NULL && T->right == NULL) return 1;
	else
	{
		int d1 = SoLa(T->left);
		int d2 = SoLa(T->right);
		return d1 + d2;
	}
}
int SoNode(Tree T){
	if (T == NULL) return 0;
	else
	if (T->left == NULL && T->right == NULL) return 1;
	else{
		int d1 = SoNode(T->left);
		int d2 = SoNode(T->right);
		return d1 + d2 + 1;
	}
}
int Height(Tree T){
	if (T == NULL) return 0;
	else if (T->left == NULL && T->right == NULL) return 1;
	else {
		int d1 = Height(T->left);
		int d2 = Height(T->right);
		if (d1>d2)
			return d1 + 1;
		else return d2 + 1;
	}
}
/*int Search(Tree T,int x){
if(T==NULL) return 0;
if(T->data==x) return x;
else
if(T->data>x)
Search(T->left,x);
else
Search(T->right,x);

}*/
/*void GiaTriLonHon_x(Tree T,int x){
if(T!=NULL){
if(T->data>x)
printf("%d\t",T->data);
if (T->left != NULL){
if(T->data>x)
GiaTriLonHon_x(T->left,x);
}
if (T->right != NULL){
if(T->data>x)
GiaTriLonHon_x(T->right,x);
}
}
}*/
int Search(Tree T, int x){
	if (!T)
		return 0;
	if (T->data == x)
		return 1 + Search(T->left, x) + Search(T->right, x);

	return 0 + Search(T->left, x) + Search(T->right, x);
}
int main()
{
	Tree T = NULL;
	Nhap(T);
	printf("\nXuat cay nhi phan tim kiem theo thu tu truoc NLR: ");
	Xuat(T);
	printf("\n Tong cac nut la trong cay: %d", SoLa(T));
	printf("\n Tong cac so nut trong cay: %d", SoNode(T));
	printf("\n Chieu cao cua cay la: %d ", Height(T));
	int x;
	printf("\nNhap vao gia tri de tim: ");
	scanf("%d", &x);
	int s = Search(T, x);
	if (s != 0)
	{
		printf("\n%d  xuat hien %d lan trong cay ", x, s);
	}

	return 0;
}