Как создать полное двоичное дерево с пустыми узлами

Question

Я работаю над слиянием двух шаблонов AVL деревьев в 1 дерево со сложностью всего несколько узлов в обоих деревьях (что сложно) - правильный алгоритм построить полное двоичное дерево с количеством узлов всего - если сумма равна мощности 2 минус 1 или создать полное двоичное дерево с большим количеством узлов, чем общее (следующая мощность 2) и вырезать ненужные листья (разница между суммой и следующей мощностью 2), в то время как узлы также являются шаблонами и должны быть пустыми. Как я могу построить полное двоичное дерево с пустыми узлами без какого-либо сравнения клавиш (у меня не может быть никаких ключей, поскольку узлы являются шаблонами)?

мой шаблон узла:

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

}; 

этот вопрос IS-Key является шаблоном параметрируемую поэтому я не могу решить, например, чтобы сделать цикл на количество узлов, необходимых и создать некоторые простой ключ (в соответствии с for-loops'counter) и вставить его, поскольку вставка нуждается в некоторой опции для сравнения.

я редактирую вопрос: я узнал here, я могу динамически выделять массив пустых узлов и рекурсивно назначить каждый узел с левой и правой, как в бинарном поиске (на индексы массива). новый вопрос: могу ли я освободить каждый узел один за другим от указателя на этот узел, хотя они были выделены в массиве? потому что я хотел остаться только с одним корнем и рассматривать его как дерево с совместимой функцией удаления.

Answer 1

Вопрос не является абсолютно четкой формой того, что вы пытаетесь достичь. Построение полного пустого дерева относительно просто. На данный момент вам не нужны никакие ключи. Все они будут NULL. Вы можете сделать что-то вроде этого:

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

Эта функция должна быть статическим членом avl_node класса, потому что он получает доступ к закрытым членам.