Rekursive Struktur ohne Zeiger? (Huffman)

Question

I definiert einen Binärbaum auf diese Weise:

struct btree { 
    int x; 
    btree* left_child = nullptr; 
    btree* right_child = nullptr; 
}; 

Dann habe ich einen Vektor von Schwimmern (prob_distr) und I drehen jedes Schwimmers in ein Blatt und ich habe alle Blätter in eine Prioritätswarteschlange (mit eine benutzerdefinierte Sortierfunktion, aber das spielt hier keine Rolle).

auto comp = [] (btree &a, btree &b) -> bool { return a.x > b.x; }; 
priority_queue<btree, vector<btree>, decltype(comp)> q(comp); 

for(auto t: prob_distr) 
{ 
    btree leaf; 
    leaf.x = t; 
    q.push(leaf); 
} 

Für den Huffman-Algorithmus, I dann die Schleife auf der Prioritäts-Warteschlange, bis sie hat nur 1 Element nach links: Ich nehme den 2-Knoten an der Spitze der Warteschlange heraus schaffe ich einen neuen Knoten mit diesen beiden Knoten als Kinder und ich legte diesen neuen Knoten in die Warteschlange.

while(q.size() >= 2) 
{ 
    btree left = q.top(); q.pop(); 
    btree right = q.top(); q.pop(); 

    btree root; 
    root.x = left.x + right.x; 
    root.left_child = &left; 
    root.right_child = &right; 

    q.push(root); 
} 

Das Problem ist, dass ich Zeiger auf die left und right Binärbäumen haben, und diese Bäume gelöscht werden, wenn aus der while-Schleife gehen. Dann habe ich Zeiger, die auf Nichts zeigen. Gibt es eine Möglichkeit, dies zu lösen, zum Beispiel mit einer Struktur, die die Kinderbäume speichert und nicht nur mit Zeigern, oder indem die Knoten woanders gespeichert werden, ohne dass es zu kompliziert wird?

Answer 1

Hier müssen Sie Zeiger verwenden, da die Größe der Struktur zur Kompilierzeit bekannt sein muss. Wenn Sie struct selbst als eine Mitgliedsvariable hätten, würde der Speicherbedarf rekursiv in die Unendlichkeit gehen.

Sie müssen den Speicher dynamisch mit new zuweisen. Der mit new zugewiesene Speicher wird zugewiesen, bis Sie ihn explizit freigeben, indem Sie delete verwenden. Schreiben Sie einfach

root.left_child = new btree(left); 
root.right_child = new btree(right); 

Wie schon gesagt, auch die Erinnerung an die Kinder zu befreien, müssen delete verwenden. Achten Sie darauf, keine Kopien von Kindern zu erstellen, die nicht gelöscht werden, und keine Kinder zu löschen, die noch an einem anderen Ort verwendet werden. Erwägen Sie die Verwendung von intelligenten Zeigern.