Więc zanim przeczytasz kilka podstawowych pojęć informatycznych.

1. Drzewo binarne jest dynamicznie alokowaną strukturą (zwykle używaną do uporządkowanego przechowywania).
2. 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.
3. W starych językach zarządzanie pamięcią wymaga ręcznego zarządzania pamięcią.
   • Podręcznik: Oznacza, że ​​musisz to zrobić sam.
4. 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:

1. Najlepsza złożoność.
2. Tie Break 1: Pierwsze zgłoszenie
3. Tie Break 2: Najmniejsza liczba postaci.

Wydaje mi się bardzo bliskie O (n):

Robi to najpierw głębokość chodzenia po drzewie i używa ->leftwskaźnika przemierzonych węzłów do śledzenia rodzica.

struct Node * node = root;
struct Node * up = NULL;

while (node != NULL) {
    if (node->left != NULL) {
        struct Node * left = node->left;
        node->left = up;
        up = node;
        node = left;
    } else if (node->right != NULL) {
        struct Node * right = node->right;
        node->left = up;
        node->right = NULL;
        up = node;
        node = right;
    } else {
        if (up == NULL) {
            free(node);
            node = NULL;
        }
        while (up != NULL) {
            free(node);
            if (up->right != NULL) {
                node = up->right;
                up->right = NULL;
                break;
            } else {
                node = up;
                up = up->left;
            }
        }
    }
}

C99, 94, O (n)

Edycja: wydaje się, że wszyscy odnoszą się struct Nodetak, Nodejakby to typedefed, 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.

void f(Node*n){for(Node*q;n;n=q)(q=n->left)?n->left=q->right,q->right=n:(q=n->right,free(n));}

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

 1
/ \
2 3
 \
 4

algorytm zmutuje wskaźniki tak, aby drzewo było

2
 \
 1
/ \
4 3

teraz możemy łatwo usunąć najwyższy węzeł.

C / C ++ / Objective-C 126 znaków (zawiera wymagany końcowy znak nowej linii)

#define b(t)(t->left||t->right)
void f(Node*r){while(r&&b(r)){Node**p=&r,*c=b(r);while(c)p=&c,c=b(c);free(*p);*p=0;}free(r);}

Nie działa w czasie O (n). Ale OP nie wymaga tego, więc oto moje rozwiązanie O (n ² ).

Algorytm: zejdź do liścia od korzenia. Puść to. Powtarzaj, aż nie będzie liści. Zwolnij root.

Nie golfowany:

void freeTree (Node * root) {
    while (root && (root->left || root->right)) {
        Node ** prev = &root;
        Node * curr = root->left || root->right;
        while (curr != 0) {
            prev = &curr;
            curr = curr->left || curr->right;
        }
        free(*prev);
        *prev = 0;
    }
    free(root);
}

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.

void freeNode(Node* t)
{
    if (t == NULL)
    {   return;
    }

    // Points at the bottom left node.
    // Any right nodes are added to the bottom left as we go down
    // this progressively flattens the tree into a list as we go.    
    Node* bottomLeft    = findBottomLeft(t);


    while(t != NULL)
    {
        // Technically we don't need the if (it works fine without)
        // But it makes the code easier to reason about with it here.
        if (t->right != NULL)
        {
            bottomLeft->left = t->right;
            bottomLeft = findBottomLeft(bottomLeft);
        }
        // Now just free the curent node
        Node*   old = t;
        t = t->left;
        free(old);
    }
}

Node* findBottomLeft(Node* t)
{
    while(t->left != NULL)
    {
        t = t->left;
    }
    return t;
}

Wersja golfowa

void f(Node*t){Node*o,*l=t;for(;t;free(o)){for(;l->left;l=l->left);l->left=t->right;o=t;t=t->left;}}

Golf rozszerzony

void f(Node* t)
{
        Node*o,*l    = t;

        for(;t;free(o))
        {
            for(;l->left;l = l->left);
            l->left = t->right;
            o = t;
            t = t->left;
        }
}

C, 150 bajtów

f(T*r,int s){T*t[s];t[0]=r;T**f=&t[0],**e=&t[0];while(f<=e){if(*f){if((*f)->left){*++e=(*f)->left;}if((*f)->right){*++e=(*f)->right;}}free(*f);f++;}}

Wypróbuj na JDoodle