#include<stdio.h>
#include<conio.h>
#include<iostream>
#include<stdlib.h>
#define MAX 12

typedef int ItemType;
struct Node {
	ItemType Info;
	Node* Left;
	Node* Right;
};
typedef Node* NodeAddress;
struct BinarySearchTree {
	NodeAddress Root;
};

void InitTree(BinarySearchTree& x);
NodeAddress createNode(ItemType x);
void traverseTreeLNR(NodeAddress n);
void traverseTreeNLR(NodeAddress n);
void traverseTreeRNL(NodeAddress n);
int insertNode(NodeAddress& t, NodeAddress p);
int sumDuongAm(NodeAddress Root,int Duong);
int countNodeDepth(NodeAddress Root, int Depth);
void printfNodeDepth(NodeAddress Root, int Depth);
int heightTree(NodeAddress Root);
int countAtoB(NodeAddress Root, ItemType A,ItemType B);
int sumSoChan(NodeAddress Root);

void Menu()
{
	printf("******************************************************\n");
	printf("*                BINARY SEARCH TREE                  *\n");
	printf("******************************************************\n");
	printf("* %-50s *\n","0.Thoat chuong trinh");
	printf("* %-50s *\n","1.Tao cay nhi phan tu mot mang cho san");
	printf("* %-50s *\n","2.Duyet Cay RLN");
	printf("* %-50s *\n","3.Duyet Cay NLR");
	printf("* %-50s *\n","4.Tong Am Tren Cay");
	printf("* %-50s *\n","5.Tong Duong Tren Cay");
	printf("* %-50s *\n","6.Nhap X vao trong cay");
	printf("* %-50s *\n","7.Xuat cac gia tri theo chieu giam dan");
	printf("* %-50s *\n","8.Dem so nut o muc k ");
	printf("* %-50s *\n","9.Xuat cac gia tro o muc k ");
	printf("* %-50s *\n","10.Dem chieu cao cua cay ");
	printf("* %-50s *\n","11.Tong cac nut co gia tri chan ");
	printf("* %-50s *\n","12.Dem so gia tri trong doan [a,b]");
	printf("******************************************************\n");
}


void main()
{
	BinarySearchTree Tree;
	InitTree(Tree);

	do
	{
		Menu();
		int choose;
		do
		{
			printf("Nhap Chuc Nang:");
			scanf_s("%d",&choose);
		} while (!(choose >= 0 && choose <= MAX));
		switch (choose)
		{
		case 1:
			{
				int number;
				do
				{
					printf("Nhap so nguyen vao cay (-999 de ket thuc):");
					scanf_s("%d",&number);
					if(number == -999) break;
					insertNode(Tree.Root,createNode(number));
				} while (true);
				printf("Nhap xong !!!");
				break;
			}
		case 2:
			{
				printf("Duyet Cay RLN: ");
				traverseTreeLNR(Tree.Root);
				break;
			}
		case 3:
			{
				printf("Duyet Cay RLN: ");
				traverseTreeNLR(Tree.Root);
				break;
			}
		case 4:
			{
				printf("Tong Am Tren Cay: %d\n",sumDuongAm(Tree.Root,0));
				break;
			}
		case 5:
			{
				printf("Tong Duong Tren Cay: %d\n",sumDuongAm(Tree.Root,1));
				break;
			}
		case 6:
			{
				ItemType X;
				printf("Nhap gia tri X:");
				scanf_s("%d",&X);
				insertNode(Tree.Root,createNode(X));
				printf("Da nhap %d vao trong cay\n",X);
				break;
			}
		case 7:
			{
				printf("Gia tri giam dan trong cay: ");
				traverseTreeRNL(Tree.Root);
				break;
			}
		case 8:
			{
				ItemType K;
				printf("Nhap muc k:");
				scanf_s("%d",&K);
				printf("So cac Node trong muc %d la: %d",K,countNodeDepth(Tree.Root,K));
				break;
			}
		case 9:
			{
				ItemType K;
				printf("Nhap muc k:");
				scanf_s("%d",&K);
				printf("Cac Node trong muc %d la: ",K);
				printfNodeDepth(Tree.Root,K);
				break;
			}
		case 10:
			{
				printf("Chieu cao cua cay la: %d",heightTree(Tree.Root));
				break;
			}
		case 11:
			{
				printf("Tong Duong Tren Cay: %d\n",sumSoChan(Tree.Root));
				break;
			}
		case 12:
			{
				ItemType A,B;
				do
				{
						printf("Nhap muc A,B [A<B]:");
						scanf_s("%d%d",&A,&B);
				} while (A > B);
				printf("So gia tri nam trong khoang [%d,%d] la: %d\n",A,B,countAtoB(Tree.Root,A,B));
				break;
			}
		case 0:
			{
				exit(0);
				break;
			}
			
		}
		printf("\n\n");
	}while(true);
}

// Khởi tạo Cây
// param BinarySearchTree x
void InitTree(BinarySearchTree& x)
{
	x.Root = NULL;
}

// Khởi tạo Node
// %param ItemType x
// %return NodeAddress
NodeAddress createNode(ItemType x)
{
	NodeAddress p = new Node;
	if (p == NULL) return NULL;
	p->Left = p->Right = NULL;
	p->Info = x;
	return p;
}

// Duyệt Cây LNR (Theo Thứ Tự Tăng Dần)
// %param BinarySearchTree Root
void traverseTreeLNR(NodeAddress Root)
{
	if (!Root) return;
	traverseTreeLNR(Root->Left);
	printf("%d\t", Root->Info);
	traverseTreeLNR(Root->Right);
}

// Duyệt Cây RNL (Theo Thứ Tự Giảm Dần)
// %param BinarySearchTree Root
void traverseTreeRNL(NodeAddress Root)
{
	if (!Root) return;
	traverseTreeRNL(Root->Right);
	printf("%d\t", Root->Info);
	traverseTreeRNL(Root->Left);
}

// Duyệt Cây NLR
// %param BinarySearchTree Root
void traverseTreeNLR(NodeAddress Root)
{
	if (!Root) return;
	printf("%d\t", Root->Info);
	traverseTreeNLR(Root->Left);
	traverseTreeNLR(Root->Right);
}


//	Thêm Node vào Cây
//	%param NodeAddress t
//	%param NodeAddress p
//	%return int 1|0 (True|False)
int insertNode(NodeAddress& t, NodeAddress p)
{
	if (p == NULL) return 0;
	if (!t) {
		t = p;
		return 1;
	}
	if (t->Info == p->Info) return 0;
	if (p->Info < t->Info) insertNode(t->Left, p);
	else insertNode(t->Right, p);
	return 1;

}

//	Tính Các Giá Trị Âm Hoặc Dương Trong Cây
//	%param NodeAddress Root
//	%param int Duong
//			Duong = 1 Là Tính Giá Trị Dương
//			Duong = 0 Là Tính Giá Trị Âm
//	%return int 
int sumDuongAm(NodeAddress Root,int Duong)
{
	if (!Root) return 0;
	int LeftSum = sumDuongAm(Root->Left,Duong);
	int RightSum = sumDuongAm(Root->Right,Duong);
	if(Duong == 1)
		if(Root->Info > 0)
			return LeftSum + RightSum + Root->Info;
	if(Duong == 0)
		if(Root->Info < 0)
			return LeftSum + RightSum + Root->Info;
	return LeftSum + RightSum;

}

//	Đếm Các Giá Trị Ở Mức K
//	%param NodeAddress Root
//	%param int Depth
//	%return int 
int countNodeDepth(NodeAddress Root, int Depth)
{
	if (!Root) return 0;
	Depth--;
	int LeftCount = countNodeDepth(Root->Left,Depth);
	int RightCount = countNodeDepth(Root->Right,Depth);
	if(Depth == 0)
		return LeftCount + RightCount + 1;
	return LeftCount + RightCount;
}

//	Xuất Các Giá Trị Ở Mức K
//	%param NodeAddress Root
//	%param int Depth
void printfNodeDepth(NodeAddress Root, int Depth)
{
	if (!Root) return;
	Depth--;
	printfNodeDepth(Root->Left,Depth);
	printfNodeDepth(Root->Right,Depth);
	if(Depth == 0)
		printf("%d\t", Root->Info);
}

//	Đếm Các Giá Trị Từ A Đến B
//	%param NodeAddress Root
//	%param int A
//	%param int B
//	%return int 
int countAtoB(NodeAddress Root, ItemType A,ItemType B)
{
	if (!Root) return 0;
	int LeftCount = countAtoB(Root->Left,A,B);
	int RightCount = countAtoB(Root->Right,A,B);
	if(Root->Info >= A && Root->Info <= B)
		return LeftCount + RightCount + 1;
	return LeftCount + RightCount;
}

//	Đếm Chiều Cao Của Cây
//	%param NodeAddress Root
//	%return int 
int heightTree(NodeAddress Root)
{
	if (!Root) return 0;
	int LeftHeight = heightTree(Root->Left);
	int RightHeight = heightTree(Root->Right);
	if(LeftHeight > RightHeight)
		return LeftHeight + 1;
	return RightHeight + 1;
}

//	Tổng Giá Trị Chẵn Có Trong Cây
//	%param NodeAddress Root
//	%return int 
int sumSoChan(NodeAddress Root)
{
	if (!Root) return 0;
	int LeftSum = sumSoChan(Root->Left);
	int RightSum = sumSoChan(Root->Right);
	if(Root->Info % 2 == 0)
		return LeftSum + RightSum + Root->Info;
	return LeftSum + RightSum;
}