// ConsoleApplication8.cpp : Defines the entry point for the console application.
//

#include"stdafx.h"
#include <iostream>
#include<windows.h>
using namespace std;

struct BSTnode {
	BSTnode * left;
	BSTnode * right;
	BSTnode* up;
	int key;
};

void addNode(BSTnode **root, int key) {
	system("CLS");
	BSTnode * newNode = new BSTnode();
	newNode->key = key;
	BSTnode * temp = new BSTnode();
	temp = *root;
	if (*root == NULL) {
		*root = newNode;
	}
	else if (key > temp->key) {
		if (temp->right) {
			addNode(&temp->right, key);
		}
		else {
			newNode->up = temp;
			temp->right = newNode;
		}
	}
	else if (key < temp->key) {
		if (temp->left) {
			addNode(&temp->left, key);
		}
		else {
			newNode->up = temp;
			temp->left = newNode;
		}
	}
}

void maxNode(BSTnode ** root) {
	BSTnode * temp = (*root);
	while (temp->right)
		temp = temp->right;
	cout<< temp->key;
}

void minNode(BSTnode ** root) {
	BSTnode * temp = (*root);
	while (temp->left)
		temp = temp->left;
	cout << temp->key;
}

void in_order(BSTnode * root) {
	if (root->left)
		in_order(root->left);
	cout << root->key << " ";
	if (root->right)
		in_order(root->right);
	if (root == NULL)
		cout << "Jebac";
}

BSTnode * searchNode(BSTnode ** root,int key) {
	BSTnode*temp = (*root);
	while (temp) {
		if (key == temp->key)
			return temp;
		else if (key < temp->key)
			temp = temp->left;
		else if (key > temp->key)
			temp = temp->right;
	}
	return NULL;
}
BSTnode * BSTminnode(BSTnode * root)
{
	BSTnode *temp = root;

	while (temp->left)
		temp = temp->left;

	return temp;
}
BSTnode * BSTsucc(BSTnode * node)
{
	if (node->right)
		return BSTminnode(node->right);

	BSTnode * y;

	do
	{
		y = node;
		node = node->up;
	} while (node && (node->left != y));

	return node;
}

void deleteNode(BSTnode * &root, BSTnode * node) {
			BSTnode * Y, *Z;

			if (node)
			{
				// Jeśli X nie ma synów lub ma tylko jednego, to Y wskazuje X
				// Inaczej Y wskazuje następnik X

				Y = !node->left || !node->right ? node : BSTsucc(node);

				// Z wskazuje syna Y lub NULL

				Z = Y->left ? Y->left : Y->right;

				// Jeśli syn Y istnieje, to zastąpi Y w drzewie

				if (Z) Z->up = Y->up;

				// Y zostaje zastąpione przez Z w drzewie

				if (!Y->up) root = Z;
				else if (Y == Y->up->left)
					Y->up->left = Z;
				else
					Y->up->right = Z;

				// Jeśli Y jest następnikiem X, to kopiujemy dane

				if (Y != node) node->key = Y->key;

				delete Y;
			}
}

int main()
{
	BSTnode * root = NULL;
	BSTnode*x;
	root = NULL;
	int wybor, a, b,value;
	do {
		cout << endl;
		cout << "------------------------------------------" << endl;
		cout << "1. addNode " << endl;
		cout << "2. maxNode " << endl;
		cout << "3. minNode " << endl;
		cout << "4. searchNode " << endl;
		cout << "------------------------------------------" << endl;
		cout << "Wybor: ";
		cin >> wybor;
		switch (wybor) {
		case 1:
			cout << "Jaki element chcesz dodac do drzewa: ";
			cin >> a;
			addNode(&root, a);
			break;

		case 2:
			cout << "Najwiekszy element to: ";
			maxNode(&root);
			Sleep(3000);
			system("CLS");
			break;

		case 3:
			cout << "Najmniejszy element to: ";
			minNode(&root);
			Sleep(3000);
			system("CLS");
			break;

		case 4:
			cout << "Szukany element: ";
			cin >> b;
			cout << "Wezel: "<< searchNode(&root, b);
			Sleep(3000);
			system("CLS");
			break;

		case 5:
			cin >> value;
			x = searchNode(&root, value);
			deleteNode(root, x);
		}
		cout << "Elementy na drzewie: ";
		in_order(root);
	} while (wybor != 10);

	return 0;
}