Wie erstellt man einen vollständigen Binärbaum mit leeren Knoten

Question

Ich arbeite am Zusammenführen von 2 Vorlage AVL Bäume in 1 Baum mit einer Komplexität von Gesamt Anzahl der Knoten in beiden Bäumen (was schwierig ist) - der richtige Algorithmus ist Erstellen Sie einen vollständigen Binärbaum mit der Anzahl der Knoten von Gesamt - wenn Summe ist gleich der Macht von 2 minus 1, oder um einen vollständigen Binärbaum mit mehr Knoten als insgesamt (die nächste Potenz von 2) zu erstellen und schneiden Sie die unnötigen Blätter (Diff zwischen Gesamt und der nächsten Potenz von 2), während die Knoten auch Vorlage sind und leer sein sollten. Wie kann ich einen vollständigen Binärbaum mit leeren Knoten ohne Schlüsselvergleich erstellen (ich kann keine Schlüssel haben, da die Knoten eine Vorlage sind)?

meine Vorlage Knoten ist:

class avl_node{ 
private: 
    friend class avl_tree; 
    //design to contain dinamically allocated key and data only! 
    //assumption- every node uses it's own data and key- no data or key are the 
    //same memory for different nodes! 
    Key *key; 
    T *data; 
    avl_node *parent; 
    avl_node *right; 
    avl_node *left; 
    int height; 
    int balance; 
    int maxHeight(int h1,int h2){ 
     return (h1 > h2) ? h1:h2; 
    } 

public: 
    avl_node(Key* key=nullptr, T* data=nullptr): key(key),data(data),right(nullptr),left(nullptr),parent(nullptr),height(0),balance(0){} 
    //no setKey since this is an invariant from node creation 
    virtual ~avl_node(){ 
     delete key; 
     delete data; 
     delete right; 
     delete left; 
    } 
    virtual bool insert(Key* key, T* data,avl_node *& to_fix_from); 
    virtual avl_node * findNode(const Key& key); 
    virtual void updateStats() { 
     if(left && right){ 
      height=maxHeight(left->height,right->height)+1; 
      balance=left->height-right->height; 
      return; 
     } 
     if(!left && right){ 
      height=right->height+1; 
      balance=-right->balance; 
      return; 
     } 
     if(left &&!right){ 
      height=left->height+1; 
      balance=left->height; 
      return; 
     } 
     this->height=0; 
    } 

}; 

das Problem ist-Key ist eine Vorlage parameter-, so kann ich nicht entscheiden, beispielsweise eine benötigte auf die Menge der Knoten für die Schleife zu machen und einige erstellen Einfacher Schlüssel (laut for-loops'counter) und einfügen - da insert benötigt eine Option zum Vergleichen.

i bin die Bearbeitung die Frage: i here fand heraus, i dinamically ein Array von leeren Knoten zuteilen kann, und jeden Knoten rekursiv mit linken zuweisen und rechts, wie in binärer Suche (auf dem Array-Indizes). neue Frage: kann ich jeden Knoten einzeln von einem Zeiger auf diesen Knoten freigeben - obwohl sie in einem Array zugewiesen wurden? weil ich mit nur einer Wurzel bleiben und es wie ein Baum mit der kompatiblen Löschfunktion behandeln wollte.

Answer 1

Die Frage ist nicht absolut klar, was Sie zu erreichen versuchen. Einen voll leeren Baum zu bauen, ist relativ einfach. Sie brauchen zu diesem Zeitpunkt keine Schlüssel. Sie werden alle NULL sein. Sie können etwas tun:

avl_node *avl_node::BuildAvlSubtree(int height_needed) 
{ 
    if (height_needed <= 0) 
     return nullptr; 
    auto node = new avl_node(); 
    node->left = BuildAvlSubtree(height_needed-1); 
    node->right = BuildAvlSubtree(height_needed-1); 
    return node; 
} 

Diese Funktion sollte ein statisches Element der avl_node Klasse sein, weil es die privaten Mitglieder zugreift.