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

Question

我正在尝试按照以下算法构建一个基于数组的“二叉搜索树”:

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)部分中的项目数组的结构:...

 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)

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

要求的reloaction方法:

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

Answer 1

有一种很好的方法可以将二叉树实现为数组，即根位于索引 0，索引 i 处的元素的 LEFT 将在 2i 处找到+ 1 和 RIGHT 将在 2i + 2 处找到。您不需要将 LEFT 和 RIGHT 作为结构的一部分。必须是

struct item
{
    int index;
    data theData;
};

不要在您的结构中存储左索引和右索引。您也不需要跟踪根索引。它始终为 0。查看 wiki article在二叉树上。搜索“存储二叉树的方法”字符串。如果需要，此实现允许轻松地向下和向上遍历树。