释放二叉树C的内存

I would like to free memory from my allocated binary tree what traversal is the best for doing so?

我想从分配的二叉树中释放内存遍历是最好的方法?

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);
}

5 个解决方案

#1

Since it's a tree, you should go with a recursive approach.

因为它是树，所以应该使用递归方法。

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

#2

Think about what the different traversal types do, and keep in mind, after you free memory you're not allowed to access it anymore:

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

Preorder: operation performed before visiting any children
预定:在探视任何儿童之前进行的操作
In-order: operation performed after visiting left subtree, before right subtree
顺序:在访问左子树、右子树之前执行的操作
Postorder: operation performed after visiting all subtrees
Postorder:访问所有子树后执行的操作

Given the above statements, the answer should be clear.

鉴于以上的陈述，答案应该是明确的。

#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);
     }}

A cool way to check seg faults and memory leaks is to use

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

valgrind --leak-check=full ./yourProgram

valgrind——检查漏气=饱了。/ yourProgram

#4

Depth first search is best for this

深度优先搜索是最好的

#5

When you say "best" do you mean "correct" (i.e., won't cause chaos by accessing freed memory) or "most efficient" or what?

当你说“最好”的时候，你的意思是“正确的”吗?不会因为访问释放的内存而引起混乱)或“最有效”或什么?

As far as correctness goes: Anything you like, provided you take care not to access data after freeing it. The obvious simplest approach (which I won't state explicitly because this looks kinda like homework :-) but it's what you'd do if you wanted to write as little code as possible [EDITED to add: it's what "cnicutar" posted; I hope it wasn't homework after all!]) works just fine.

至于正确性:你喜欢的任何东西，只要你在释放后不去访问数据。最简单的方法(我不明确说明，因为这看起来有点像家庭作业:-)，但如果你想写尽可能少的代码，你就应该这么做(编辑后添加:这是“cnicutar”发布的内容;我希望这不是家庭作业!

You might get more efficient results (in space or time) by appropriate matching of the order of freeing with the order of allocation, but the details depend on your memory allocator and you probably shouldn't care.

通过适当地匹配释放的顺序和分配的顺序，您可能会得到更有效的结果(在空间或时间上)，但是细节取决于您的内存分配程序，您可能不需要在意。

#1