Przebieg drzewa - zaczynając od liści z tylko rodzicami wskazującymi?

Question

Czy możliwe jest koncepcyjne posiadanie drzewa, w którym je przechodzisz, zaczynając od danego węzła liściowego (zamiast węzła głównego) i używając wskaźników rodzicielskich, aby dostać się do katalogu głównego?

Pytam o to, ponieważ widziałem kogoś, kto zaimplementował drzewo i użyli tablicy do przechowywania wszystkich węzłów liści/zewnętrznych węzłów, a każdy z liści/zewnętrznych węzłów wskazuje tylko na ich węzły macierzyste i te punkty nadrzędne na ich rodzica węzeł itd., aż dojdziesz do węzła głównego, który nie ma rodziców. Ich implementacja wymagałaby zatem, abyś zaczął od jednej z liści, aby dostać się do dowolnego miejsca w drzewie i nie mógłbyś "zejść" z drzewa, ponieważ jej węzły drzewa nie mają żadnych wskaźników dla dzieci, tylko wskaźniki rodziców.

Znalazłem to wdrożenie interesujące, ponieważ nie widziałem czegoś podobnego, ale byłem ciekawy, czy można go jeszcze uznać za "drzewo". Nigdy nie widziałem drzewa, w którym zaczynasz przemierzać liście, zamiast korzenia. Nigdy też nie widziałem drzewa, w którym węzły drzewa mają tylko wskaźniki rodzica i dzieci nie wskazują.

Answer 1

Tak, ta struktura istnieje. Jest często nazywany .

Stosy spaghetti są przydatne do reprezentowania relacji "jest częścią". Na przykład, jeśli chcesz reprezentować hierarchię klas w sposób, który sprawia, że ​​upcasting jest wydajny, możesz reprezentować hierarchię klas jako stos spaghetti, w którym węzeł każdego typu przechowuje wskaźnik do swojego rodzica. W ten sposób łatwo jest ustalić, czy upcast jest ważny, idąc w górę od węzła.

Są również często używane w kompilatorach do śledzenia informacji o scopingu. Każdy węzeł reprezentuje jeden zakres w programie, a każdy węzeł ma wskaźnik do węzła reprezentujący zakres jeden poziom powyżej niego.

Mam nadzieję, że to pomoże!

Answer 2

Jeśli podano tablicę A węzłów liści, możliwe jest przemieszczenie. Jeśli podany jest tylko jeden węzeł liścia, nie wiem, jak przejść przez drzewo. Pseudokod:

// initial step 
add all nodes in A to a queue Q 

//removeNode(Q) returns pointer to node at front of Q 
while((node = removeNode(Q)) != NULL) 
    /* do your operation on node */ 
    add node->parent to Q