c++ - 二叉搜索树 C++

Question

我有点懵。我想知道是否以这种方式实现了基于数组的二叉搜索树？

void BST::insert(item &items, const data & aData )
{//helper function.
    Parent++;
    data *new_data = new data(aData);
    this->insert(*new_data);
}

// insert a new item into the BST
void BST::insert(const data &aData )
{
    if ( items[Parent].empty ) 
    {
        items[Parent].theData = aData;
        items[Parent].empty = false;
    }
    else if ( aData < items[Parent].theData )
    {
              if ( Parent >= maxSize ) this->reallocate();
              this->insert(items[2*Parent+1], aData);
    }
    else
    {
           this->insert(items[2*Parent+2], aData);
    }
}

//我进行初始化的构造函数。

BST::BST(int capacity) : items(new item[capacity]), 
Parent(0), leftChild(0), rightChild(0), maxSize(capacity)
{
}

Answer 1

我不确定基于数组的二叉树是最好的主意，因为它:

1. 防止节点平衡(优化不平衡树的查找)
2. 浪费空间 - 大量空间，尤其是当树不平衡时。

话虽如此，但这是一种有效的方法，只需稍作改动:改变

if ( Parent >= maxSize ) this->reallocate();

到

if ( 2*Parent >= maxSize ) this->reallocate();