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

#include "stdafx.h"
#include <iostream>
#include <cstring>

using namespace std;
struct node
{
    char* data = new char[1024];
    node* next;
};
node* make_linked_list(int n)
{
    node *beg;//указатель на первый элемент
    node *p, *r;//вспомогательные указатели
    beg = new(node);//выделяем память под первый элемент
    cout << "Ввод " << n << " значений информационного поля:" << endl;
    cin >> beg->data;//вводим значение информационного поля
    beg->next = 0;//обнуляем адресное поле
    p = beg;//ставим на этот элемент указатель p (последний элемент)
    for (int i = 0; i < n - 1; i++)
    {
        r = new(node);//создаем новый элемент
        cin >> r->data;
        r->next = 0;
        p->next = r;//связываем p и r
        //ставим на r указатель p (последний элемент)
        p = r;
    }
    return beg;//возвращаем beg как результат функции
}
void print_linked_list(node* beg)

{
    node* p = beg;//начало списка
    cout << "Однонаправленный список:" << endl;
    while (p != 0)
    {
        cout << p->data << " ";
        p = p->next;//переход к следующему элементу
    }
    cout << endl;
}
node* add_node(node* beg, int k)
//добавление элемента с номером k
{
    node *p = beg;//встали на первый элемент
    node *New = new(node);//создали новый элемент
    cout << "Ввод нового элемента: "; cin >> New->data;
    if (k == 0)//добавление в начало, если k=0
    {
        New->next = beg;
        beg = New;
        return beg;
    }
    for (int i = 0; i < k - 1 && p != 0; i++)
        p = p->next;//проходим по списку до(k-1) элемента или до конца
    if (p != 0)//если k-й элемент существует
    {
        New->next = p->next;//связываем New и k-й элемент
        p->next = New;//связываем (k-1)элемент и New
    }
    return beg;
}
/*find - функция для нахождения номера добавляемого элемента*/
int find(node* beg, char *s)
{
    node* p = beg;//начало списка
    int k = 1;
    while (p != 0, strcmp(p->data, s)){
        p = p->next;//переход к следующему элементу
        k++;
    }
    return k;
}
void delete_linked_list(node *beg)
{
    node* p = beg;//начало списка
    node* r = p->next;
    while (p != 0 && r != 0)
    {
        delete (p);
        p = r;
        r = p->next;
    }
    cout << endl;
}


struct dobly_node{
    int key;
    dobly_node *next;
    dobly_node *prev;
};
dobly_node *make_point(int key)
//создание одного элемента двунаправленного списка
{
    dobly_node *p = new(dobly_node);
    p->next = 0; p->prev = 0;//обнуляем указатели
    p->key = key;//выделение памяти под строку
    return p;
}
dobly_node *make_dobly_list(int n)//создание двунаправленного списка
{
    dobly_node *p, *beg;
    int a;
    cin >> a;
    beg = make_point(a);//создаем первый элемент
    beg->next = 0;//конца списка
    for (int i = 1; i<n; i++)
    {
        cin >> a;
        p = make_point(a);//создаем один элемент
        //добавление элемента в начало списка
        p->next = beg;//связываем р с первым элементом
        beg->prev = p;//связываем первый элемент с p
        beg = p;// p становится первым элементом списка
    }
    beg->prev = 0;//зануление начала списка
    return beg;
}
void print_dobly_list(dobly_node *beg)
{
    dobly_node *p = beg;
    cout << "Двунаправленный список: ";
    while (p != 0)
    {
        cout << p->key << " ";
        p = p->next;//переход к следующему элементу
    }
    cout << endl;
}
dobly_node *delete_even(dobly_node *beg, int n)
{
    dobly_node *p = beg, *r = 0, *del = 0;
    while (p->next != 0){
        if ((p->key % 2) == 0 && p->prev != 0){
            del = p;
            r = p->prev;
            p = del->next;
            p->prev = r;
            r->next = p;
            delete(del);
        }
        else if ((p->key % 2) == 0 && p->prev == 0){
            del = p;
            p = del->next;
            delete(del);
            p->prev = 0;
            beg = p;
        }
        else
            p = p->next;

    }
    if (p->key % 2 == 0)
        p = p->prev;
    p->next = 0;
    return beg;
}
void delete_dobly_list(dobly_node *beg)//удаление списка
{
    dobly_node *p, *r;
    p = beg;
    r = beg->next;
    while (p != 0 && r != 0)
    {
        delete(p);
        p = r;
        r = p->next;
    }
}

struct leaf
{
    char data;//информационное поле
    leaf *left;//адрес левого поддерева
    leaf *right;//адрес правого поддерева
};
leaf* first(char d)//формирование первого элемента дерева
{
    leaf* p = new leaf;
    p->data = d;
    p->left = 0;
    p->right = 0;
    return p;
}
leaf* Tree(int n, leaf *p)//создание идеально сбалансированного дерева
{
    leaf *r;
    char nl, nr;
    if (n == 0){ p = 0; return p; }
    nl = n / 2;
    nr = n - nl - 1;
    r = new leaf;
    cin >> r->data;
    r->left = Tree(nl, r->left);
    r->right = Tree(nr, r->right);
    p = r;
    return p;
}
void Print_tree(leaf*p)//печать дерева
{
    if (p)
    {
        cout << p->data << ' ';
        Print_tree(p->left);//переход к левому поддереву
        Print_tree(p->right);//переход к правому поддереву
    }
}
int Find_hight(leaf*p, int h)//нахождение высоты дерева
{
    if (p)
    {
        ++h;
        h = Find_hight(p->left, h);//переход к левому поддереву
    }
    return h;
}
void To_binary_tree(leaf*p)//преобразование идеально сбалансированного дерева в дерево поиска
{
    if (p)
    {
        char tmp;
        if (p->left && p->left->data > p->data)
        {
            tmp = p->data;
            p->data = p->left->data;
            p->left->data = tmp;
        }
        if (p->right && p->right->data < p->data)
        {
            tmp = p->data;
            p->data = p->right->data;
            p->right->data = tmp;
        }
        To_binary_tree(p->left);//переход к левому поддереву
        To_binary_tree(p->right);//переход к правому поддереву
    }
}


int main()
{
    setlocale(LC_ALL, "rus");
    cout << "Ввод начального кол-ва записей однонаправленного списка:";
    int n;
    cin >> n;
    node *beg = make_linked_list(n);
    print_linked_list(beg);
    cout << "Ввод элемента после которого будет добавляться новый элемент:";
    char* s = new char[1024];
    cin >> s;
    beg = add_node(beg, find(beg, s));
    print_linked_list(beg);
    delete_linked_list(beg);
    cout << "Ввод начального кол-ва записей двунаправленного списка:";
    cin >> n;
    dobly_node *start = make_dobly_list(n);
    print_dobly_list(start);
    start = delete_even(start, n);
    cout << "Удаление четных информационных полей..." << endl;
    print_dobly_list(start);
    delete_dobly_list(start);
    leaf *root = new leaf;
    cout << "Ввод кол-ва элементов идеально сбалансированного дерева: "; cin >> n;
    cout << "Ввод " << n << " элементов дерева:" << endl;
    root = Tree(n, root);
    cout << "Вывод идеально сбалансированного дерева:" << endl;
    Print_tree(root);
    cout << "\nВысота:" << Find_hight(root, 0) << endl;
    for (int i = 0; i < Find_hight(root, 0); ++i)
        To_binary_tree(root);
    cout << "Дерево поиска:" << endl;
    Print_tree(root);
    system("pause");
    return 0;
}