释放二叉树C的内存

Question

我想从我分配的二叉树中释放内存,这样做最好的遍历是什么？

typedef struct Node{
struct Node * right;
struct Node * left;
void * data;
}Node;


typedef int (*cmp) (void*,void *);


Node* init(void * element){
    Node * newNode=(Node*)malloc(sizeof(Node));
    newNode->data=element;
    newNode->left=NULL;
    newNode->right=NULL;
    return newNode; 
}

void  insert(void * element, Node** root,cmp compareTo){
    if(*root==NULL){
        *root=init(element);
        return;
    }
    if(compareTo(element,(*root)->data)==1)
        insert(element,&((*root)->left),compareTo);
    else
        insert(element,&((*root)->right),compareTo);
}

Answer 1

考虑一下不同的遍历类型的作用,并记住,在你释放内存之后,你不再允许它访问它:

• 预购:在访问任何儿童之前进行的操作
• 有序:在访问左子树之后,在右子树之前执行的操作
• 后序:访问所有子树后执行的操作

鉴于上述陈述,答案应该清楚.

Answer 2

既然它是一棵树,你应该采用递归方法.

deallocate (node):
    //do nothing if passed a non-existent node
    if node is null
        return

    //now onto the recursion
    deallocate(left node)
    deallocate(right node)

    free node

Answer 3

void free_tree(Node * node){
   //post-order like FatalError hinted at
       if (node != NULL) {
        free_tree(node->right);
        free(node->data); //if data was heap allocated, need to free it
        free_tree(node->left);
        free(node);
     }}

检查段错误和内存泄漏的一种很酷的方法是使用

valgrind --leak-check=full ./yourProgram