Czy ktoś może mi pomóc zrozumieć następujący algorytm przemierzania drzewa Morrisa bez używania stosów lub rekurencji? Próbowałem zrozumieć, jak to działa, ale po prostu mi to wymyka.
1. Initialize current as root
2. While current is not NULL
If current does not have left child
a. Print current’s data
b. Go to the right, i.e., current = current->right
Else
a. In current's left subtree, make current the right child of the rightmost node
b. Go to this left child, i.e., current = current->left
Rozumiem, że drzewo jest modyfikowane w taki sposób, że current node
jest uczynił right child
z max node
w right subtree
i wykorzystać tę właściwość dla Inorder przechodzenia. Ale poza tym jestem zagubiony.
EDYCJA: Znaleziono ten towarzyszący kod C ++. Trudno mi było zrozumieć, w jaki sposób drzewo jest przywracane po modyfikacji. Magia tkwi w else
klauzuli, która jest uderzana po zmodyfikowaniu prawego liścia. Zobacz kod po szczegóły:
/* Function to traverse binary tree without recursion and
without stack */
void MorrisTraversal(struct tNode *root)
{
struct tNode *current,*pre;
if(root == NULL)
return;
current = root;
while(current != NULL)
{
if(current->left == NULL)
{
printf(" %d ", current->data);
current = current->right;
}
else
{
/* Find the inorder predecessor of current */
pre = current->left;
while(pre->right != NULL && pre->right != current)
pre = pre->right;
/* Make current as right child of its inorder predecessor */
if(pre->right == NULL)
{
pre->right = current;
current = current->left;
}
// MAGIC OF RESTORING the Tree happens here:
/* Revert the changes made in if part to restore the original
tree i.e., fix the right child of predecssor */
else
{
pre->right = NULL;
printf(" %d ",current->data);
current = current->right;
} /* End of if condition pre->right == NULL */
} /* End of if condition current->left == NULL*/
} /* End of while */
}
c++
binary-tree
tree-traversal
brainydexter
źródło
źródło
pre->right = NULL;
Odpowiedzi:
Jeśli dobrze czytam algorytm, powinien to być przykład tego, jak to działa:
Najpierw
X
jest katalog główny, więc jest inicjowany jakocurrent
.X
ma lewe dziecko, więcX
jest prawe skrajne prawe dzieckoX
lewego poddrzewa - bezpośredniego poprzednikaX
w wewnętrznym przechodzeniu. WięcX
staje się właściwym dzieckiemB
, a następniecurrent
jest ustawione naY
. Drzewo wygląda teraz następująco:(Y)
powyżej odnosi się doY
i wszystkich jego elementów podrzędnych, które są pomijane w przypadku problemów z rekursją. Ważna część jest jednak wymieniona. Teraz, gdy drzewo ma łącze z powrotem do X, przeglądanie jest kontynuowane ...Następnie
A
jest wyprowadzane, ponieważ nie ma lewego dziecka, icurrent
jest zwracane, doY
którego zostało utworzoneA
prawe dziecko w poprzedniej iteracji. W następnej iteracji Y ma dwoje dzieci. Jednak podwójny stan pętli powoduje jej zatrzymanie, gdy osiągnie samą siebie, co wskazuje, że jej lewe poddrzewo zostało już przekroczone. Tak więc drukuje się i kontynuuje z odpowiednim poddrzewem, którym jestB
.B
drukuje się, a następniecurrent
staje sięX
, który przechodzi przez ten sam proces sprawdzania, coY
zrobił, zdając sobie również sprawę, że jego lewe poddrzewo zostało przekroczone, kontynuując procesZ
. Reszta drzewa ma ten sam wzór.Rekurencja nie jest konieczna, ponieważ zamiast polegać na cofaniu się przez stos, łącze z powrotem do korzenia (pod) drzewa jest przenoszone do punktu, w którym byłby dostępny w rekurencyjnym algorytmie przechodzenia przez drzewo w kolejności - po jego zakończenie lewego poddrzewa.
źródło
Rekurencyjne in-order przechodzenie jest:
(in-order(left)->key->in-order(right))
. (jest to podobne do DFS)Kiedy wykonujemy DFS, musimy wiedzieć, dokąd się cofnąć (dlatego zwykle trzymamy stos).
Kiedy przechodzimy przez węzeł nadrzędny, do którego będziemy musieli cofnąć się -> znajdujemy węzeł, z którego będziemy musieli cofnąć się i aktualizujemy jego łącze do węzła nadrzędnego.
Kiedy się cofniemy? Kiedy nie możemy iść dalej. Kiedy nie możemy iść dalej? Kiedy nie ma pozostawionego dziecka.
Gdzie wracamy? Uwaga: do SUKCESORA!
Tak więc, gdy podążamy za węzłami wzdłuż ścieżki po lewej stronie, ustaw poprzednik na każdym kroku tak, aby wskazywał na bieżący węzeł. W ten sposób poprzednicy będą mieli linki do następców (łącze do cofania).
Idziemy w lewo, dopóki możemy, dopóki nie będziemy musieli się wycofać. Kiedy musimy się cofnąć, drukujemy bieżący węzeł i podążamy za odpowiednim łączem do następcy.
Jeśli właśnie się wycofaliśmy -> musimy podążać za prawym dzieckiem (skończyliśmy z lewym dzieckiem).
Jak sprawdzić, czy właśnie się wycofaliśmy? Pobierz poprzednika bieżącego węzła i sprawdź, czy ma poprawne łącze (do tego węzła). Jeśli tak - to postępowaliśmy zgodnie z nim. usuń łącze, aby przywrócić drzewo.
Jeśli nie było lewego linku => nie cofaliśmy się i powinniśmy kontynuować za lewymi dziećmi.
Oto mój kod Java (przepraszam, to nie jest C ++)
źródło
Animację dla algorytmu zrobiłem tutaj: https://docs.google.com/presentation/d/11GWAeUN0ckP7yjHrQkIB0WT9ZUhDBSa-WR0VsPU38fg/edit?usp=sharing
Miejmy nadzieję, że to pomoże zrozumieć. Niebieskie kółko to kursor, a każdy slajd to iteracja zewnętrznej pętli while.
Oto kod dla morris traversal (skopiowałem i zmodyfikowałem go z maniaków dla maniaków):
źródło
print(cursor.value)
popre.right = None
wierszuMyślę, że ten kod lepiej byłoby zrozumieć, po prostu użyj wartości null, aby uniknąć nieskończonych pętli, nie musisz używać innych magii. Można go łatwo zmodyfikować, aby zamówić w przedsprzedaży.
źródło
temp.left = null
drzewo zostanie utracone.Znalazłem bardzo dobre obrazkowe wyjaśnienie Morrisa Traversala .
źródło
Mam nadzieję, że poniższy pseudokod jest bardziej pouczający:
Odnosząc się do kodu C ++ w pytaniu, wewnętrzna pętla while znajduje poprzednika w kolejności bieżącego węzła. W standardowym drzewie binarnym prawe dziecko poprzednika musi mieć wartość null, podczas gdy w wersji z wątkami prawe dziecko musi wskazywać na bieżący węzeł. Jeśli prawe dziecko ma wartość null, jest ustawiane na bieżący węzeł, skutecznie tworząc wątek , który jest używany jako punkt powrotu, który w przeciwnym razie musiałby być przechowywany, zwykle na stosie. Jeśli prawe dziecko nie jest zerowe, algorytm upewnia się, że oryginalne drzewo zostało przywrócone, a następnie kontynuuje przeglądanie w prawym poddrzewie (w tym przypadku wiadomo, że odwiedzono lewe poddrzewo).
źródło
Złożoność czasowa rozwiązania Pythona: O (n) Złożoność przestrzeni: O (1)
Doskonałe wyjaśnienie przejścia Morris Inorder
źródło
PFB Wyjaśnienie przejścia Morris w kolejności.
źródło