BST продолжает получать ошибку сегментации

#c #g #binary-search-tree

#c #g #двоичное дерево поиска

Вопрос:

РЕДАКТИРОВАТЬ: запуск его через gdb дает

 Program received signal SIGSEGV, Segmentation fault.
0x0000000000400e4c in Tree::findKey(std::basic_string<char, std::char_traits<char>, std::allocator<char> >amp;, int, Tree::Node*) ()

Нужна помощь с моим первым BST-кодом, я продолжаю получать ошибку сегментации, я думаю, что это утечка памяти? если это так, я не знаю, где / как исправить, вот коды, которые, по моему мнению, вызывают проблему. Это потому, что у меня еще не настроен конструктор копирования??

tree.cpp файл

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

bool Tree::insert(int k, string s)
{
  return insert(root, k, s);
}
//HELPER Call find data with key function
bool Tree::findKey(stringamp; s, int k)
{
    return findKey(s, k, root);
}
bool Tree::insert(Node*amp; currentRoot, int k, string s)
{
  if(currentRoot == NULL){
    currentRoot = new Node;
    currentRoot->key = k;
    currentRoot->data = s;
    currentRoot->left = NULL;
    currentRoot->right = NULL;
    return true;
  }
  else if (currentRoot->key == k)
    return false;
  else if (currentRoot->key > k)
    return insert(currentRoot->left, k, s);
  else
    return insert (currentRoot->right,k, s);
}
bool Tree::findKey(stringamp; s, int k, Node* currentRoot)
{
    if (currentRoot->key == k){
        s = root->data;
        return true;
    }
    else if (root->key < k)
        return findKey (s, k, root->right);
    else if (root->key > k)
        return findKey (s, k, root->left);
    else
        return false;
}

main.cpp

 int main()
{
string sout;
  Tree test;
    test.insert(1, "a");
    test.insert(2, "b");
    test.insert(3, "c");
    test.findKey(sout, 3);
    cout<<sout<<endl;
  return 0;
}

1. Использовали ли вы ‘valgrind’, чтобы найти место, где ваша реализация сталкивается с ошибкой seg?

2. Как насчет запуска его в отладчике или в IDE, чтобы вы могли сообщить нам, в какой строке он выполняет сегментацию?

3. Вы действительно хотите передать ссылку на указатель? bool Tree::insert(Node *amp; currentRoot, int k, string s)

4. @tgmath: Ссылка на указатель выглядит нормально, потому что он хочет инициализировать переданный указатель. И a *amp; , безусловно, новичку легче понять и использовать, чем a ** .

5. Tree::findKey должен использовать только currentRoot, а не root.

Ответ №1:

 bool Tree::findKey(stringamp; s, int k, Node* currentRoot)
{
    if (currentRoot->key == k){
        s = root->data;
        return true;
    }
    else if (root->key < k)
        return findKey (s, k, root->right);
    else if (root->key > k)
        return findKey (s, k, root->left);
    else
        return false;
}

Вы всегда используете root вместо currentRoot , поэтому на самом деле вы не спускаетесь по дереву и в какой-то момент получите stackoverflow. Кроме того, вам не хватает проверки, currentRoot есть NULL ли это, потому что, если вы получите к нему доступ, вы получите хороший segfault (это то, что имел в виду @tgmath).

 bool Tree::findKey(stringamp; s, int k, Node* currentRoot)
{
    if(currentRoot == NULL)
        return false;
    // as before ...
}

Ответ №2:

Я вижу некоторую возможную ошибку сегментации, когда смотрю на ваш метод. Просто подумайте о крайних случаях.

Что здесь происходит?:

 Tree test; 
test.findKey(sout, 3);

или

 Tree test;
test.insert(1, "a");
test.findKey(sout, 3);

Исправьте эти случаи и продолжайте.