c++ - 基于数组的二叉搜索树C++

我试图通过遵循以下算法构建基于数组的“二进制搜索树”:

http://highered.mcgraw-hill.com/olcweb/cgi/pluginpop.cgi?it=gif%3A:600%3A:388%3A%3A/sites/dl/free/0070131511/25327/tree%5Finsert.gif%3A%3ATREE-INSERT

直到我需要重新生成树，我的树才像:

     R
    /
   A
    \
     F
      \
       L
      /
     B
      \
       C
        \
         T

递归地。但是，即时通讯注意到我需要回到根目录“R”...。现在尝试这样做。

void BST::insert(const data& aData)
{
item *y = NULL;   // Algorithm calls for NULL assignment..
item *x = new item();

     // How do i Init LEFT and RIGHT?
     // With no nested copy ctor for struct item?
if ( items->empty )
{
    items = new item();
    items->empty = false;
    items->theData = aData; // Get the data.
    ++size;
}
else if ( size == maxSize ) this->reallocate();
else
{
        if ( aData < items->theData )
        {
            x[x->LEFT].theData = aData;
            x->LEFT = x->LEFT + 1;
            this->insert(items->theData);
        }
        else if ( items->theData < aData )
        {
            x[x->RIGHT].theData = aData;
            x->RIGHT = x->RIGHT + 1;
            this->insert(items->theData);
        }
                       else this->insert(items->theData);
}

这是我的BST类对象文件的private部分中的items数组的结构:
...

 private:
    int size;  // size of the ever growing/expanding tree :)
    int maxSize;
    struct item
    {
              bool empty;
         int  LEFT;
              int  RIGHT;
              data theData;
         };

    item *items;    // The tree array
    item *oldRoot;
         int root_index;   // index for the root(s)

嗯我还在重载赋值运算符...我不知道该说些什么。这个很难(硬。我在网上看了很多例子和讲座。以及算法...

要求的展开方法:

void BST::reallocate()
{
    item *new_array = new item[size*2];
    for ( int array_index = 0; array_index < size; array_index++ )
    {
        new_array[array_index].theData = items[array_index].theData;
        new_array[array_index].empty = false;
    }
    size *= 2;
    delete [] items;

    items = NULL;
    items = new_array;
}

最佳答案

有一种公认的方法将二进制树实现为数组，该方法表示根位于索引0处，索引i处元素的LEFT将位于2i + 1处，而RIGHT将位于2i + 2处。您不需要将LEFT和RIGHT作为结构的一部分。
它一定要是

struct item
{
    int index;
    data theData;
};

不要而不是将左索引和右索引存储在结构中。另外，您不需要跟踪根索引。始终为0。在二叉树上 check out wiki article。搜索“用于存储二进制树的方法”字符串。
如果需要，此实现允许轻松遍历树。

关于c++ - 基于数组的二叉搜索树C++，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/1736872/