Как освободить выделенную память в двоичном дереве в C

Question

У меня возникла проблема с функцией в моей программе на C. Цель программы заключается в следующем:

• Читать целые числа от двоичного файла в массив
• Сортировать эти числа, используя бинарное дерево
• сделать некоторые другие вещи
• Free всей память, что вы выделенной с помощью таНос();

У меня все работает, за исключением возможности освободить мое двоичное дерево. Вот мои структуры для дерева и узла (лист a.k.a.).

typedef struct Node *NodeP; 
typedef struct Tree *TreeP; 

// Definition of a tree 
    struct Tree 
    { 
     NodeP root; 
    }Tree; 

    // Definition of a node 
    struct Node 
    { 
     int data; 
     NodeP L, R; 
    }Node; 

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

/* 
* Frees the memory allocated for 
* each node 
*/ 
void freeNode(NodeP p) 
{ 
    if(p == NULL) return; 
    freeNode(p->L); 
    freeNode(p->R); 
    free(p); 
} 

/* 
* Frees the memory allocated 
* for the tree 
*/ 
TreeP freeTree(TreeP tree) 
{ 
    if(tree->root == NULL) 
     free(tree); 
    else 
    { 
     freeNode(tree->root); 
     free(tree); 
    } 

    return NULL; 
} 

Когда я запускаю эту программу, мой отладчик дает мне эту ошибку.

EXC_BAD_ACCESS (code=EXC_I386_GPFLT) 

Я попытался мысленно проходя каждую итерацию рекурсии, и я не могу найти, почему это дает мне ошибку. Я думаю, что он падает с края дерева в крайних случаях? Я не уверен. Любая помощь очень ценится!

EDIT:

Вот ссылка на скачивание полной программе. Я включил README и двоичные файлы, с которыми я работаю. Один имеет длину всего 10 целых чисел, а другой - 20000. Спасибо за вашу помощь!

https://copy.com/902v0bMv8DtIMUrc

Answer 1

Существует путаница здесь:

// Definition of a tree 
struct Tree 
{ 
    NodeP root; 
}Tree; 

// Definition of a node 
struct Node 
{ 
    int data; 
    NodeP L, R; 
}Node; 

Определение выше определяет переменные, а не тип!

Существует ошибка здесь:

TreeP newTree() 
{ 
    TreeP tree = (TreeP) malloc(sizeof(TreeP)); 
    tree->root = NULL; 
    return tree; 
} 

Он должен прочитать TreeP tree = malloc(sizeof(struct Tree));. Хороший пример того, почему это плохая идея для указателей структуры typedef. Поскольку Tree содержит только один указатель, это не вызывает никаких проблем, но оно должно быть исправлено.

Вот ошибка:

/* 
* Creates a new node in the tree 
*/ 
void insertTreeNode(TreeP tree, int data) 
{ 
    NodeP p = tree->root; 
    Boolean b = FALSE; 

    /* Creates a node and tests for errors */ 
    NodeP node = (NodeP) malloc(sizeof(Node)); 
    if(node == NULL) 
     fprintf(stderr, "Memory allocation failed! \n"); 
    else 
    { 
     node->data = data; 
     node->L = NULL; 
     node->R = NULL; 

     /* Inserts in empty tree case */ 
     if(tree->root == NULL) 
      tree->root = node; 
     else 
     { 
      /* Inserts in any other case */ 
      while(p != NULL && b != TRUE) 
      { 
       if(node->data >= p->data) 
       { 
        if(p->R == NULL) 
        { 
         p->R = node; 
         b = TRUE; 
        } 
        else p = p->R; 
       } 
       if(node->data <= p->data) // replace this line with else 
       { 
        if(p->L == NULL) 
        { 
         p->L = node; 
         b = TRUE; 
        } 
        else p = p->L; 
       } 
      } 
     } 
    } 
} 

Вы должны связать новый узел влево или вправо от узла р, но не в обоих поддеревьев, если p->data == data.

Могут быть другие ошибки, но этот укусы!