/ Bintree.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"
#include <cstdlib>
#include <iostream>
#include <algorithm>

struct Node
{
    int contain; //содержимое узла
    Node *left; //указатель на левого потомка
    Node *right; //указатель на правого потомка
    Node *parent;  //указатель на предка
};

void tree_print_simple(Node *node, int level)
{
    for (int i = 0; i < level; i++)
        std::cout << "  ";
    if (!node)
    {
        std::cout << "-\n";
        return;
    }
    std::cout << node->contain << '\n';
    if (node->left || node->right)
    {
        tree_print_simple(node->left, level+1);
        tree_print_simple(node->right, level+1);
    }
}

Node *key_search(int key_s, Node *origin)
{
    Node *node = origin;
    while (node)
    {
        if (node->contain == key_s)
            return node;
        if (node->contain > key_s)
            node = node->left;
        else
            node = node->right;
    }
    return 0;
}

void key_add(int key_a, Node *origin)
{

    Node *node = new Node;
    node->contain = key_a;
    node->left = NULL;
    node->right = NULL;
    Node **a = &origin, *b = 0;
    while (*a)
    {
        b = *a;
        if (node->contain < (*a)->contain)
            a = &(*a)->left;
        else
            a = &(*a)->right;
    }
        *a = node;
        node->parent = b;
}

int min_key(Node *origin)
{
    Node *node = origin;
    if (!node)
        return -1;
    while (node->left)
        node = node->left;
    return node->contain;
}

void key_delete(int key_d, Node *origin)
{
    Node *node = origin;
    while (node)
    {
        if (node->contain == key_d)
        {
            Node *ptr;
            if (node->left == 0)
                ptr = node->right;
            else
                ptr = node->left;
            if (node == (node->parent)->left)
                node->parent->left = ptr;
            else
                node->parent->right = ptr;
            ptr->parent = node->parent;
            delete node;
            return;
        }
        if (node->contain > key_d)
            node = node->left;
        else
            node = node->right;
    }
}

void traverse(Node *node)
{
    if (!node) return;
    std::cout << node->contain << ' ';
    traverse(node->left);
    traverse(node->right);
}

int main()
{
    int key_s, key_a, key_d;
    std::cout << "Enter keys for binary tree: ";
    Node *origin = 0;
    for (int i = 0; i < 25; i++)
    {
        Node *node = new Node;
        std::cin >> node->contain;
        node->left = 0;
        node->right = 0;

        Node **a = &origin, *b = 0;
        while (*a)
        {
            b = *a;
            if (node->contain < (*a)->contain)
                a = &(*a)->left;
            else
                a = &(*a)->right;
        }
        *a = node;
        node->parent = b;
    }

    tree_print_simple(origin, 0);

    std::cout << "Enter needed key: ";
    std::cin >> key_s;
        Node *p = key_search(key_s, origin);
        if (p)
            std::cout << "Needed key is found! \n";
        else
            std::cout << "Sorry, no such key! \n";

    std::cout << "Enter the key, which you want to add: ";
    std::cin >> key_a;

    key_add(key_a, origin);

    tree_print_simple(origin, 0);

    if (min_key(origin))
        std::cout << "Minimal key is " << min_key(origin)<<'\n';
    else
        std::cout << "Didn't manage to find minimal key!\n";

    std::cout << "Enter the key, which you want to delete: ";
    std::cin >> key_d;

    key_delete(key_d, origin);

    tree_print_simple(origin, 0);

    traverse(origin);

    std::cout << "\n";
    system("pause");
}