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

Question

我试图插入一个基于数组的二进制搜索树。

我不确定如何防止使用左右索引覆盖数据...

我是否将左子插入为 tree[2 * i + 1] 并将右子插入为 tree[2 * i + 2] ？我认为这是为了定位给定名称的节点的位置...

那是我的问题。不知道如何插入，递归或迭代(我选择递归但它可能是完全错误的)。

BST::BST(int capacity) : items(new item[capacity]), size(0),
leftChild(0), rightChild(0), root_index(1)
{
 items->empty = true;
 maxSize = capacity-1;
}

下面是插入函数。我见过很多处理链表实现的，但没有基于数组的!这是我的尝试:

void BST::insert(const data& aData)
{
if ( items[root_index].empty ) 
{
    items[root_index].theData = aData;// Get the data.
    items[root_index].empty = false;
    oldRoot.theData = aData;
} 
else  
{   
    if ( aData < items[root_index].theData )
    {
        leftChild = root_index * 2;
        if ( items[leftChild].empty )
        {
            items[leftChild].theData = aData;
            items[leftChild].empty = false;
        }//items->empty = true;
        else 
        {
            items[root_index].theData = items[leftChild].theData;
            this->insert(aData);
        }
    }
    else if ( items[root_index].theData < aData )
    {
        rightChild = root_index * 2 + 1;
        if ( items[rightChild].empty )
        {
            items[rightChild].theData = aData;
            items[rightChild].empty = false;
        }
        else//items->empty = true;
        {
            items[root_index].theData = items[rightChild].theData;      
            this->insert(aData);
        }

    }
    else return;
}
items[1].theData = oldRoot.theData;
}

什么是正确的？...有人有任何基于数组的插入建议吗？我似乎陷入了无限递归

Answer 1

• 首先看看什么是插入 BST 的算法(别管它怎么样为数组实现...)
• 了解如何插入后，看看如何选择当前节点的左/右子节点，并将算法替换为您需要访问基于数组的 BST 中的节点的方式，这意味着您的 ( left,right) --> [2*i + 1],[2*i + 2] ... 这个计算给出了节点在数组中的位置

在 wikipedia 查看 BST 描述，以及以下示例:

 /* Inserts the node pointed to by newNode into the subtree rooted at treeNode */
 void InsertNode(Node* &treeNode, Node *newNode)
 {
     if (treeNode == NULL)
       treeNode = newNode;
     else if (newNode->key < treeNode->key)
       InsertNode(treeNode->left, newNode);
     else
       InsertNode(treeNode->right, newNode);
 }

替换数组中节点和值的访问方式，意思是替换treeNode->key , treeNode->left , treeNode->right以及如何访问子节点和数组中的值(计算数组中存储值的位置的索引)。

您可能不需要通过 Node* around 因为您将在数组上进行操作，并且您可能可以将索引传递给当前 node然后添加到它以获得左/右 child 的索引。

顺便说一句 (1)，如果它是基于 array 的，它可能不应该在内存中增长，您在开始时创建固定大小的数组，该数组足够大以容纳您的元素然后插入您的元素放入该数组的适当索引中。

顺便说一句 (2)，你从哪里得到你试图实现的比较树？ Z 怎么可能在 R 的左边？如果在 R 已经在树中时插入 Z 时根据相同的算法插入，您会执行 (Z < R ? go left : go right)所以 Z 最终会在从根 R 开始的正确路径上结束(与在 R 之后插入第一个 A 相同:(A < R ? go left : go right) 您最终在左侧路径上插入 A ...)

顺便说一句(3)，正如其他人提到的那样是正确的，最终的树在这里取决于插入的顺序。生成树的最低效的方法是对元素进行排序并一个一个地插入，因为您最终会得到链表，因此遍历将花费 O(n) 而不是 O(logN)。因此，如果您有固定的元素集，您要么选择随机元素，要么选择一致的中间元素。