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

Question

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

我不知道我如何防止使用左，右的索引覆盖数据...

我插入leftchild作为树[2 * I + 1]和rightchild作为树[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; 
} 

什么是正确的？...有没有人有任何基于阵列的suggstions插入？我似乎陷入了无限递归

Answer 1

我认为，您希望能够使用数组中的元素，而不必在插入新元素时重新排列数组？

显然，你会想把树的根节点放在索引零处。之后，您可以使用下降路径来构建二进制数字。例如，沿着左下角的树向左走，会得到数字0b1011 = 11（我用左边的1和右边的0）将1加1，所以这个节点将在索引12处下降。下降进一步在树中，使用逻辑或与下降的方向。

Answer 2

• 首先看看什么是 算法插入BST （不关心它是如何实现的 数组...）
• 一旦你了解如何插入，看看如何选择当前节点的左/右子节点，并用您需要访问基于BST的数组中的节点替换该算法，即您的（左，右） - > [2 * i + 1]，[2 * i + 2] ...该计算给出了阵列中节点的位置

看一看的BST说明在wikipedia，和下面的例子：

/* 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*身边，因为你的阵列上进行操作，并且可能是你可以围绕指数传递到当前node，然后只需添加到它以获取左/右孩子索引。

顺便说一句（1），如果是基于它可能不应该在内存中成长，你是大到足以容纳你的元素开始创建固定大小的数组，然后您插入元素融入适当阵列该数组的索引。

顺便说一句（2），你从哪里得到你试图实现的比较树？ Z如何在R的左边路径上？如果在R已经在树中时插入Z时按照相同的算法插入，则执行(Z < R ? go left : go right)，因此Z将从根R的右侧路径结束（与插入R之后的第一个A相同：(A < R ? go left : go right)您最终插入A在左边的路径上......）

Btw（3），正如其他人提到的那样，最终的树在这里取决于插入的顺序。生成树的最低效的方法是对元素进行排序并逐个插入，因为最终会得到链表，因此遍历将使用O（n）而不是O（logN）。所以如果你有固定的元素集合，你可以选择随机或一致的中间元素。

Answer 3

如果你想展示一个完整的二叉树数组，i_left=i_parent*2和i_right=i_parent*2+1效果很好（有i_root=1）。通过修改树中沿着从根到另一个节点的路径上的节点，BST应该被有效地更新;与位置无关的明确的左右子指针（或索引）允许这样做，因为移位子树的位置（或重用）不需要深度复制。

如果这个集合是固定的，那么拥有一个打包的二叉搜索树（基于父索引的左右子树的固定位置）的唯一方法就是：对它进行排序并递归，抓取已排序的子范围的中间，并将其用作BST子树的根。