C++ 二叉搜索树实现不添加每个元素

Question

我有一个 BST 的简单 C++ 实现。我只是想按顺序添加数字并打印出来。问题是，在我尝试添加的 16 个数字中，我只能添加 12 个(遗漏了 32、15、14 和 3)。我的控制台的输出如下所示:

Printing the tree before adding numbers:
The list is empty
The key 32 has already been added.
The key 15 has already been added.
The key 14 has already been added.
The key 3 has already been added.
Printing the tree in order after adding numbers:
2 4 21 50 52 64 70 76 80 83 87 100
Program ended with exit code: 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 时，问题就开始了。由于 21 已经在 50 的左侧，当您执行 root->data 时，您的算法认为它已经插入 32 > 而不是正确的 n->data，而不是比较 data 值并抛出异常。

因此:检查左右是否为 null，比较 data 是否更大或更小，并检查是否相等。这样做可以让您更轻松地找到此类错误。