Подсчёт элементов в бинарном дереве поиска

@EskoS · Регистрация: 14.01.2020

Author24 — интернет-сервис помощи студентам

Требуется подсчитать количество элементов. Словарь из 200000 слов, но выдаёт 197345.

Создаю бинарное дерево

C

FILE *data_average;
    data_average = fopen("list.txt", "r");
 
    char *words = malloc(200000 * 30);
    for (int i = 0; i < 200000; i++) {
        fscanf(data_average, "%s", words + 30*i);
    }
    fclose(data_average);
    int k = 0;
 
    bstree *tree_av = bstree_create(words, 0);
    for (int i = 2; i < 200000; i++) {
        bstree_add(tree_av, words + 30*(i - 1), i - 1);
    }
    count(tree_av, &k);
    printf("%d\n", k);

Обхожу его

C

void count(bstree *tree, int *k)
{
    if (tree != NULL) {
        count(tree->left, k);
        (*k)++;
        count(tree->right, k);
    }
}

@Catstail · 08.04.2022, 10:25

Реализации нет, данных нет. Ты думаешь, кто-то откликнется?

@FasterHarder · 08.04.2022, 14:38

о возможных проблемах:
1. точно в функции вставки ДУБЛИКАТЫ вставляются
2. зачем тебе вспомогательный буфер words, когда слова можно СРАЗУ грузить в дерево при считывании: слово считал - добавил в дерево -> no problems...
3. кол-во маг.чисел зашкаливает...

касательно получения кол-ва узлов (повезло тебе, что все узлы надо посчитать, а, например, не только листья или неполные, или полные узлы)

я б написал так:

C

size_t Get_count_nodes( const bstree* const tree)
{
     if( tree == NULL )
            return 0;
     return ( Get_count_nodes( tree -> left) + Get_count_nodes( tree -> right) + 1 );
}

наверное, сработало бы...

Сообщение от Catstail

Реализации нет, данных нет. Ты думаешь, кто-то откликнется?

деревья интересная тема

@Catstail Модератор 37331 / 20763 / 4275 Регистрация: 12.02.2012 Сообщений: 34,168 Записей в блоге: 14
	08.04.2022, 10:25	2
	Реализации нет, данных нет. Ты думаешь, кто-то откликнется? 0

	08.04.2022, 14:38