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

using namespace std;

struct tree {
    int key;
    tree* left;
    tree* right;
} *root = NULL;

const int n = 10;//максимум брой елементи в граф

struct link //spisak ot grafa
{
    int key;
    link *next;
}
*gr[n]; //масив от указатели


void add_tree(int n, tree *&t);
void obhozdane_tree(tree *t);

void inti_graph(link *gr[n]);
int search_node_graph(link *gr[n], int c);
int search_arc_graph(link *gr[n], int c1, int c2);
void add_node_graph(link *gr[n], int c);
void add_arc_graph(link *gr[n], int c1, int c2);
void print_graph(link *gr[n]);

void main()
{
    inti_graph(gr);

    int broj;
    cout << "Broj elementi na darvoto: ";
    cin >> broj;

    while (broj < 1) { //ако потребителя въведе число по-малко от 1 за брой, накарай го да въвежда пак число
        cout << "Nevaliden broj" << endl;
        cout << "Broj elementi na darvoto: ";
        cin >> broj;
    }

    int number;
    cout << "Vavedete elementi na darvoto: " << endl;

    for (int i = 0; i < broj; i++)
    {
        cin >> number;
        add_tree(number, root);
    }

    obhozdane_tree(root);//конвертра дървото в граф
    cout << "Spisacite na grafa: " << endl;
    print_graph(gr);
}


//obhozdane prav red - корен, lqvo poddarvo dqsno poddarvo
void obhozdane_tree(tree *t)
{
    if (t)
    {
        if (t->left != NULL) {
            add_arc_graph(gr, t->key, t->left->key);
        }

        if (t->right != NULL) {
            add_arc_graph(gr, t->key, t->right->key);
        }

        obhozdane_tree(t->left);
        obhozdane_tree(t->right);
    }
}

void add_tree(int n, tree *&t) //dobavqne na listo
{
    if (t == NULL)
    {
        t = new tree;
        t->key = n;
        t->left = t->right = NULL;
    }
    else
    {
        if (t->key < n)
        {
            add_tree(n, t->right);
        }
        else
        {
            add_tree(n, t->left);
        }
    }
}

// Инициализация
void inti_graph(link *gr[n])
{
    for (int i = 0; i < n; i++)
        gr[i] = NULL;
}

//Търсене на връх
int search_node_graph(link *gr[n], int c)
{
    int flag = 0;

    for (int i = 0; i < n; i++)
    {
        if (gr[i])
        {
            if (gr[i]->key == c)
                flag = 1;
        }
    }
    return flag;
}

//Търсене на дъга
int search_arc_graph(link *gr[n], int c1, int c2)
{
    int flag = 0;

    if (search_node_graph(gr, c1) && search_node_graph(gr, c2))
    {
        int i = 0;

        while (gr[i]->key != c1)
            i++;

        link *p = gr[i];

        while (p->key != c2 && p->next != NULL)
            p = p->next;

        if (p->key == c2)
            flag = 1;
    }

    return flag;
}

//Добавяне на връх
void add_node_graph(link *gr[n], int c)
{
    if (search_node_graph(gr, c))
        cout << "Sashtestvuva vruh s tazi stojnost" << endl;
    else
    {
        int i = 0;
        while (gr[i] && i < n)
            i++;

        if (gr[i] == NULL)
        {
            gr[i] = new link();
            gr[i]->key = c;
            gr[i]->next = NULL;
        }
        else
            cout << "Prepalvane na strukturata" << endl;
    }
}

//добавяне на дъга
void add_arc_graph(link *gr[n], int c1, int c2)
{
    if (search_arc_graph(gr, c1, c2))
        cout << "Dagata veche sashtestvuca";
    else
    {
        if (!search_node_graph(gr, c1))
            add_node_graph(gr, c1);
        if (!search_node_graph(gr, c2))
            add_node_graph(gr, c2);

        int i = 0;
        while (gr[i]->key != c1)
            i++;

        link *p = new link;
        p->key = c2;
        p->next = gr[i]->next;
        gr[i]->next = p;
    }
}

void print_graph(link *gr[n])
{
    for (int i = 0; i < n; i++)
    {
        if (gr[i])
        {
            link *p = gr[i];

            while (p)
            {
                cout << p->key << "\t";
                p = p->next;
            }

            cout << endl;
        }
    }
}