Поиск элемента в дереве(ошибка)

238

15 сентября 2018, 05:10

Подскажите, плиз. Делаю поиск в дереве, нахожу и возвращаю указатель, а он выдаёт ошибку. Компилятор Dev-C++.

Node* SearchNode(Node* tree, std::string str) { 
 if(!tree) 
       return NULL; 
 else if(tree->name == str) 
       return tree;    
 else if(str < tree->name) 
        SearchNode(tree->left, str); 
  else 
        SearchNode(tree->right, str);}

Answer 1

Все пути выполнения не-void функции в С++ должны заканчиваться return (или throw, как заметил, @acade):

Node* SearchNode(Node* tree, std::string str) 
{ 
  if (!tree) 
    return NULL; 
  else if (tree->name == str) 
    return tree;    
  else if (str < tree->name) 
    return SearchNode(tree->left, str); 
  else 
    return SearchNode(tree->right, str);
}

В противном случае - поведение не определено. (Исключением из этого правила является только функция main).

Передача параметра str "по ссылке" const std::string &str, вместо передачи "по значению" - хорошая и правильная идея, но это не более чем оптимизация, на работоспособность кода не влияющая.

P.S. Как ни странно, исправление std::string str на const std::string &str может неожиданно сделать ваш исходный вариант внешне "работоспособным", несмотря на отсутствующие return в третьей и четвертой ветке. Но это не более чем хорошо известный наведенный эффект, случайное проявление неопределенного поведения.

Answer 2

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

Node* SearchNode(Node* tree, const std::string& str) { 
    while (tree && tree->name != str) 
        tree = str < tree->name ? tree->left : tree->right;
    return tree;
}