Loop insert binary tree

Question

Я пытаюсь понять, как вставить большое количество чисел в двоичное дерево. Программа начинается с запроса номера и вставляет 0 в любой номер, введенный пользователем. Моя программа работает, но она начинает крушить около 40 000, где я получаю ошибку: Возвращенный процесс -1073741571 (0XC00000FD)

Я новичок в управлении C и памятью, но я считаю, что проблема там. любой совет?

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

typedef struct node BSTREE; 

struct node 
{ 
    int data; 
    struct node * left; 
    struct node * right; 
}; 

void insert(BSTREE ** root, int number); 

int main() 
{ 

    BSTREE *root = malloc(sizeof *root); 
    BSTREE *tmp = malloc(sizeof *root); 
    root = NULL; 
    int x; 
    int input; 

    FILE *fp; 
    fp=fopen("c:\\test2.txt", "w"); 


    printf("Please enter a number: "); 
    scanf("%d", &input); 

    for (x = 0; x < input; x++) 
    { 
    insert(&root, x); 
    } 
    printf("%d", x); 
    free(root); 

    fclose(fp); 

    } 

void insert(BSTREE ** root, long int number) 
{ 

    BSTREE *temp = NULL; 
    if(!(*root)) 
    { 
     temp = (BSTREE *)malloc(sizeof(BSTREE)); 
     temp->left = temp->right = NULL; 
     temp->data = number; 
     *root = temp; 
     return; 
    } 

    if(number < (*root)->data) 
    { 
     insert(&(*root)->left, number); 
     free(root); 
    } 
    else if(number > (*root)->data) 
    { 
     insert(&(*root)->right, number); 
     free(root); 
    } 
free(root); 
    } 

Answer 1

Вы звоните free(root) дважды при каждом вызове вставки. Как только сразу после insert возвращается. И тут же на том же узле снова. И вы, кажется, всегда свободны от узла, который вы только что вставили. Следовательно, ваша память, вероятно, повреждена и просто работает на небольших деревьях. По мере увеличения вашего дерева память начинает перераспределяться, и повреждение дерева становится более очевидным.

Предлагаемое более простое решение. Это более подробно, но обрабатывает malloc и освобождается в одной функции, тогда как рекурсивная вставка ядра выполняется в другой. Надеюсь это поможет.

extern int insert_node(BSTREE* root, BSTREE* node); 

void insert(BSTREE** root, int number) 
{ 
    /* allocate a node for our number to be inserted */ 
    BSTREE* node = malloc(sizeof(BSTREE)); 
    node->data = number; 
    node->left = NULL; 
    node->right = NULL; 
    int insert_result; 

    if (*root == NULL) 
    { 
     /* handle the empty tree case */ 
     *root = node; 
     return; 
    } 

    insert_result = insert_node(*root, node); 

    if (!insert_result) 
    { 
     /* insert_node returned false. 
      This means it already had a duplicate of the node 
      in the tree. Just free it since it did not get inserted 
     */ 
     free(node); 
     node = NULL; 
    } 

} 

int insert_node(BSTREE* root, BSTREE* node) 
{ 
    int result = 1; /* success */ 

    if (node->data < root->data) 
    { 
     /* traverse left */ 
     if (node->left != NULL) 
     { 
      result = insert_node(root->left, node); 
     } 
     else 
     { 
      root->left = node; 
     } 
    } 
    else if (node->data > root->data) 
    { 
     /* traverse right */ 
     if (node->right != NULL) 
     { 
      result = insert_node(root->right, node); 
     } 
     else 
     { 
      root->right = node; 
     } 
    } 
    else 
    { 
     /* else node is equal to root - nothing to do */ 
     /* return 0 to indicate the node should be free'd by the caller*/ 
     result = 0; 
    } 

    return result; 
}