Невозможно вернуть узел дерева, когда он найден
Как мне вернуть узел дерева, когда я его нашел?
Итак, у меня есть двоичное дерево, и когда я ищу в дереве то, что я искал, было найдено, я хочу вернуть указатель на этот узел, чтобы я мог использовать этот узел в другой функции. Есть моя функция поиска:
Tnode *Tsearch(Tnode *r, char *word) {
if (r == NULL) {
printf("%s NOT FOUND\n", word);
return NULL;
}
int comp = strcasecmp(r->word, word);
if ( comp == 0) {
printf("%s FOUND\n", r->word);
return r;
}
else if ( comp > 0) {
Tsearch(r->left, word);
}
else if ( comp < 0) {
Tsearch(r->right, word);
}
return 0;
}
Моя проблема в том, что когда я пытаюсь использовать возврат функции Tsearch, она не работает, и я действительно не могу понять, почему и как ее решить.
Функция, в которой я хочу использовать этот возвращенный узел из функции поиска, следующая:
int Tsearch_ref(Tnode *r, char (*words)[30]) {
if (r == NULL) {
return 0;
}
printf("%s, %d", words[0], (int)strlen(words[0]));
Tsearch(r,words[0]);
auxT = Tsearch(r,words[0]);
Lnode *aux = auxT->head;
printf("Title: %s\n", ((Book *)aux->ref)->title);
while(aux != NULL) {
aux_arr[i].ref=aux->ref;
printf("Title: %s\n", ((Book *)aux_arr[i].ref)->title);
printf("%p\n", &(aux_arr[i].ref));
aux = aux->next;
i++;
}
}
Эта функция не завершена, потому что я пытался решить проблему возврата, но в основном я хочу взять этот узел дерева, внутри которого есть список, и поместить этот список во временный массив.
Структуры следующие:
typedef struct {
char *title;
char isbn13[ISBN13_SIZE];
char *authors;
char *publisher;
int year;
} Book;
typedef struct lnode {
struct lnode *next;
void *ref;
} Lnode;
typedef struct tnode {
struct tnode *left;
struct tnode *right;
char *word;
Lnode *head;
} Tnode;
Это мой первый вопрос здесь, в StackOverflow, поэтому, если вам понадобится дополнительная информация о чем-либо, я, очевидно, предоставлю ее.
Заранее спасибо!
Ответы 2
Вам нужно изменить рекурсивные вызовы Tsearch, чтобы фактически вернуть найденный узел. Итак, вместо этого кода:
else if ( comp > 0) {
Tsearch(r->left, word);
}
else if ( comp < 0) {
Tsearch(r->right, word);
}
сделай это:
else if ( comp > 0) {
return Tsearch(r->left, word);
}
else if ( comp < 0) {
return Tsearch(r->right, word);
}
Обратите внимание, что если ваше дерево очень глубокое, вы можете использовать весь стек вызовов и вызвать исключение.
невозможно сказать, почему вы ничего не распечатываете. Я предполагаю, что вам нужно пройти код в gdb или каком-нибудь отладчике и посмотреть, каково значение aux->ref. Возможно, вам придется создать локальную переменную Book *b = aux->ref; для проверки значения в отладчике.
Хорошо, поэтому поздно ночью работать плохо, Tsearch_ref не печатал, потому что я не вызывал функцию. Я это понимаю после использования отладчика. Большое спасибо за огромную помощь!
Почему бы не использовать цикл пока?
Tnode *Tsearch(Tnode *r, char *word) {
Tnode *cur = r;
int comp;
while (cur != NULL)
{
if ((comp = strcasecmp(cur->word, word)) == 0)
{
printf("%s FOUND\n", cur->word);
return cur;
}
else if (comp > 0)
{
/* Move to the left child */
cur = cur->left;
}
else
{
/* Move to the right child */
cur = cur->right;
}
}
printf("NOT FOUND\n");
return NULL;
}
Моя первая версия была такой же, но у меня была та же проблема, потому что я не делал cur = cur->left/right;, поэтому я сделал вторую версию и столкнулся с той же проблемой! Но спасибо за альтернативу!
Он решил ошибку (и я понял почему), но теперь у меня все еще есть другая проблема, например, когда в
printf("Title: %s\n", ((Book *)aux->ref)->title);он ничего не печатает, как я ожидал. Что может быть причиной этого? Еще раз спасибо!