C＆＃x2B;＆＃x2B;二进制树segfault（与类实现）

Question

我一直在尝试在C ++中实现BST，并编写了这些功能以将新节点插入其中。但是，我现在很困难地试图理解为什么此代码会导致segfault。

这可能与我没有将root地址传递给实用程序功能的事实有关，因为当我这样做时，插入功能开始正常工作。但是，我不明白为什么这种特定的实现不起作用。 我真的很感激是否可以澄清

class Bst {
    private:
        struct bstNode *root;
        struct bstNode* insertUtil(int, struct bstNode*);
        void delTree(struct bstNode**);
    public:
        Bst();
        ~Bst();
        void insert(int);
};

 /// struct bstNode *root = NULL;

struct bstNode* Bst::insertUtil(int x, struct bstNode *r){
    if(r == NULL){
        r = newNode(x);
    }
    if(x < r->data){
        r->left = insertUtil(x, r->left);
    } else{
        r->right = insertUtil(x, r->right);
    }
    return r;
}

void Bst::insert(int x){
    if(root == NULL){
        root = newNode(x);
        return;
    }
    insertUtil(x, root);
}

如果您有兴趣， 完整的代码： https://codepen.io/ adrasti/pen/nwyvozy

Answer 1

我认为这是一个逻辑错误。

此行（在中insertutil中）：

r = newNode(x); //no return

因此，程序将执行

insertUtil(x, r->left);

或

r->right = insertUtil(x, r->right);

将执行：永远

r = newNode(x); //no return

不要停止直到出现。

我也在学习C ++，如果我不正确，我希望得到纠正。

Answer 2

绝对会错过bst :: intertutill您可以通过在该功能中进行小重构来快速的

struct bstNode *Bst::insertUtil(int x, struct bstNode *r)
{
  if (r == nullptr)
  {
    r = newNode(x);
    return nullptr;
  }
  if (x < r->data)
  {
    r->left = insertUtil(x, r->left);
  }
  else
  {
    r->right = insertUtil(x, r->right);
  }
  return r;
}

条件

void Bst::insert(int x)
{
  insertUtil(x, root);
}

中断 溢出。

如果搜索此操作，您可以将-fsanitize =地址 flag添加到GCC编译器或用户valgrind

也可以重构代码以成为更多C ++现代风格，但是我可以粘贴它稍后你