插入基於數組的二叉搜索樹？ 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子樹的根。