Czy drzewo można przemierzać bez rekurencji, stosu lub kolejki, a jedynie garść wskazówek?

Pół dekady temu siedziałem w klasie struktur danych, w której profesor oferował dodatkowy kredyt, jeśli ktokolwiek mógł przemierzać drzewo bez użycia rekurencji, stosu, kolejki itp. (Lub innych podobnych struktur danych) i tylko kilka wskazówek. Wpadłem na to, co uważałem za oczywistą odpowiedź na to pytanie, które ostatecznie zostało zaakceptowane przez profesora. Siedziałem w dyskretnej klasie matematycznej z innym profesorem w tym samym dziale - a on zapewnił, że niemożliwe jest przemierzanie drzewa bez rekurencji, stosu, kolejki itp. Oraz że moje rozwiązanie jest nieprawidłowe.

Czy to możliwe, czy niemożliwe? Dlaczego lub dlaczego nie?

Edycja: Aby dodać wyjaśnienia, zaimplementowałem to w drzewie binarnym, które miało trzy elementy - dane przechowywane w każdym węźle i wskaźniki do dwojga dzieci. Moje rozwiązanie można rozszerzyć na drzewa n-ary z kilkoma zmianami.

Mój nauczyciel struktur danych nie nałożył żadnych ograniczeń na mutowanie drzewa, i rzeczywiście dowiedziałem się później, że jego własnym rozwiązaniem było użycie wskaźników potomnych, aby skierować drzewo w górę. Mój dyskretny profesor matematyki powiedział, że jakakolwiek mutacja drzewa oznacza, że ​​nie jest to już drzewo zgodnie z matematyczną definicją drzewa, jego definicja wyklucza również wszelkie wskazówki dla rodziców - co pasowałoby do przypadku, w którym rozwiązałem je powyżej.

Wiele badań w tej dziedzinie zostało poddanych kopule, motywowanych metodą „taniego” przemieszczania się drzew i ogólnych struktur list w kontekście wywozu śmieci.

Gwintowane drzewo binarne to dostosowana reprezentacja drzew binarnych, w których niektóre wskaźniki zerowe są używane do łączenia się z następnymi węzłami w drzewie. Tych dodatkowych informacji można użyć do przejścia przez drzewo bez stosu. Konieczny jest jednak dodatkowy bit na węzeł, aby odróżnić wątki od wskaźników potomnych. Wikipedia: Tree_traversal

O ile wiem, drzewa binarne zaimplementowane przy użyciu wskaźników w zwykły sposób (lewy i prawy wskaźnik na węzeł) można przechodzić za pomocą metody wątków, w metodzie przypisanej Morrisowi . Wskaźniki NIL są tymczasowo ponownie używane do wątkowania ścieżki z powrotem do katalogu głównego. Sprytną częścią jest to, że podczas przechodzenia można odróżnić oryginalne krawędzie od tymczasowych połączeń nitek, wykorzystując sposób, w jaki tworzą one cykle na drzewie).

Dobra część: brak dodatkowej struktury danych. Zła część: nieco oszustwo, stos jest w sprytny sposób wewnątrz drzewa. Bardzo mądry.

Dowód ukrytego stosu pokazano w P. Mateti i R. Manghirmalani: Ponownie rozpatrzony algorytm przemierzania drzewa Morrisa DOI: 10.1016 / 0167-6423 (88) 90063-9

JM Morris: Przemierzanie drzew binarnych prosto i tanio. IPL 9 (1979) 197-200 DOI: 10.1016 / 0020-0190 (79) 90068-1

Jest też Lindstrom skanowanie . Ta metoda „obraca” trzy wskaźniki zaangażowane w każdym węźle (rodzic i dwoje dzieci). Jeśli chcesz wykonać przyzwoite algorytmy przedsprzedażowe lub po zamówieniu, potrzebujesz dodatkowych bitów na węzeł. Jeśli chcesz tylko odwiedzić wszystkie węzły (trzy razy, ale nigdy nie wiesz, którą wizytę wykonujesz), możesz to zrobić bez bitów.

G. Lindstrom: Skanowanie struktur list bez stosów i bitów znaczników. IPL 2 (1973) 47–51. DOI: 10.1016 / 0020-0190 (73) 90012-4

Być może najprostszym sposobem jest metoda Robsona . Tutaj stos potrzebny do klasycznego algorytmu jest przewleczony przez liście.

JM Robson: Ulepszony algorytm przechodzenia przez drzewa binarne bez stosu pomocniczego IPL 1 (1973) 149-152. 10.1016 / 0020-0190 (73) 90018-5

IPL = Listy przetwarzania informacji

$v$

Moim rozwiązaniem było przejście do pierwszej hodowli za pomocą zagnieżdżonych pętli for, aby brutalnie wymusić na drzewie. W żaden sposób nie jest to wydajne i rzeczywiście rekurencyjna struktura danych, taka jak drzewo, prosi o rekurencyjne przechodzenie, ale pytanie nie brzmiało, czy drzewo można skutecznie przechodzić, to, czy było to w ogóle możliwe.

Pseudocode:
root = pointer root 
depth = integer 0
finished = bool false
//If we n-ary tree also track how many children have been found 
//on the node with the most children for the purposes of this psuedocode 
//we'll assume a binary tree and insert a magic number of 2 so that we 
//can use bitwise operators instead of integer division 
while(!finished)
    ++depth
    treePosition = pointer root
    finished = true;
    for i := 0..2**depth
        for j := 0..depth
            if (i & j) //bitwise operator explained below
                // if right child doesn't exist break the loop
                treePosition = treePosition.rightChild
            else
                // if left child doesn't exist break the loop
                treePosition = treePosition.leftChild
        if j has any children
            finished = false
            do anything else you want when visiting the node

Dla kilku pierwszych poziomów wyglądałoby to tak, jak widać, operator bitowy w pseudokodzie po prostu decyduje o skręcie w lewo lub w prawo na drzewie binarnym:

2**1       0               1
2**2   00      01      10      11
2**3 000 001 010 011 100 101 110 111

W przypadku n-ary weźmiesz i% (maxChildren ** j) / j, aby określić, którą ścieżkę wybrać między 0 a maxChildren.

W każdym węźle n-ary musisz również sprawdzić, czy liczba dzieci jest większa niż maxChildren i odpowiednio ją zaktualizować.