Jak przechowywać drzewa nadrzędny-podrzedny

0

Witajcie.

Mam problem ze stworzeniem pętli do następującego zadania.

Mamy tabele połączeń:
over - nadrzedny element
sub - podrzedny element


Array
(
    [0] => Array
        (
            [over] => 0
            [sub] => 1
        )

    [1] => Array
        (
            [over] => 1
            [sub] => 2
        )
    [2] => Array
        (
            [over] => 1
            [sub] => 3
        )
    [3] => Array
        (
            [over] => 2
            [sub] => 4
        )
    [4] => Array
        (
            [over] => 2
            [sub] => 5
        )
    [5] => Array
        (
            [over] => 4
            [sub] => 6
        )

)

Nie mogę rozgryźć jak zrobić z tego i jak skonstruować tabelę do tego:
user image

Dziekuję za sugestię

0

Każdy parzysty element drzewa o wartości n (prócz 0) ma dwójkę dzieci, jedno o wartości n+2, a drugie o wartości n+3. Chyba o to ci chodzi, ale nie dam sobie uciąć głowy xD

Więc napiszmy przykładowy (nie jest ładny może coś lekko zabugowałem, nie pisze zbytnio w cpp), ale idea:

#include <vector>

using std::vector;

struct Node
{
    Node* firstChild;
    Node* secondChild;
    Node* parent;
    int value;
};

int main(void)
{
         vector<Node> tree;

         //x jako ilość elementów w drzewie
         int x;         
         wczytaj(x);

         for(int i = 0; i < x; i++)
         {
               Node n;
               tree.push_back(n);
         }

         for(int i = 0; i < x; i++)
         {
                if(i == 0)
                {
                      tree[i].firstChild = tree[i+1];
                      tree[i].secondChild = NULL;
                      tree[i].parent = NULL;
                      tree[i].value = i;
                }
                else if(i == 1)
                {
                      tree[i].firstChild = tree[i+1];
                      tree[i].secondChild = tree[i+2];
                      tree[i].parent = tree[i-1];
                      tree[i].value = i;
                }
                else if(i == 2)
                {
                      tree[i].firstChild = tree[i+2];
                      tree[i].secondChild = tree[i+3];
                      tree[i].parent = tree[i-1];
                      tree[i].value = i;
                }
                else if(i == x - 1)
                {
                      tree[i].firstChild = NULL;
                      tree[i].secondChild = NULL;
                      tree[i].parent = i % 2 == 0 ? tree[i-2] : tree[i-3];
                      tree[i].value = i;
                }
                else if(i % 2 == 0)
                {
                      tree[i].firstChild = tree[i+2];
                      tree[i].secondChild = tree[i+3];
                      tree[i].parent = tree[i-2];
                      tree[i].value = i;
                }
                else
                {
                      tree[i].firstChild = NULL;
                      tree[i].secondChild = NULL;
                      tree[i].parent = tree[i-3];
                      tree[i].value = i;
                }
         }
}
0
Wybitny Lew napisał(a):

Witajcie.

Mam problem ze stworzeniem pętli do następującego zadania.

Mamy tabele połączeń:
over - nadrzedny element
sub - podrzedny element


Array
(
    [0] => Array
        (
            [over] => 0
            [sub] => 1
        )

    [1] => Array
        (
            [over] => 1
            [sub] => 2
        )
    [2] => Array
        (
            [over] => 1
            [sub] => 3
        )
    [3] => Array
        (
            [over] => 2
            [sub] => 4
        )
    [4] => Array
        (
            [over] => 2
            [sub] => 5
        )
    [5] => Array
        (
            [over] => 4
            [sub] => 6
        )

)

Nie mogę rozgryźć jak zrobić z tego i jak skonstruować tabelę do tego:
user image

Dziekuję za sugestię

Przecież to jest to samo, tylko jedno w postaci listy połączeń a drugie w postaci (obrazka) drzewa. Możesz sprecyzować swoje pytanie? Co dokładnie chcesz osiągnąć? Chcesz mieć kod który skonstruuje ci drzewo z listy połączeń?

1 użytkowników online, w tym zalogowanych: 0, gości: 1