Необработанное исключение с двоичным деревом поиска

Question

Я понятия не имею, что его вызывает. Можете ли вы, ребята, помочь мне? Поскольку в последний раз люди жаловались, потому что я должен публиковать только MCVE, а не весь исходный код. Я просто напишу, что (я думаю) связано с проблемой. В основном это двоичное дерево поиска, а необработанное исключение связано с методом добавления класса BST.

node.h

#ifndef NODE_H 
#define NODE_H 

#include "Button.h" 

class Node 
{ 
private: 

    int key; 
    Node* left; 
    Node* right; 
    Button nextPlay; 
    bool used; 

public: 

    Node(); 
    Node(int k, int x, int y); 

    void setLeft(Node* n); 
    Node* getLeft(); 
    void setRight(Node* n); 
    Node* getRight(); 
    Button getPlay(); 
    int getKey(); 
    void setUsed(); 
    bool getUsed(); 

}; 

#endif 

node.cpp

#include "Node.h" 

Node::Node() 
{ 
    key = 0; 
    left = NULL; 
    right = NULL; 
    //nextPlay = NULL; 
    used = false; 
} 

Node::Node(int k, int x, int y) 
{ 
    key = k; 
    left = NULL; 
    right = NULL; 
    nextPlay.getPosition()->x = x; 
    nextPlay.getPosition()->y = y; 
    used = false; 
} 

void Node::setLeft(Node* n) 
{ 
    left = n; 
} 

Node* Node::getLeft() 
{ 
    return left; 
} 

void Node::setRight(Node* n) 
{ 
    right = n; 
} 

Node* Node::getRight() 
{ 
    return right; 
} 

Button Node::getPlay() 
{ 
    return nextPlay; 
} 

int Node::getKey() 
{ 
    return key; 
} 

void Node::setUsed() 
{ 
    used = true; 
} 

bool Node::getUsed() 
{ 
    return used; 
} 

BST.h

#ifndef BST_H 
#define BST_H 

#include "Node.h" 

class BST 
{ 
private: 

    Node* root; 

    bool add(Node* n, int k, int x, int y); 
    int remAll(Node* n); 
    Button get(Node* n); 

public: 

    BST(); 
    ~BST(); 

    bool add(int k, int x, int y); 
    int remAll(); 
    Button get(); 

}; 

#endif 

BST.cpp

#include "BST.h" 

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

BST::~BST() 
{ 
    remAll(); 
} 

bool BST::add(Node* n, int k, int x, int y) 
{ 
    bool success; 
    if (n = NULL) 
    { 
     n = new Node(k, x, y); 
     success = true; 
    } 
    else 
    { 
     if (k == n->getKey()) 
     { 
      success = false; 
     } 
     else 
     { 
      if (k < n->getKey()) 
      { 
       Node* leftTree = n->getLeft(); 
       success = add(leftTree, k, x, y); 
       n->setLeft(leftTree); 
      } 
      else 
      { 
       Node* rightTree = n->getRight(); 
       success = add(rightTree, k, x, y); 
       n->setRight(rightTree); 
      } 
     } 
    } 
    return success; 
} 

int BST::remAll(Node* n) 
{ 
    int number; 
    if (n == NULL) 
    { 
     number = 0; 
    } 
    else 
    { 
     number = remAll(n->getLeft()); 
     number += remAll(n->getRight()); 
     delete n; 
     number++; 
    } 
    return number; 
} 

Button BST::get(Node* n) 
{ 
    if (n != NULL) 
    { 
     if (!n->getUsed()) 
     { 
      n->setUsed(); 
      return n->getPlay(); 
     } 
     else 
     { 
      Node* rightTree = n->getRight(); 
      if (rightTree != NULL) 
      { 
       return get(rightTree); 
      } 
      else 
      { 
       Node* leftTree = n->getLeft(); 
       if (leftTree != NULL) 
       { 
        return get(leftTree); 
       } 
      } 
     } 
    } 
} 

bool BST::add(int k, int x, int y) 
{ 
    return add(root, k, x, y); 
} 

int BST::remAll() 
{ 
    int number = remAll(root); 
    root = NULL; 
    return number; 
} 

Button BST::get() 
{ 
    return get(root); 
} 

Когда я запустить программу необработанных точки исключения для:

int Node::getKey() 
{ 
    return key; 
} 

, который используется в методе добавления в BST.

Answer 1

Если добавить примечание к пустому BST, исполнение будет:

bool BST::add(int k, int x, int y) 
{ 
    return add(root, k, x, y); 
} 

Как root является NULL, следующий будет в add(root, k, x, y):

bool success; 
    if (n = NULL) {  // <=== OUCH !!! you set n to NULL if if wasn't 
     ...    // this is ignored because the condition is always NULL 
    } 
    else {    // so the else part is executed  
     if (k == n->getKey()) { // <======OUCH !!! remember n is NULL 

Таким образом, на данном этапе, из-за двух ошибок (см. выше комментарии OUCH), вы разыскиваете нулевой указатель n. Это вызывает ваш segfault.

Примечание: С технической точки зрения, так как getKey() не является виртуальным, что функция может фактически дозвонились с this будучи NULL, так что выдаёт ошибку сегментации будет срабатывать только при key доступе. Но это зависит от реализации.

Как это решить?

Во-первых, исправить случай, когда узел NULL:

if (n == NULL) // == instead of = 

Но этого недостаточно. Ваш рекурсивный алгоритм ожидает, что следующий оператор изменяет указатель в дереве. К сожалению, в действительности это только изменяет только локальную переменную указатель, и пусть дерево, как это было:

n = new Node(k, x, y); // store the newly created node, but... n is local 

Ваш подход будет работать только если n будет ссылка на оригинальный указатель на дереве. Вы можете добиться этого, изменив подпись функции:

bool BST::add(Node*& n, int k, int x, int y) // pass n by reference 

Answer 2

Проблема заключается в создании узла. Вы передаете указатель по значению в методе add вместо ссылки. Подпись функции должна быть bool BST::add(Node*& n, int k, int x, int y). Также измените n = NULL на n == NULL, чтобы сравнить вместо asign.

Надеюсь, это поможет!

Answer 3

Часто-Предложен метод, чтобы избежать ошибок вида

if (n = NULL) { 

, чтобы попытаться переключить свой стиль, чтобы сделать

if (NULL == n) { 

Это должно привести компилятор дает вам сообщение об ошибке. Оператор L.H.S больше не является l-значением и становится незаконным для '=', но не для '==', что мешает вам случайно сделать это. Я сделал эту ошибку пару раз на ранней стадии своей карьеры и постоянно переключался.