C++バイナリ検索ツリーの実装ですべての要素が追加されない

Question

私はBSTの単純なC++実装を持っています。私は数字を追加して、それらを順番に印刷しようとしています。問題は、私が追加しようとする16個の数字のうち、12個（32,15,14、および3個を残して）を追加できることだけです。私のコンソールからの出力を以下に示します。

を数字を追加する前にツリーを印刷：
リストが 空
であるキー32が既に追加されています。
キー15はすでに が追加されています。
キー14は既に追加されています。
キー3にはすでに が追加されています。
番号を追加した後ためにツリーを印刷： 終了コードで終了しプログラム：0

#include <iostream> 

using namespace std; 
class BST { 

private: 

    struct node { 
     int data; 
     node * left; 
     node * right; 
    }; 

    node * root; 

    void addLeafPrivate(int data, node * n); 
    void printInOrderPrivate(node *); 


public: 

    BST(); 
    node * createLeaf(int data); 
    void addLeaf(int data); 
    void printInOrder(); 


}; 

int main() { 

    int TreeKeys[16]= {50, 76, 21, 4, 32, 64, 15, 52, 14, 100, 83, 2, 3, 70, 87, 80}; 
    BST bst; 

    cout << "Printing the tree before adding numbers: \n"; 
    bst.printInOrder(); 

    for (int i = 0; i < 16; i++) { 
     bst.addLeaf(TreeKeys[i]); 
    } 

    cout << "Printing the tree in order after adding numbers: \n"; 

    bst.printInOrder(); 

    return 0; 
} 

BST::BST() {root = NULL;} 

BST::node * BST::createLeaf(int data) { 

    node * n = new node; 

    n->data = data; 
    n->right = NULL; 
    n->left = NULL; 


    return n; 

} 

void BST::addLeaf(int data) { 
    addLeafPrivate(data, root); 
} 


void BST::addLeafPrivate(int data, node * n) { 

    if (root == NULL) { 
     root = createLeaf(data); 
    } 

    else if (data < n->data) { // add recursively on left left side. 
      if (n->left != NULL){ 
      addLeafPrivate(data, n->left); 
      } 
      else { // if left is empty 
       n->left = createLeaf(data); 
      } 
     } 

     else if (data > root->data) { // add recursively on right left side. 
      if (n->right != NULL) { 
       addLeafPrivate(data, n->right); 
      } 
      else { // right is empty 
       n->right = createLeaf(data); 
      } 


     } 

    else { 
     cout << "The key " << data << " has already been added.\n"; 
    } 
} 

void BST::printInOrder() { 

    printInOrderPrivate(root); 

} 

void BST::printInOrderPrivate(node * n) { 

    if (n != NULL) { 

     if (n->left != NULL) { 
      printInOrderPrivate(n->left); 
     } 
     cout << n->data << " "; 

     if (n->right != NULL) { 
      printInOrderPrivate(n->right); 
     } 


    } 

    else { 
     cout << "The list is empty\n"; 
    } 


} 

Answer 1

else if (data > root->data) { // add recursively on right left side. 

は

なければなりません

else if (data > n->data) { // add recursively on right left side. 

32に来ると問題が発生します。 dataの値を比較して例外をスローするのではなく、がすでに50のままになっているので、n->dataの代わりにroot->dataを使用したときに、アルゴリズムは既に32に挿入されているとみなします。

So：nullの場合は右と左をチェックし、dataの方が大きいかどうかを比較し、同等かどうかを確認してください。そうすることで、このようなバグを見つけやすくなります。