c++ - 在 BST 中插入节点的逻辑错误

Question

我已经为 BST 编写了节点插入代码。但它似乎无法正常工作。它给出了“段错误”。这是我的插入逻辑。

    void insert(Node* root, int data){
     if(root==NULL){
      root= new Node;
      root->data = data;
      }
    else if(data < root->data){
      insert(root->left,data);
      }
    else if(data> root->data){
      insert(root->right,data);
      }
    }

我该如何解决？谢谢

编辑:所以我尝试了一些东西，这个就可以了

    Node* insert(Node* &root, int data){
    if(root==nullptr){
    root = create(data);
    return root;
    }
    else if(data < root->data){
    insert(root->left,data);
    }
    else if(data> root->data){
    insert(root->right,data);
    } 
    }

Node* root 和 Node* &root 有什么区别？

Answer 1

好吧，如果节点不存在(它是NULL)，你只是将你的root指针设置为new Node，但是您缺少将其“挂断”给它的 parent 。如前所述，自 C++11 起，您可以使用 unique_ptr-s 来避免内存泄漏(即当您忘记删除对象时)。看起来像:

struct Node {
    int data = -1;  // not initialized
    std::unique_ptr<Node> l;
    std::unique_ptr<Node> r;
}

void insert(Node *root, int data) {
    if (root->data == -1) {
        root->data = data;
        return;
    }
    if (data < root->data) {
        if (!root->l) {
            // hanging new left node up
            root->l = std::make_unique<Node>();  // std::make_unique comes since C++14
        }
        insert(root->l.get(),  // getting raw ptr
               data);
    }
    else {
        if (!root->r) {
             // hanging new right node up
             root->r = std::make_unique<Node>();
        }
        insert(root->r.get(), data);
    }
}

此外，您可能对名为 treap 的数据结构感兴趣，因为如果您插入例如递增序列，您的实现可能会工作很长时间:

Node root;

for (int i = 1; i <= 100'000; i++) {
    insert(&root, i);
}

所以你的二叉树在这种情况下看起来像:

1
 \                  
  2                 <=
   \                <= very long path
    3               <=
     \
     ...
       \
     100'000

Treap 有助于避免 BST 中的长路径。