Ошибка сегментации при реализации двоичного дерева в c

Я новичок в c, но для проекта я реализую двоичное дерево. вот мой код для функций:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct BSTnode{
  int key;
  int subtree_size;
  struct BSTnode* left;
  struct BSTnode* right;
} TreeNode;

TreeNode* newNode(int value){
  TreeNode *node = malloc(sizeof(TreeNode));
  node->key = value;
  node->left = NULL;
  node->right = NULL;
  node->subtree_size = 1;
  return node;
}

TreeNode* insert(TreeNode* root, TreeNode* to_insert){
  if (root == NULL){
    root = newNode(to_insert->key);
  }
  else if (to_insert->key> root->key){
    if (root->right == NULL){
      root->right = to_insert;
      return root;
    }
    else{
      root->right = insert(root->right, to_insert);
    }
  }
  else if (to_insert->key< root->key){
    if (root->left == NULL){
      root->left = to_insert;
      return root;
    }
    root->left = insert(root->left, to_insert);

  }

  root->subtree_size = 1 + (root->left? root->left->subtree_size: 0) + (root->right? root->right->subtree_size: 0);
  return root;
}

int find(TreeNode* root, int value){
  if (root == NULL || root->key == value){
    return root->key;
  }
  else if (value > root->key){
    return find(root->right, value);
  }
  else{
    return find(root->left, value);
  }
}

В моей основной функции я читаю файл, содержащий число в каждой строке, которое мне нужно вставить в BST. Каждая строка начинается с буквы, за которой следует число, разделенное пробелом.

int main (int argc, char* argv[]){
  FILE* input;

  input = fopen(argv[1], "r");

  char oper;
  int num;

  TreeNode* root = NULL;
  
  while(fscanf(input, "%c", &oper) != EOF){
    if (oper == 'i'){
      fscanf(input, " %d\n", &num);
      TreeNode* to_insert = newNode(num);
      insert(root, to_insert);
      //printf("operation: %c, num: %d\n", oper, num);
    }
    if (oper == 'r'){
//do some other thing
    }
  }
  if (root == NULL){
    printf("yes\n");
  }
  printf("size: %d\n", root->subtree_size);
  printf("left size: %d\n", root->left->subtree_size);
  printf("right size: %d\n", root->right->subtree_size);
  fclose(input);
}

Запуск кода печатает «да», а затем выдает ошибку сегмента. Я видел еще одно сообщение о подобной проблеме, и решение состояло в том, чтобы изменить функцию вставки, чтобы она принимала двойной указатель для root. Здесь это работает? Да, как бы это выглядело? Я не очень хорошо разбираюсь в двойных указателях.

Редактировать 1: предположим, что fscanf() и входной файл правильно используются и открываются.

Edit2: входной файл будет выглядеть так:

i 10
i 20
i 30
i 40
i 50
i 60
i 70
i 80
i 90
i 99
i 15
i 14
i 12
i 25
i 28
i 95
i 35
i 38
i 11
i 23
i 22

Во-первых, поскольку вы не проверяете возвращаемое значение ваших вызовов fscanf(), вы понятия не имеете, прочитали ли вы то, что, по вашему мнению, прочитали. На самом деле, вы даже не знаете, успешно ли вы открыли input. И если root равно NULL, следующие printf() следуют за указателем NULL, что является неопределенным поведением. Либо используйте отладчик, чтобы выяснить, что происходит (рекомендуется), либо добавьте больше сообщений о состоянии к операциям чтения/построения дерева, чтобы вы видели, что происходит, а не только конечный результат.

DevSolar 20.05.2024 02:26

@DevSolar fscanf() и входной файл открываются правильно. надо было упомянуть об этом в посте

The-coder-E 20.05.2024 02:31

@DevSolar Я добавил пример того, как будет выглядеть входной файл.

The-coder-E 20.05.2024 02:39

«При запуске кода выводится «да», а затем выдается ошибка сегмента». if (root == NULL){ printf("yes\n"); } printf("size: %d\n", root->subtree_size); Если root имеет значение NULL, вы не должны удалять его ссылку. Сегфолт является разумным потенциальным последствием этого.

Avi Berger 20.05.2024 02:41
Стоит ли изучать PHP в 2026-2027 годах?
Стоит ли изучать PHP в 2026-2027 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
4
64
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Твоя проблема:

Ваша функция insert() возвращает root. Но вы никогда ничему не присваиваете возвращаемое значение, по крайней мере, в своем main():

TreeNode* root = NULL;

while(fscanf(input, "%c", &oper) != EOF){
  // ...
  insert(root, to_insert);

Ваш root всегда остаётся NULL.

Как я узнал:

gcc -Wall -Wextra -g testme.c -o testme
gdb -tui --args ./testme input.txt
break main
run

Затем «n» означает «следующий» (шаг вперед) и «s» означает «шаг» (вход). Либо научитесь использовать GDB, либо ознакомьтесь с другим отладчиком по вашему выбору. Заниматься разработкой программного обеспечения без отладчика сложно. Не пытайтесь это сделать.

Мое исправление:

Я ненавижу двойные указатели. К счастью, есть простое решение вашей проблемы. В insert() для первого полученного узла не делайте newNode(), просто возьмите тот узел, который вам дали:

if (root == NULL){
  root = to_insert;
}

И в main() присвойте возвращаемое значение root:

  TreeNode* to_insert = newNode(num);
  root = insert(root, to_insert);

Еще предстоит сделать:

Обратите внимание, что ваша программа теряет всю выделенную ей память.

Вам необходимо проверить root на NULL перед доступом к root->left и root->right (в случае, если вы не читали какие-либо данные), и вам нужно еще раз проверить любой из них на NULL перед доступом к соответствующим ...->subtree_size (в случае, если вы, как в примере с данными, , вообще не имеют данных ни в одном поддереве).

выполнение root = insert(root, to_insert); позволяет мне напечатать «размер: 17», а затем ошибку сегмента. Знаете, что не так с root->left->subtree_size?

The-coder-E 20.05.2024 02:51

@The-coder-E Ваше начальное значение — 10. Все последующие значения больше 10 и, следовательно, идут справа от root. root->left остаётся NULL, а значит root->left->subtree_size — незаконный доступ. (Вы пробовали использовать отладчик?)

DevSolar 20.05.2024 02:56

Большое спасибо за помощь. Проблемы с памятью я решу позже, а сейчас у меня есть дела поважнее.

The-coder-E 20.05.2024 03:03

Другие вопросы по теме