Как создать двоичное дерево поиска из строк? - PullRequest
Новая
       13

Как создать двоичное дерево поиска из строк?

0 голосов
/ 26 мая 2019

У меня есть следующая задача: создать двоичное дерево поиска из строк, а затем распечатать их в алфавитном порядке. Как пример, 

orange
melon
apple
grapes
plum
banana

должно иметь 

apple
banana
grapes
melon
orange
plum

как вывод. Я написал решение, но у меня есть проблема: печатается только последняя строка ввода (в данном примере это banana), и я не могу найти ошибку в своем коде. 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node {
    char *data;
    struct Node *left;
    struct Node *right;
} Node;
Node* getFreeNode(char *value) {
    Node* tmp = (Node*)malloc(sizeof(Node));
    tmp->left = tmp->right = NULL;
    tmp->data = value;
    return tmp;
}
void insert(Node **head, char *value) {
    Node* tmp = (Node*)malloc(sizeof(Node));
    tmp = *head;
    if (*head  == NULL) {
        *head = getFreeNode(value);
        return;
    }
    else{
        if (strcmp(value, tmp->data) > 0) {
            return insert(&(tmp->right), value);
        }
        else if (strcmp(value, tmp->data) < 0) {
            return insert(&(tmp->left), value);
        }
    }
}
void print_tree(Node *t)
{
    if (!t) return;
    print_tree(t->left);
    printf("%s\n", t->data);
    print_tree(t->right);
}
int main(){
    Node* a = NULL;
    FILE *in = fopen("input.txt", "r");
    freopen("output.txt", "w", stdout);
    char word[20];
    while (fscanf(in, "%s", word) == 1){
        insert(&a, word);
    }
    print_tree(a);
    return 0;
}

1 Ответ

1 голос
/ 26 мая 2019

В main ваш код вставляет word, который является локальной переменной стека.Следовательно, data член каждого узла указывает на один и тот же адрес.После вставки адреса памяти word в дерево вы перезаписываете word следующей строкой вашего файла.Опять же, конечный эффект состоит в том, что член data любого узла указывает на одну и ту же строку - последнюю прочитанную строку.

Вам необходимо сделать копию строки перед ее вставкой в ​​дерево.Измените вашу функцию getFreeNode следующим образом: 

Node* getFreeNode(char *value) {
    Node* tmp = (Node*)malloc(sizeof(Node));
    tmp->left = tmp->right = NULL;
    // tmp->data = value;
    tmp->data = strdup(value); // make a copy of the string for the new node
    return tmp;
}

strdup делает копию строки.Вы можете использовать его, добавив #include <strings.h> вверху вашего исходного файла.В противном случае он идентичен следующему: 

tmp->data = malloc(strlen(value) + 1);
strcpy(tmp->data, value);

Как видно из раздела комментариев исходного вопроса, это может быть не единственной вашей ошибкой.

...