Bevor Sie also einige grundlegende Informatikkonzepte lesen.
- Ein Binärbaum ist eine dynamisch zugewiesene Struktur (normalerweise für die geordnete Speicherung verwendet).
- 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.
- In altmodischen Sprachen erfordert die Speicherverwaltung eine manuelle Speicherverwaltung.
- Handbuch: Bedeutet, dass Sie es selbst tun müssen.
- 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:
- Beste Komplexität.
- Tie Break 1: Zuerst eingereicht
- Tie Break 2: Wenig Charaktere.
quelle
C99, 94, O (n)
Bearbeiten: Jeder scheint sich auf
struct Node
genau so zu beziehenNode
als ob dertypedef
es , 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.
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
Der Algorithmus mutiert die Zeiger, so dass der Baum wird
Jetzt können wir den obersten Knoten leicht löschen.
quelle
C / C ++ / Objective-C 126 Zeichen (einschließlich erforderlicher Zeilenumbrüche)
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:
quelle
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.
Golf Version
Golf erweitert
quelle
C 150 Bytes
Probieren Sie es auf JDoodle
quelle