c++ - 该函数不会向我的 bst 树添加任何内容

Question

class node{
public:
    int data;
    node *left;
    node *right;
};

class BFStree{
public:
    void insert(int key);
    void deleteNode(int key);
    void inorderTraversal(node *temp);
    void inorder();
    node *root;
    BFStree(){
        root = NULL;
    }
};

 void BFStree::insert(int key){
    node *temp = root;
        while(temp!=NULL){
            if(key>temp->data){
                temp = temp->right;
            }
            else if(key<temp->data){
                temp = temp->left;
            }
            else{
                cout << "NOT ALLOWED TO HAVE SAME DATA" << temp->data << " " << key << endl;
            }
        }
        node *temp2 = new node;
        temp2->data = key;
        cout << key << " inserted" << endl;
        temp2->left = NULL;
        temp2->right = NULL;
        temp = temp2;
    }

int main(){
    BFStree t;
    t.insert(7);
    t.insert(3);
    t.insert(21);
}

我正在尝试使用上面的函数将数据插入到 bst 树中，但它什么也没做，即使根是 NULL但是当我使用以下功能时，工作就完成了。我不明白我在这两个代码中做了什么不同的事情。我是编程新手，所以我很怀疑。请帮我清除它。

void BFStree::insert(int key){
    node *temp = root;
    if(temp==NULL){
        temp = new node;
        temp->data = key;
        temp->left = NULL;
        temp->right = NULL;
        root = temp;
        return;
    }
    while(1){
        if(key>temp->data){
            if(temp->right==NULL){
                node *temp2 = new node;
                temp2->data = key;
                temp2->left = NULL;
                temp2->right = NULL;
                temp->right = temp2;
                break;
            }
            else{
                temp = temp->right;
            }
        }
        else if(key<temp->data){
            if(temp->left==NULL){
                node *temp2 = new node;
                temp2->data = key;
                temp2->left = NULL;
                temp2->right = NULL;
                temp->left = temp2;
                break;
            }
            else{
                temp = temp->left;
            }
        }
    }
}

Answer 1

第一个函数的主要问题是您只是遍历树直到找到一个空值，然后将该空值赋给 temp。

之后，您创建一个新节点并为 temp 分配新节点的引用。但是您的临时节点未连接到树。并且临时节点与其树的父节点或根节点之间没有连接。

而在第二个例子中:

if(temp->right==NULL){
            node *temp2 = new node;
            temp2->data = key;
            temp2->left = NULL;
            temp2->right = NULL;
            temp->right = temp2;
            break;
 }

这是关键，您将新创建节点的引用存储在其父节点的右或左子节点中。