q// wezel ktory nie ma rodzica jest korzeniem
// wezel ktory nie ma dziecka jest liściem
// dzielimy drzewo na poziomy

// preorder (root, left, right)
// inorder (left, root, right)
// postorder (left, right, root)

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <string>
using namespace std;

class node // sam w sobie węzeł 
{
public:

	int value;
	node* left;
	node* right;

	node();
};

node::node()
{
	value = 0;
	left = nullptr;
	right = nullptr;
}

class binaryTree // klasa obsługująca funkcje drzewa 
{
private:

	node* root;

	void inOrderPrint(node* element);
	void postOrderPrint(node* element);
	void preOrderPrint(node* element);
	void destroyTree(node* element);
	void insert(int key, node* element);
	

public:

	binaryTree();
	~binaryTree();

	void readDataOfADataFromFile();
	void insert(int key); // dodanie elementu do drzewa
	void destroyTree(); // kasowanie drzewa
	void inOrderPrint();
	void postOrderPrint();
	void preOrderPrint();
};



binaryTree::binaryTree() // na samym początku drzewo będzie puste więc root będzie nullptr
{
	root = nullptr;
}

binaryTree::~binaryTree() // podczas uruchomienia destruktora kasowana jest cała zawartość sterty (czyli tam gdzie są węzły drzewa)
{
	destroyTree();
	cout << "Usuwanie drzewa..." << endl;
}


void binaryTree::destroyTree()
{
	destroyTree(root);
}

void binaryTree::destroyTree(node* element)
{
	if (element != nullptr)
	{
		destroyTree(element->left);
		destroyTree(element->right);
		delete element;
	}
}

void binaryTree::insert(int key, node* element)
{
	if (key < element->value) // elementy mniejsze lądują na lewej stronie, a większą bądź równe na prawej
	{
		if (element->left != nullptr) // jeżeli mamy wartość mniejszą i chcemy ją zapisać jako nowy węzeł 
		{							  // ale okaże się, że wskaźnik do następnego elementu istnieje i ma wartość to musimy jeszcze raz wywołać funkcje rekursywnie aby przejść do następnego elementu i od niego stworzyć nowy węzeł
			insert(key, element->left); // tutaj rekursywne przejście do następnego elementu drzewa
		}
		else
		{
			element->left = new node(); // tworzymy nowy węzeł
			element->left->value = key;
			element->left->left = nullptr;
			element->left->right = nullptr;
		}
	}
	else if (key >= element->value) // analogicznie jak dla if(key < element>value)
	{
		if (element->right != nullptr)
		{
			insert(key, element->right);			
		}
		else
		{
			element->right = new node();
			element->right->value = key;
			element->right->right = nullptr;
			element->right->left = nullptr;
		}
	}
}

void binaryTree::insert(int key) // funkcja do ogarnięcia czy drzewo jest puste czy nie
{
	if (root != nullptr)
	{
		insert(key, root); // jeżeli nie jest pusta to lecimy z prywatną metodą insert(int key, node* element), która leci po całym drzewie szukając odpowiedniego węzła do stworzenia drzewa
	}
	else // jeżeli drzewo jest puste to tworzymy pierwszy węzeł drzewa (korzeń)
	{
		root = new node(); 
		root->value = key;
		root->left = nullptr;
		root->right = nullptr;
	}
}

void binaryTree::inOrderPrint(node* element) // (left, root, right)
{

	if (element == nullptr) // jeżeli drzewo jest puste, przy okazji warunek wyjścia z rekursji
	{
		return;
	}
	inOrderPrint(element->left);
	cout << element->value << endl;
	inOrderPrint(element->right);
}

void binaryTree::inOrderPrint() // (left, root, right)
{
	inOrderPrint(root);
	cout << endl;
}


void binaryTree::postOrderPrint(node* element) // (left, right, root)
{
	if (element == nullptr) // jeżeli drzewo jest puste, przy okazji warunek wyjścia z rekursji
	{
		return;
	}
	postOrderPrint(element->left);
	postOrderPrint(element->right);
	cout << element->value << endl;


}

void binaryTree::postOrderPrint() // (left, right, root)
{
	postOrderPrint(root);
	cout << endl;
}

void binaryTree::preOrderPrint(node* element) // (root, left, right)
{
	if (element == nullptr) // jeżeli drzewo jest puste, przy okazji warunek wyjścia z rekursji
	{
		return;
	}
	cout << element->value << endl;
	preOrderPrint(element->left);
	preOrderPrint(element->right);
}

void binaryTree::preOrderPrint() // (root, left, right)
{
	preOrderPrint(root);
	cout << endl;
}

void binaryTree::readDataOfADataFromFile()
{
	string line;
	int number;
	fstream plik;

	plik.open("lista.txt", ios::in); // powiązanie strumienia z plikiem

	if (plik.good() == false) // jezeli jest zamkniety to error
	{
		cout << "Plik nie istnieje" << endl;
		exit(EXIT_FAILURE);
	}
	else // jezeli nie lecimy
	{
		while (!plik.eof()) // działa dopóty, dopóki coś sie nie "zepsuje"
		{
			getline(plik, line, ' ');
			number = atoi(line.c_str());

			insert(number); // funkcja zrobi z tego co wczytalismy liste
		}
	}
	plik.close(); // zamykanie
}


int main()
{	
	binaryTree* tree = new binaryTree();

	tree->readDataOfADataFromFile();

	tree->preOrderPrint(); // (root, left, right), 15, 6, 3, 2, 4, 7, 13, 9, 18, 17, 20 (ok, dobrze działa) (poza zerem)
	//tree->inOrderPrint(); // (left, root, right), 2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20 (ok, dobrze działa) (poza zerem)
	//tree->postOrderPrint(); // (left, right, root), 2, 4, 3, 9, 13, 7, 6, 17, 20, 18, 15 (ok, dobrze działa) (poza zerem)

	delete tree; // trzeba to jawnie zainicjować ponieważ wtedy wywoła się domyślny destruktor bez ciała


	return 0;
}