c - 修复c中的树结构

Question

我在c(四叉树)中有一个树结构，我想清理它以避免长 Twig 。这是一个例子:

而不是这种树结构，

我想清理树以获得此结构(相同的信息，更少的内存消耗，更快的树遍历)。

这里红色节点是树的根。蓝色节点是空节点，黑色节点是携带信息的树节点。

我的树在 c 中具有以下结构:

typedef enum{particle, pseudo_particle} node_type;

typedef struct{
    double m;
    double x[DIM];
    int to_delete;
} Particle;

typedef struct{
    double x_min[DIM];
    double x_max[DIM];
} tree_box;

typedef struct tree_node{
    Particle p;
    tree_box box;
    node_type node;
    struct tree_node *child[4];
} tree_node;

清理树的函数

void clean_tree(tree_node *t){
    if(t != NULL){
        for(int i=0; i<4; i++){
            clean_tree(t->child[i]);
        }
        // Operation on *t
        if(t->node != particle){
            int child_counter = 0;
            int d = 0;
            for(int i=0; i<4; i++) {
                if(t->child[i] != NULL) {
                    if(t->child[i]->p.to_delete == TRUE){
                        free(t->child[i]);
                        t->child[i] = NULL;
                    }
                    else {
                        child_counter++;
                        d=i;
                    }
                }
            }

            if(child_counter == 0) {
                t->p.to_delete = TRUE;
            }else if (child_counter == 1) {
                t = t->child[d];
                free(t->child[d]);
                t->child[d] = NULL;
            }
        }
        // End of operation on *t
    }
}

但问题是:调用 clean_tree() 后，我的树结构不再存在。整棵树都会被删除。但为什么？有人看到我的错误吗？

Answer 1

我验证了您的代码。

你正在做的是，你正在遍历树，当你发现三个节点的所有子节点都为空时，你将其设置为删除，或者你正在删除所有子节点都为空的父节点或删除。直到我明白你做对了。但是，当只有一个子节点存在且其余为空或已删除时，您将删除具有相同索引的子节点，这对我来说是无法理解的。

     if(child_counter == 0) {   
            t->p.to_delete = TRUE;// Here you are setting the parent node to be deleted while you found that all the child nodes are null or you deleted them in the above
            //but instead of this you should delete the node here itself like  free(t); and you don’t need to call the method `clear_tree` again
        }else if (child_counter == 1) {
            t = t->child[d];     //as t is a local pointer to the current function(recursive) function. Once it return to its previous call the t in that function is holding the address of different node
            free(t->child[d]); //why are you deleting this node? By doing it you are deleting the whole tree
           //this child node might have a branches in it. Instead of deleting it you should store its address in parents node’s child node list or if this is the only node of the tree just leave it
            t->child[d] = NULL;
        }

您的问题正是在上面的代码中。只需关注我的评论，它可能会帮助您解决问题。