Befreie einen binären Baum

13

Bevor Sie also einige grundlegende Informatikkonzepte lesen.

  1. Ein Binärbaum ist eine dynamisch zugewiesene Struktur (normalerweise für die geordnete Speicherung verwendet).
  2. Wegen seiner Natur ist das Durchqueren von Binärbäumen normalerweise rekursiv;
    Dies liegt daran, dass lineares Überqueren (über eine Schleife) nicht natürlich ist, wenn es zwei Möglichkeiten zum Schleifen gibt.
    • Rekursiv: Dies ist eine Funktion, die sich selbst aufruft.
  3. In altmodischen Sprachen erfordert die Speicherverwaltung eine manuelle Speicherverwaltung.
    • Handbuch: Bedeutet, dass Sie es selbst tun müssen.
  4. Wenn Sie die manuelle Speicherverwaltung durchführen, müssen Sie das zugrunde liegende System auffordern, jedes Mitglied des Baums freizugeben.
    • Kostenlos: Stellen Sie den Speicher in den globalen Poos wieder her, damit er wiederverwendet werden kann und Ihnen nicht der Speicher ausgeht.
    • Freigeben: Dies erfolgt durch Aufrufen der Funktion free()und Übergeben des Zeigers, den Sie wiederherstellen möchten.
    • Zeiger: Es ist wie ein virtueller Stock. Am Ende steht die Erinnerung. Wenn Sie nach Speicher fragen, erhalten Sie einen Zeiger (virtuellen Stick) mit Speicher. Wenn Sie fertig sind, geben Sie den Zeiger (virtuellen Stick) zurück.

Die rekursive Lösung:

freeTree(Node* node)
{
    freeTree(node->left);  
    freeTree(node->right);
    free(node);
}

Das Problem ist dann, dass Rekursion bedeutet, dass Sie wiederholt dieselbe Funktion aufrufen. Dies vergrößert den Stapel. Wenn Sie den Stapel vergrößern, wird mehr Speicher benötigt. Der Grund, warum Sie den Baum freigeben, besteht darin, dass Sie möchten, dass mehr Speicher verwendet wird, was kontraproduktiv ist (auch wenn Sie beide Speicherbits zurückerhalten).

Endlich die Frage:

Das Problem dreht sich darum, obige rekursive Version in eine lineare Lösung umzuwandeln (damit Sie keinen Speicher verwenden müssen).

Geben Sie den Knotentyp an

typedef struct Node Node;
struct Node
{
    Node* left;
    Node* right;
};

Schreiben Sie eine Funktion, um einen Baum dieser Knoten freizugeben.

Beschränkungen:

  • Kann keine Rekursion verwenden (auch nicht indirekt)
  • Es kann kein dynamischer Speicherplatz für die Verfolgung zugewiesen werden.

  • Beachten Sie, dass es eine O (n) -Lösung gibt

Gewinner:

  1. Beste Komplexität.
  2. Tie Break 1: Zuerst eingereicht
  3. Tie Break 2: Wenig Charaktere.
Martin York
quelle

Antworten:

7

Scheint mir sehr nahe zu sein:

Dies führt einen Tiefenrundgang auf dem Baum durch und verwendet den ->leftZeiger überquerter Knoten, um den Überblick über den übergeordneten Knoten zu behalten.

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;
            }
        }
    }
}
Arnaud Le Blanc
quelle
+1 Addiere das Häkchen für die einzige Antwort. Es ist ein bisschen komplexer als die Lösung, die ich unten präsentiere, aber sehr gut.
Martin York
4

C99, 94, O (n)

Bearbeiten: Jeder scheint sich auf struct Nodegenau so zu beziehenNode als ob der typedefes , also habe ich es auch getan.

Dies ist eigentlich mein erster C-Golf. viele segfaults.

Dies erfordert jedoch C99, da eine Deklaration in der ersten Anweisung einer for-Schleife verwendet wird.

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));}

nicht einmal mit #define !

Dieser Algorithmus transformiert den Baum so, dass der oberste Knoten kein untergeordnetes Element mehr hat, löscht ihn und wechselt zu seinem rechten untergeordneten Element.

Zum Beispiel, wenn wir mit dem Baum beginnen

 1
/ \
2 3
 \
 4

Der Algorithmus mutiert die Zeiger, so dass der Baum wird

2
 \
 1
/ \
4 3

Jetzt können wir den obersten Knoten leicht löschen.

stolzer haskeller
quelle
Ich habe typedef nicht verwendet, weil meins in C ++ war (Sie vergessen diese kleinen Unterschiede zwischen den Sprachen). Ich habe die Frage so aktualisiert, dass sie in C und C ++ gleich funktioniert.
Martin York
@LokiAstari Ich kenne C ++ nicht wirklich und habe gerade erst angefangen, C zu lernen. Aber ich wusste genug, um das zu beantworten :-)
stolzer Haskeller
1
Ich werde jetzt eine +1 machen. Aber ich habe immer noch nicht herausgefunden, wie es funktioniert, also werde ich nach der Türkei zurück sein. :-)
Martin York
@LokiAstari verwendet im Grunde genommen die Tatsache, dass C Ausdrücke und Anweisungen zusammenmischt, um etwas zu tun, das nur Ausdrücke verwendet
stolzer Haskeller
1

C / C ++ / Objective-C 126 Zeichen (einschließlich erforderlicher Zeilenumbrüche)

#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);}

Läuft nicht in O (n) Zeit. Das OP erfordert dies jedoch nicht. Hier ist meine O (n 2 ) -Lösung.

Algorithmus: Gehen Sie von der Wurzel zu einem Blatt. Lass es los. Wiederholen, bis keine Blätter mehr vorhanden sind. Lassen Sie die Wurzel los.

Ungolfed:

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);
}
Thomas Eding
quelle
Das geht leider nicht. Sie setzen den Zeiger auf das Blatt nicht auf NULL, bevor Sie es freigeben. Auf diese Weise werden Sie immer wieder denselben Blattknoten freigeben und nie an den Punkt gelangen, an dem Sie den Baum freigeben.
Martin Yorker
@LokiAstari: Danke, dass du den Fehler bemerkt hast. Es sollte jetzt behoben sein (obwohl ich den Code nicht getestet habe).
Thomas Eding
1

c ++ 99 O (n)

Die hier aufgeführten Schleifen eignen sich hervorragend zum Verketten einer Liste, nicht jedoch zum Auf- und Absteigen von Hierarchien. user300 hat es geschafft (ich bin beeindruckt), aber der Code ist schwer zu lesen.

Die Lösung besteht darin, den Baum in eine Liste umzuwandeln.
Der Trick besteht darin, es gleichzeitig mit dem Löschen der Knoten zu tun.

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;
}

Golf Version

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 erweitert

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;
        }
}
Martin York
quelle
0

C 150 Bytes

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++;}}

Probieren Sie es auf JDoodle

T. Salim
quelle