二進制搜索樹陣列Imp。 C++

我只是在插入到數組中遇到問題...並讓孩子從根分支或「父母」..二進制搜索樹陣列Imp。 C++

我一直在試圖插入數據到一個基於數組的實現BST：

BST::BST(int capacity) : items(new item[capacity]), size(0) 
{ 
    // define the constructor to the BST Class. 
} 

void BST::insert (const data& aData) 
{ 
    if (items[root].empty) // make the first data the root. 
    { 
     items[root].theData = aData; 
     items[root].empty = false; 
     size++; 
    } 
    else if (items[root].theData.getName() < aData) 
    { 
     items[leftChild].theData = aData; // will be overwritten... 
     this->insert(aData); 
    } 
    else if (aData < items[root].theData.getName()) 
    { 
     items[rightChild].theData = aData; 
     this->insert(aData); 
    } 
}

有幾件事情是錯誤的。首先讓我說第一個傳入的數據將是根。所有其他數據將與它進行比較。當我遞歸調用「插入」時，基本上我是如何「思考」我是「遍歷」（如果它是一個鏈表）。我的主要問題是知道我的左右兒童會被覆蓋。我想知道如何保持從孩子的「節點」分支......？

這是我的BST類的頭文件，我也擔心如果我已經設置了成員的權利和一切..？

class BST 
{ 
public: 
    BST(int capacity = 5); 
    BST(const BST& aTable); 

    void insert(const data& aData); 
     .... 
private: 
    int size; // size of the ever growing/expanding tree :) 

    struct item 
    { 
     bool empty; 
     data theData; 
    }; 

    item * items; // The tree array 
    int rightChild; // access to the RHS 
    int leftChild; // access to the LHS 
    int root; // index to the root 
};

我有另一個源文件，「數據」，我打電話，「getname」。我已經定義了三種簡單的方法，到目前爲止是賦值運算符重載，比較「<」過載和構造函數的數據類：

data::data(char const * const name) : name(new char[strlen(name)+1]) 
{ 
    if (name) 
    { 
     strcpy(this->name , name); 
    } 
    else this->name = NULL; 
} 

data& data::operator=(const data& data2) 
{ 
    if (this != &data2) // check for selfassignment 
    { 
     delete [] name; 
     name = NULL; 

     this->name = new char[strlen(data2.name)+1]; 
     strcpy(this->name , data2.name); 
    } 
    return *this; 
    } 

bool operator< (const data& d1, const data& d2) 
{ 
    if (strcmp(d1.getName(), d2.getName()) == -1) 
    { 
     return false; 
    } 
    else if (strcmp(d1.getName(), d2.getName()) == 1) 
    { 
     return true; 
    } 
    return false; // if they are equal return false 
}

來源

2009-11-10 user40120

我看到了一些問題。 leftChild和rightChild應該是項目結構的成員，而不是BST的成員，因爲它們對於每個項目都不相同（或者它們不應該作爲字段存在並被動態計算）。我看到沒有任何代碼將leftChild和rightChild設置爲任何值。

它看起來像你試圖遞歸定義insert。您應該定義一個插入幫助器函數，該函數可以同時獲取插入點的項目和索引。這應該讓你走上正軌。

該wikipedia article有更多的僞代碼，你可以看看。

來源

2009-11-10 23:53:05

好的。鑑於他們應該是項目結構的成員，使用它們作爲我的數組實現的索引還是明智的嗎？ – user40120 2009-11-10 23:59:12

這就是我的困惑所在。如何作爲一個數組工作？我已經完成鏈表，但我似乎無法完成連接。 – user40120 2009-11-11 00:00:44

鏈表實現是否使用指針或索引？相同的技術將在這裏工作，只是每個項目有兩個下一個指針而不是一個。還有幾件事需要考慮：一個新項目是如何分配的（eqivalently，leftChild和rightChild如何設置）？如果物品沒有離開孩子，那麼leftChild有什麼價值？如何實現查找（應該比插入更容易）？ – 2009-11-11 00:10:40

二進制搜索樹陣列Imp。 C++

回答

相關問題