二進制搜索樹C++（Parents）

我只需要在我的BST上多一點幫助。這是我的BST看起來插入時這樣的：二進制搜索樹C++（Parents）

R，L，J，G

     R --Root at Index 0 
        /\ 
    L @ Index1  L NULL 
       /\ 
    J @ Index3 J NULL 
       /\ 
    G @ Index7 G NULL

這裏，使得它發生的代碼。

void BST::insert(const data &aData) 
{ 
    if (items[Parent].empty) 
    { 
     items[Parent].theData = aData; // insert at leaf. 
     items[Parent].empty = false; 
     size++; 

     return; 
    }   
    for (int i = 0; i <= size; i++) 
    { 
     if (aData < items[Parent].theData) 
     { 
      if (items[2*i+1].empty) 
      { 
      items[2*i+1].theData = aData; 
      items[2*i+1].empty = false; 
      } 
      else 
          { 
      // we must already have a left child to some root. 
           Parent++; So make the previous data the root??? 
      if (items[Parent].empty) 
      { 
       items[Parent].theData = items[2*i+1].theData; 
       items[Parent].empty = false; 
       Parent = (i-1)/2; 
      } 
          } 
     } 
     else 
     { ...// do the same for data greater than but with items[2*i+2] }

我的問題是，我什麼時候需要做一個新的根？我什麼時候需要創建一個新的根？爲了重新比較？

這種方法是否正確？謝謝那些甚至兩個看我的帖子:)

//構造函數的BST類和它的私人部分。

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

來源

2009-11-17 user40120

您可以簡化問題，因此包含完整的代碼是可行的嗎？或者把它寫入（完整的）僞代碼？沒有指出像「item」，「Parent」，「data」等事情，這使得很難破譯你正在做的事情。 – 2009-11-17 21:03:42

你爲什麼使用數組？ – 2009-11-17 21:06:58

我發佈的構造函數，還有它的私人部分，我定義我的數據數組。對於那個很抱歉！ – user40120 2009-11-17 21:07:26

你的邏輯（相當模糊的，我必須說）似乎是錯誤的：什麼樣的「如果」順序是什麼？

if (items[2*i+1].empty) 
{ 
} 
else if (!items[2*i+1].empty) 
{ 
    if (items[2*i+1].empty) 
    { 
     // any code here is unreachable 
    } 
}

來源

2009-11-17 21:12:19 BostonLogan

我想知道我自己。它繼續前進，所以我沒有問題。 – user40120 2009-11-17 21:16:04

我認爲如果我至少可以構建它。回去做好它會很容易。我很難第一次編寫高效的代碼。 – user40120 2009-11-17 21:17:50

我想我需要它做的是循環迭代 – user40120 2009-11-17 21:21:06

我建議你重新實現這個以遞歸方式工作。事情是這樣的：

void BST::insert(const data& aData, int pos) { 
    if (items[pos].empty) { 
     // insert it here 
    } 
    else (aData < items[pos].theData) { 
     // go to left child 
     insert(aData, 2*pos + 1); 
    } 
    else { 
     // go to right child 
     insert(aData, 2*pos + 2); 
    } 
}

這不是真的清楚什麼家長，leftChild和rightChild在你的類做，但是這是一個單獨的問題。

來源

2009-11-17 21:46:39 Andrey

二進制搜索樹C++（Parents）

回答

相關問題