Jak wygląda drzewo n-arne?


(Lord218) #1

Witam.

Czy moglibyście podrzucić jakiś kod (najlepiej c++) jak wygląda zwykłe, najprostsze drzewo n-arne?

Takie na strukturze, albo klasie bez użycia STL'a itp.

Byłbym wdzięczny, gdyż nie mogę zrozumieć jak te drzewa działają.

Pozdrawiam.


(kostek135) #2

Jeśli bez STL'a to najprościej zacząc od napisnia jakiejś listy (linkowanej, czy swobodny dostęp - nie istotne). Załóżmy, że na nasze potrzeby to będzie List;

struct Node {
    ListNode* lista_dzieci; // obowiązkowe
    Node* rodzic; // nie obowiązkowe, ale w niektórych algorytmach (backtrack) przydatne
};

Nie mniej to naprawdę zależy czasami niektóre drzewa idzie zrobić na tablicy, np. kopiec. Ale to będzie takie najbardziej generyczne drzewo ogólnego przeznaczenia.


(Lord218) #3

Ok. Dzięki kostek.

Czy jak by coś to mogę tu wrzucić swój kod żebyście mi sprawdzili?

Z reszta przydałby się tu taki dział/poddział do sprawdzania poprawności kodu.

Dzięki jeszcze raz i pozdrawiam.


(kostek135) #4

Nie bardzo wiem, co chcesz, żeby tobie sprawdzić. Tu nie ma większej filozofii, ponad to co napisałem.


(Lord218) #5

Rozumiem, ale chodziło mi po prostu o to, czy jak napisze sobie drzewko i nóż coś mi nie zadziała to czy wtedy mi sprawdzicie?


(kostek135) #6

Myślę, że nie powinno być problemu. Tylko bądź precyzyjny z przykładami tego jaki jest wynik, a jaki powinien być według ciebie. Bo czasem coś może działać dobrze, tylko nie tak jak chcesz.


(Lord218) #7

A mógłby ktoś dać linka do jakiegoś przykładu drzewa i funkcji, która wstawia nowy element?

Bo robię coś i nic mi nie wychodzi.


([alex]) #8

Zajrzyj do implementacji STL'a


(kostek135) #9

Wstawianie elementu drzewa == wstawianie elementu do listy, jeśli wpiszesz w Google: "Linked list c++" albo "Array list c++" otrzymasz to czego szukasz. Po prostu na drzewo powinieneś patrzeć jak na grupę list połączonych ze sobą, ale w taki sposób, że dla dowolnych wierzchołków {X, Y} nie istnieje cykl.