數組BST的插入排序如何工作？

我試圖做遞歸..父母的整數變量就像我，符合公式2*i +1爲leftChild的和2*i +2的權利。數組BST的插入排序如何工作？

void BST::insert(const data &aData) 
{ 
    if (items[Parent].empty) 
    { 
     items[Parent].theData = aData; 
     items[Parent].empty = false; 
    } 
    else if (aData < items[Parent].theData) 
    { 
     Parent = 2 * Parent + 1; 
     if (Parent >= maxSize) this->reallocate(); 
     this->insert(aData); 
    } 
    else 
    { 
     Parent = (2 * rightChild++)+ 2; 
     if (Parent >= maxSize) this->reallocate(); 
     this->insert(aData); 
    } 
}

這將是比原來的父項... 時工作正常，但當我找到的東西，是較大的這一切搞砸了：X

void BST::reallocate() 
{ 
    item *new_array = new item[maxSize*2]; 

    for (int array_index = 0; array_index < maxSize; array_index++) 
    { 
     if (! items[array_index].empty) 
     { 
      new_array[array_index].theData = items[array_index].theData; 
     } 
    } 
    maxSize *= 2; 
    delete [] items; 

    items = NULL; 
    items = new_array; 
}

這裏是我的構造函數等等沒有人會再糊塗那麼我：

BST::BST(int capacity) : items(new item[capacity]), size(0), Parent(0), 
leftChild(0), rightChild(0) 
{ 
    items->empty = true; 
    maxSize = capacity; 
} 
private: 
    int size; // size of the ever growing/expanding tree :) 
    int Parent; 
    int maxSize;  
    int leftChild; 
    int rightChild; 
    struct item 
    { 
     bool empty; 
     data theData; 
    }; 
    item *items; // The tree array

上方插入函數實際上是最好的，我可以得到..

        R 
           /\ 
          / \ 
          / \ 
          L  X 
          /\ /\ 
          J V K T <--The only out of place node. 
         /\ \ 
         /NULL \ 
         G  /
           P

當插入：R, L, J, G, X, K, V, P, T的順序

來源

2009-11-18 user40120

這只是一個遞歸定義的插入函數，試圖完成。 – user40120 2009-11-18 00:45:19

T是插入的最後一項，是原因嗎？ – user40120 2009-11-18 01:14:30

我會懷疑你的問題是在這條線：

Parent = (2 * rightChild++)+ 2;

你爲什麼要使用rightChild在這裏，而不是(2 * Parent) + 2？

爲了讓事情更清晰，你可能想一些簡單的內聯函數添加到您的類計算左/右兒童和家長的指標，給出指數：

inline int getLeftChildIndex(int nodeNdx) { return (nodeNdx * 2) + 1; } 
inline int getRightChildIndex(int nodeNdx) { ... } 
inline int getParentIndex(int nodeNdx) { ... }

您可能還需要考慮使用類別search()或find()方法（我假設它有一個）來確定插入新節點的位置。搜索函數應該返回現有節點的索引（由您決定如何處理插入重複值）或者應該插入新值的索引。

來源

2009-11-24 00:08:38 sdtom

數組BST的插入排序如何工作？

回答

相關問題