如何创建具有空节点的完整二叉树

我正在将2个模板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; 
    } 

};

的问题是 - 主要是模板参数 - 所以我不能决定，例如，做一个for循环所需要的节点数量，并创建一些简单的键（根据for-loops'counter）并插入它 - 因为插入需要一些选项来比较。

我编辑的问题：我发现here，我可以dinamically分配空节点的数组，并递归地分配每个节点与左和右如二进制搜索（在阵列索引）。 新问题：我可以从一个指向这个节点的指针中逐一释放每个节点 - 尽管它们被分配在一个数组中吗？因为我想只保留一个根，并把它看作一棵具有兼容删除功能的树。

来源

2016-12-01 Asher Yartsev

更详细地解释你的问题。它与C++有什么关系？ –

“节点是模板”是什么意思？你知道如何以你想要的方式构建* one *节点吗？如果节点的总数不是2^n-1？ – Beta

我现在就编辑它，查找并感谢@KirillKobelev –

问题不是绝对清楚的形式，你想达到什么目的。构建一个完整的空树是相对简单的。此时您不需要任何密钥。它们将全部为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类的静态成员。

来源

2016-12-01 19:12:28

如何创建具有空节点的完整二叉树

回答

相关问题