Reprezentacja układu cyfrowego w drzewie

pytanie zadane 21 stycznia 2020 w C i C++ przez Agnes Użytkownik (990 p.)

Dopiero zaczynam uczyć się o drzewach i nie wiem co zrobić gdyby trzeba było przedstawić w postaci drzewa taki układ:

Jak by to miało wyglądać? Który węzeł byłby rodzicem dla węzła trzeciego? Węzeł ten trzeba jakoś połączyć z 2 i 4, ale przecież nie może on mieć dwóch rodziców.

komentarz 22 stycznia 2020 przez j23 Mędrzec (194,920 p.)

Może nie patrz na to jak na klasycznie drzewo jeden rodzić -> dwójka dzieci.

komentarz 22 stycznia 2020 przez Agnes Użytkownik (990 p.)

Muszę patrzeć na to jak na drzewo, taki jest warunek zadania. A są drzewa, gdzie jeden węzeł może mieć dwóch rodziców?

komentarz 22 stycznia 2020 przez j23 Mędrzec (194,920 p.)
edycja 22 stycznia 2020 przez j23

Pisałem o klasycznym drzewie binarnym. Całość możesz zrealizować w postaci klas reprezentujących bramki AND i NOT. Każda bramka ma piny wejściowe, do których można podłączyć dowolną liczbę innych bramek. Coś w ten deseń:

struct Gate {
    virtual void connect(unsigned, Gate*) = 0;
    virtual ~Gate() {};
};

struct AND : public Gate {

    void connect(unsigned inPin, Gate* gate) override
    {
        if (inPin > 1) return;
        mInput[inPin].push_back(gate);
    }

private:
    std::vector<Gate*> mInput[2];
};

struct NOT : public Gate {

    void connect(unsigned inPin, Gate* gate) override
    {
        if (inPin > 0) return;
        mInput.push_back(gate);
    }

private:
    std::vector<Gate*> mInput;
};

komentarz 23 stycznia 2020 przez Agnes Użytkownik (990 p.)

Nie mogę używać vectora i nie moze to być napisane obiektowo

komentarz 23 stycznia 2020 przez mokrowski Mędrzec (155,460 p.)

@Agnes, 3 jest korzeniem drzewa bo do niego spływają wszystkie sygnały. 1 i 6 jest "na najniższym piętrze".

komentarz 23 stycznia 2020 przez Agnes Użytkownik (990 p.)

Ale wtedy 5 miałoby dwóch rodziców - 2 i 4, nie?

Możesz narysować jak to widzisz?

komentarz 23 stycznia 2020 przez mokrowski Mędrzec (155,460 p.)

No miało by :) Ale odwracając problem. Czy z 2 i 4 nie można prowadzić akurat do tego samego węzła 5? :)

To tylko kwestia implementacji obsługi. A w wymaganiach nie widzę by to miało być drzewo jakiegoś konkretnego rodzaju. Z rodzica w tej implementacji będzie zawsze referencja maksymalnie na 2 potomków. Parsowanie stanu będzie odpytaniem potomków a nie "wypychaniem z potomków" danych do rodzica.

Chyba że czegoś jeszcze o problemie nie wiem?

Zobacz. Pytamy jaki jest stan 3. 3 będzie wiedziało jak dowie się od 2 i 4. 2 będzie wiedziało jaki jest jego stan jeśli zapyta (pośrednio) w 5. 5 się dowie jak (pośrednio) odpyta przełączniki. Które to przełączniki będą także częściową informacją dla 2 i 4. Da się...

komentarz 23 stycznia 2020 przez Agnes Użytkownik (990 p.)

Czyli jeśli prowadzi się od 2 i 4 do tego samego węzła 5 to nie jest równoznaczne z tym, że 5 ma dwóch rodziców? Czy drugie to nie jest efekt pierwszego? Jak to możliwe?

komentarz 23 stycznia 2020 przez mokrowski Mędrzec (155,460 p.)
edycja 23 stycznia 2020 przez mokrowski

Ja zadaję sobie pytanie do jakich celów ma służyć to drzewo. Jeśli do określenia stanu sygnałów przy ustawionych przełącznikach, to można to zrobić jak naszkicowałem.

Jeśli pytasz o implementację, to powiedz... to rodzic ma wskaźniki/referencje do dzieci czy odwrotnie? IMHO w moim opisie to rodzic ma te odniesienia (1 lub 2) do poszczególnych węzłów potomnych.

Wybrałaś implementację drzewa do tego problemu. Przy tak narzuconych ograniczeniach, to jest jedno z możliwych wyjść. Zachowanie drzewa i zezwolenie na stan odniesień dla 2 węzłów nadrzędnych. Inne (i częste dla takich problemów) to graf skierowany ale rozumiem że tego tu nie wolno/nie taki był wybór.