如何释放C中二叉树中分配的内存

Question

我在使用 C 程序中的函数时遇到问题。该计划的目的是：

将二进制文件中的整数读入数组
使用二叉树对这些数字进行排序
做一些其他的事情
释放您使用 malloc() 分配的所有内存；

除了能够释放我的二叉树之外，我已经完成了所有工作。这是我的树和节点结构 (a.k.a.leaf).

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)

我已经尝试在脑海中遍历递归的每次迭代，但我找不到为什么它会给我一个错误。我在想它在边缘情况下从树的边缘掉下来了吗？我不确定。非常感谢任何帮助！

编辑：

这里是link完整程序的下载地址。我包含了一个自述文件和我正在使用的二进制文件。一个长度只有 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.

，则必须 link 节点 p 左侧或右侧的新节点但不能在两个子树中

可能还有其他错误，但这一个很重要！

如何释放C中二叉树中分配的内存

How to free allocated memory in a binary tree in C

c

malloc

free

tree

binary-tree