3. Написать процедуру, которая выполняет вставку компоненты по заданному ключу.

include <stdio.h>

#include <stdlib.h>

#define MyType int

//Будем считать, что ключ в нашем случае - это эзначение типа int.

//Хранение значений -в виде двоичного однонаправленного дерева. Левое поддерево - данные, со значением ключа меньше, чем вершина, прваое - большим, чем вершина.

typedef struct element //элемент-вершина дерева.

{

int key;

struct element * left_el;

struct element * right_el;

MyType val;

} MyElement;

typedef struct

{

MyElement * tree_root; //корень;

int size;

} MyMap; //сама структура хранилища.

MyMap initNewMap()

{

MyMap mm;

mm.tree_root=NULL;

mm.size=0;

return mm;

}

int add_element(MyMap * mm, int k, MyType el) //добавить пару ключ-значение

{

MyElement * new_el = malloc(sizeof(MyElement));

if(new_el)

{

new_el->key=k;

new_el->val=el;

new_el->left_el=NULL;

new_el->right_el=NULL;

if(mm->tree_root==NULL)

{

mm->tree_root=new_el;

mm->size++;

return 0;

}

if(!paste_element(new_el, mm->tree_root))

{

mm->size++;

//printf("SIZE: %d \n", mm->size);

return 0;

}

else

{

printf("ERROR!\n");

}

}

else

{

return -1;

}

}

int paste_element(MyElement * me, MyElement * root) //рекурсивная функция вставки. 0 - в случае успеха, -1 - ошибка

{

if(root==NULL)

{

return -1;

}

if(me->key==root->key)

{

root->val=me->val;

return 0;

//printf("ALREADY EXIST!\n"); //Значиение с совпадающим ключем заменяет текущее

}

if(me->key<root->key)

{

if(root->left_el==NULL)

{

//printf("ADD LEFT!\n");

root->left_el=me;

return 0;

}

else

root=root->left_el;

}

if(me->key>root->key)

{

if(root->right_el==NULL)

{

//printf("ADD Right!\n");

root->right_el=me;

return 0;

}

else

root=root->right_el;

}

paste_element(me, root);

}

MyType get_value(MyMap *mm, int key)

{

return find_element(key, mm->tree_root);

}

MyType find_element(int key, MyElement * root)

{

if(root==NULL)

{

return -1;

}

if(key==root->key)

return root->val;

else

{

if(key<root->key)

{

if(root->left_el==NULL)

{

return -1;

}

else

root=root->left_el;

}

if(key>root->key)

{

if(root->right_el==NULL)

{

return -1;

}

else

root=root->right_el;

}

find_element(key, root);

}

}

int main(void)

{

MyMap m_map = initNewMap();

add_element(&m_map, 12, 13);

add_element(&m_map, 15, 14);

add_element(&m_map, 14, 16);

add_element(&m_map, 15, 12);

add_element(&m_map, 19, 123);

add_element(&m_map, 39, 121);

printf ("VALUE 15: %d\n",get_value(&m_map, 15));

printf ("VALUE 19: %d\n",get_value(&m_map, 19));

printf ("VALUE 12: %d\n",get_value(&m_map, 12));

printf ("VALUE 12: %d\n",get_value(&m_map, 552));

return 0;

}