Найти String в BST

Question

Я построил BST, который содержит названия альбомов и годы, и он построен в соответствии с годами. Но я хочу ввести названия альбомов, и это должно дать год. Так что я построил этот код часть:

int FindString(treeAlbum *node,char albumTitle[]) 
{ 

    FindString(node->Left,albumTitle); 
    FindString(node->Right,albumTitle); 
    if(!strcpy(node->albumTitle, albumTitle)) 
    { 
     return node->year; 
    } 
} 

И treeAlbum структура

struct treeAlbum{ 
     char albumTitle[100]; 
     int year; 
     struct treeAlbum *Left; 
     struct treeAlbum *Right; 
} 

Наконец, этот код выдаст ошибку (Сегментация Fault). Как я могу это исправить ? Спасибо.

Answer 1

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

int FindString(treeAlbum *node,char albumTitle[]) 
{ 
    if (!node) 
    { 
     // Return something sane here 
     return ERROR_NOT_FOUND; 
    } 

    FindString(node->Left,albumTitle); 
    FindString(node->Right,albumTitle); 
    if(!strcpy(node->albumTitle, albumTitle)) 
    { 
     return node->year; 
    } 
} 

Однако, код имеет некоторые другие вопросы:

1. Что вы делаете с возвращаемые значения из рекурсивных вызовов в FindString. Сейчас ты ничего не делаешь.
2. Вы используете strcpy, но, возможно, вы имеете в виду strcmp.
3. У вас есть двоичное дерево поиска, но вы выполняете поиск после исправления. Это линейно по размеру вашего дерева, но вы должны иметь возможность использовать сортировку BST для получения бинарного дерева log (n). А именно, посмотрите на альбом в текущем узле и посмотрите, все ли вы сделали, нужно искать влево или искать.

Answer 2

Первое, что вы делаете в FindString это вызов FindString снова node->Left. Либо node->Left в конечном итоге составляет null (если ваше дерево правильно построено), что вызовет segfault или это более ранний узел в дереве (в этом случае ваша рекурсия заставит стек заполнить). Проверка нулевого случая обязательно необходима!

Answer 3

Вы хотите использовать strcmp, а не strcpy. Вы должны оценить результат двух вызовов FindString() и продолжить работу, только когда они не удались.