Więc zanim przeczytasz kilka podstawowych pojęć informatycznych.
- Drzewo binarne jest dynamicznie alokowaną strukturą (zwykle używaną do uporządkowanego przechowywania).
- Ze względu na swój charakter przechodzenie przez drzewa binarne jest zwykle rekurencyjne;
Wynika to z faktu, że przejście liniowe (przez pętlę) nie jest naturalne, gdy istnieją dwie możliwości zapętlenia.- Rekurencyjny: oznacza funkcję, która się wywołuje.
- W starych językach zarządzanie pamięcią wymaga ręcznego zarządzania pamięcią.
- Podręcznik: Oznacza, że musisz to zrobić sam.
- Podczas ręcznego zarządzania pamięcią należy faktycznie poprosić system podstawowy o zwolnienie każdego członka drzewa.
- Bezpłatnie: odzyskaj pamięć do globalnych kupek, aby można ją było ponownie wykorzystać i nie zabrakło pamięci.
- Uwalnianie: odbywa się to przez wywołanie funkcji
free()
i przekazanie jej wskaźnika, który chcesz odzyskać. - Wskaźnik: To jak wirtualny kij. Na końcu jest pamięć. Gdy poprosisz o pamięć, otrzymasz wskaźnik (wirtualny drążek), który ma pamięć. Po zakończeniu oddasz wskaźnik (wirtualny drążek).
Rozwiązanie rekurencyjne:
freeTree(Node* node)
{
freeTree(node->left);
freeTree(node->right);
free(node);
}
Problem polega na tym, że rekurencja oznacza, że wielokrotnie wywołujesz tę samą funkcję. To zwiększa stos. Zwiększenie stosu wymaga więcej pamięci. Powodem, dla którego zwalniasz drzewo, jest to, że chcesz odzyskać pamięć przy użyciu większej ilości pamięci, co przynosi efekt przeciwny do zamierzonego (nawet jeśli odzyskasz oba bity pamięci).
Nareszcie pytanie:
Więc problem koncentruje się wokół konwersji powyższej wersji rekurencyjnej na rozwiązanie liniowe (dzięki czemu nie musisz używać pamięci).
Podaj typ węzła
typedef struct Node Node;
struct Node
{
Node* left;
Node* right;
};
Napisz funkcję, aby zwolnić drzewo tych węzłów.
Ograniczenia:
- Nie można użyć rekurencji (nawet pośrednio)
Nie można przydzielić dynamicznej przestrzeni do śledzenia.
Zauważ, że istnieje rozwiązanie O (n)
Zwycięzca:
- Najlepsza złożoność.
- Tie Break 1: Pierwsze zgłoszenie
- Tie Break 2: Najmniejsza liczba postaci.
źródło
C99, 94, O (n)
Edycja: wydaje się, że wszyscy odnoszą się
struct Node
tak,Node
jakby totypedef
ed, więc ja też.to właściwie mój pierwszy golf C. wiele wad.
w każdym razie wymaga to C99, ponieważ używa deklaracji wewnątrz pierwszej instrukcji pętli for.
nawet nie używam
#define
!ten algorytm działa poprzez przekształcenie drzewa, tak aby górny węzeł nie miał lewego dziecka, a następnie usunięcie go i przejście do jego prawego dziecka.
na przykład, jeśli zaczniemy od drzewa
algorytm zmutuje wskaźniki tak, aby drzewo było
teraz możemy łatwo usunąć najwyższy węzeł.
źródło
C / C ++ / Objective-C 126 znaków (zawiera wymagany końcowy znak nowej linii)
Nie działa w czasie O (n). Ale OP nie wymaga tego, więc oto moje rozwiązanie O (n 2 ).
Algorytm: zejdź do liścia od korzenia. Puść to. Powtarzaj, aż nie będzie liści. Zwolnij root.
Nie golfowany:
źródło
c ++ 99 O (n)
Pętle są świetne do łączenia łańcuchów wzdłuż listy, ale nie do hierarchii. user300 zarządzał nim (jestem pod wrażeniem), ale kod jest trudny do odczytania.
Rozwiązaniem jest przekonwertowanie drzewa na listę.
Sztuką jest zrobienie tego w tym samym czasie, gdy usuwasz węzły.
Wersja golfowa
Golf rozszerzony
źródło
C, 150 bajtów
Wypróbuj na JDoodle
źródło