#include<stdio.h>
#include<conio.h>
#include<iostream>
#include<stdlib.h>
#include<fstream>
using namespace std;
#define space 5


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);
NodeAddress findNodeX(NodeAddress& t, ItemType x);
void traverseTree(NodeAddress n);
bool deleteTree(NodeAddress& root);
bool insertNode(NodeAddress& t, NodeAddress p);
NodeAddress findNodeReplace(NodeAddress& p);
NodeAddress deleteNode(NodeAddress root, ItemType x);

//Other
void docFile(BinarySearchTree& bt, const char* filename);
void showNode(Node* p);
void traverseLNR(Node* root);
bool ktSoHoanThien(ItemType n);
void showSoHoanThien(Node* root);

// Draw Tree
int _print_t(NodeAddress tree, int is_left, int offset, int depth, char s[50][255]);
void print_t(NodeAddress tree);

int main()
{
	ItemType DataTree[] = { 25,3,7,5,32,81,10,34,53,44,43,23,53,6,26,14,43,65,89,40,59,12,4,23,53,47,57,57,58,16,39,41,58,46,31,29,99,2,1 };
	BinarySearchTree Tree;
	InitTree(Tree);
	for (int i = 0; i < ((int)sizeof(DataTree)) / sizeof(int); i++)
	{
		insertNode(Tree.Root, createNode(DataTree[i]));
		//        getchar();
		//        print_t(Tree.Root);

	}
	print_t(Tree.Root);
	//    printf("\n\n");
	//    deleteNode(Tree.Root, 53);
	//    print_t(Tree.Root);
	printf("\n\n");
	puts("\nPress any key to continue ... ");
	getchar();
	return 1;
}

// Init Binary Search Tree Node
void InitTree(BinarySearchTree& x)
{
	x.Root = NULL;
}


// Create Node
NodeAddress createNode(ItemType x)
{
	NodeAddress p = new Node;
	if (p == NULL) return NULL;
	p->Left = p->Right = NULL;
	p->Info = x;
	return p;
}

// Find for Node by X value in Search Binary Tree
NodeAddress findNodeX(NodeAddress& t, ItemType x)
{
	if (!t) return NULL;
	if (t->Info == x) return t;
	if (t->Info > x)return findNodeX(t->Left, x);
	else return findNodeX(t->Right, x);
}

// Traverse Binary Tree Search
void traverseTree(NodeAddress n)
{
	if (!n) return;
	traverseTree(n->Left);
	printf("%d\t", n->Info);
	traverseTree(n->Right);
}

// Delete Tree
bool deleteTree(NodeAddress& root)
{
	if (!root) return false;
	deleteTree(root->Left);
	deleteTree(root->Right);
	delete root;
	return true;

}

// Insert Node into Binary Tree Search
bool insertNode(NodeAddress& t, NodeAddress p)
{
	if (p == NULL) return false;
	if (!t) {
		t = p;
		return true;
	}
	if (t->Info == p->Info) return false;
	if (p->Info < t->Info) insertNode(t->Left, p);
	else insertNode(t->Right, p);
	return true;

}

// Delete Note in Binary Search Tree
NodeAddress deleteNode(NodeAddress root, ItemType x)
{
	if (!root) return root;
	if (root->Info > x)
		root->Left = deleteNode(root->Left, x);
	else if (root->Info < x)
		root->Right = deleteNode(root->Right, x);
	else {
		if (!root->Left)
		{
			NodeAddress NewRoot = root->Right;
			free(root);
			return NewRoot;
		}
		else if (!root->Right)
		{
			NodeAddress NewRoot = root->Left;
			free(root);
			return NewRoot;
		}
		else {
			NodeAddress rp = findNodeReplace(root);
			root->Info = rp->Info;
			root->Right = deleteNode(root->Right, root->Info);
		}

	}
	return root;
}

// Find Node Minimum on Left Child Tree and Replace in Binary Search Tree
NodeAddress findNodeReplace(NodeAddress& p)
{
	NodeAddress f = p, rp = p->Right;
	while (rp->Left != NULL)
	{
		f = rp;
		rp = rp->Left;
	}
	p->Info = rp->Info;
	if (f == p) f->Right = rp->Right;
	else f->Left = rp->Right;
	return rp;
}


// Other

void docFile(BinarySearchTree& bt, const char* filename)
{
	ifstream in;
	in.open(filename);
	ItemType x;
	while (in >> x)
	{
		insertNode(bt.Root, createNode(x));
	}
}
void showNode(Node* p)
{
	printf("%4d", p->Info);
}

// Duyet ds theo LNR
void traverseLNR(Node* root)
{

	if (root == NULL) return;
	traverseLNR(root->Left);
	showNode(root);
	traverseLNR(root->Right);
}

bool ktSoHoanThien(ItemType n)
{
	ItemType sum = 0;
	for (int i = 1; i < n; i++)
	{
		if (n % i == 0)
			sum += i;
	}
	if (sum == n && sum != 0)
		return true;

	return false;
}

void showSoHoanThien(Node* root)
{
	if (root == NULL) return;
	showSoHoanThien(root->Left);
	if (ktSoHoanThien(root->Info))
		printf("%4d", root->Info);
	showSoHoanThien(root->Right);
}

void Menu()
{

	printf("\n=============== MENU =============");
	printf("\n* 1. Tao cay NPTK tu File        *");
	printf("\n* 2. Duyet cay theo LNR          *");
	printf("\n* 3. Show so hoan thien          *");
	printf("\n* 0. Ket thuc!                   *");
	printf("\n==================================");

}

void process()
{
	ItemType choose, x;
	Node* p;
	BinarySearchTree bt;
	InitTree(bt);
	do
	{
		Menu();
		printf("\nBan hay chon chuc nang (tu 0 -> 3): ");
		scanf_s("%d", &choose);
		switch (choose)
		{
		case 1:
		{
			docFile(bt, "../Tree/Text.txt");
			printf("\nDoc file thanh cong!");
			break;
		}
		case 2:
		{
			printf("\nDuyet cay theo LNR");
			traverseLNR(bt.Root);
			break;
		}
		case 3:
		{
			printf("\nSo hoan thien trong cay:");
			showSoHoanThien(bt.Root);
			break;
		}
		case 0:
		{
			exit(1);
		}
		}
	} while (1);
}


// Draw Tree

int _print_t(NodeAddress tree, int is_left, int offset, int depth, char s[50][255])
{
	char b[50];
	int width = 3;

	if (!tree) return 0;

	sprintf_s(b, "%03d", tree->Info);

	int left = _print_t(tree->Left, 1, offset, depth + 1, s);
	int right = _print_t(tree->Right, 0, offset + left + width, depth + 1, s);

	for (int i = 0; i < width; i++)
		s[2 * depth][offset + left + i] = b[i];

	if (depth && is_left) {

		for (int i = 0; i < width + right; i++)
			s[2 * depth - 1][offset + left + width / 2 + i] = '-';

		s[2 * depth - 1][offset + left + width / 2] = '+';
		s[2 * depth - 1][offset + left + width + right + width / 2] = '+';

	}
	else if (depth && !is_left) {

		for (int i = 0; i < left + width; i++)
			s[2 * depth - 1][offset - width / 2 + i] = '-';

		s[2 * depth - 1][offset + left + width / 2] = '+';
		s[2 * depth - 1][offset - width / 2 - 1] = '+';
	}
	return left + width + right;
}

void print_t(NodeAddress tree)
{
	char s[50][255];
	for (int i = 0; i < 50; i++)
		sprintf_s(s[i], "%200s", " ");

	_print_t(tree, 0, 0, 0, s);

	for (int i = 0; i < 25; i++)
		printf("%s\n", s[i]);
}