Wie erstellen Sie einen zeigerbasierten Binärbaum, ohne die dynamische Speicherzuweisung zu verwenden?

Question

Einige C++ - Programmierer sagen, dass die dynamische Speicherzuweisung schlecht ist und wann immer möglich vermieden werden sollte. Ich habe versucht, eine binäre Baumdatenstruktur ohne Verwendung der dynamischen Speicherzuweisung zu erstellen, und es funktioniert nicht. Hier ist, was ich versucht:

struct BTNode { 
    BTNode *left = 0, *right = 0; 
    int data; 

    BTNode(int d_) { data = d_; } 

    void insert(int d_) { 
     BTNode n(d_); 
     if (d_ <= data) 
      if (left == 0) left = &n; 
      else left->insert(d_); 
     else 
      if (right == 0) right = &n; 
      else right->insert(d_); 
    } 
} 

Und dann diese in Haupt tun ...

BTNode root(8); 
root.insert(9); 
root.insert(10); 
cout << root.right->right->data; 

führt zu einer segfault, weil die BTnode die Daten enthalten, den Gültigkeitsbereich ging vor langer Zeit.

Meine Frage ist, wie soll man einen Zeiger-basierten Binärbaum so ohne die Verwendung von new und delete strukturieren?

Answer 1

Die kurze Antwort ist: Sie können so ziemlich nicht.

Die einzige Möglichkeit ist, dass der gesamte Baum in entweder automatisch zu erfolgen, oder globaler Reichweite und manuell aufgebaut:

BTNode root; 
BTNode left, right; 

root.left=&left; 
root.right=&right; 

Aber entweder das Ganze wird zerstört, wenn der automatische Rahmen bleibt, oder Sie haben jetzt eine Reihe hässlicher Globals.

Es ist nichts falsch mit dynamischen Bereich und dynamische Speicherzuweisung; vorausgesetzt, dass es richtig verwendet wird.

Answer 2

Sie können alle Ihre Knoten in einem einzigen std::array<> haben. Sie können frei aufeinander verweisen, und wenn Sie Ihr Array freigeben, werden alle Ihre Knoten ebenfalls sicher freigegeben. Sie müssen nur sicherstellen, dass Sie wissen, welche Elemente in Ihrem Array bereits verwendet wurden.

Bitte implementieren Sie aus pädagogischen Gründen nur eigene Bäume und ähnliche Behältnisse, oder wenn Sie sehr, sehr, sehr gute Gründe haben, die von der Standardbibliothek bereitgestellten nicht zu verwenden. Im letzteren Fall sollten Sie die Standardschnittstelle so genau wie möglich nachahmen, um Standardalgorithmen, bereichsbasierte For-Schleifen und leicht verständlichen Code für andere C++ - Entwickler zu ermöglichen.

Answer 3

Die Einfügemethode weist das BTNode-Objekt auf dem Stapel zu, dh der Speicher des Objekts ist ungültig, sobald die INSERT-Funktion zurückgegeben wird.

könnten Sie

tun

 BTNode newObj(9) 
     root.insert(newObj); 

Sie müssten auch

 void insert(BTNode &node) { ... 

in diesem Fall NEWOBJ Objekt bleibt im Rahmen der insert-Methode ändern, bis Sie Ihre Hauptfunktion verlassen. Noch besser können Sie es von statischen Umfang machen, dann wird es für die Dauer des Programms zur Verfügung stehen.