Donc, avant de lire quelques concepts informatiques de base.

1. Un arbre binaire est une structure allouée dynamiquement (généralement utilisée pour le stockage ordonné).
2. En raison de sa nature, la traversée d'arbres binaires est généralement récursive;
   En effet, la traversée linéaire (via une boucle) n'est pas naturelle lorsqu'il existe deux voies de bouclage.
   • Récursif: cela signifie une fonction qui s'appelle elle-même.
3. Dans les langues anciennes, la gestion de la mémoire nécessite une gestion manuelle de la mémoire.
   • Manuel: signifie que vous devez le faire vous-même.
4. Lorsque vous effectuez une gestion manuelle de la mémoire, vous devez demander au système sous-jacent de libérer chaque membre de l'arborescence.
   • Gratuit: récupérez la mémoire dans le caca mondial afin qu'elle puisse être réutilisée et que vous ne manquiez pas de mémoire.
   • Libération: cela se fait en appelant la fonction free()et en lui passant le pointeur que vous souhaitez récupérer.
   • Pointeur: C'est comme un bâton virtuel. À la fin, c'est la mémoire. Lorsque vous demandez de la mémoire, vous recevez un pointeur (bâton virtuel) qui a de la mémoire. Lorsque vous avez terminé, vous rendez le pointeur (bâton virtuel).

La solution récursive:

freeTree(Node* node)
{
    freeTree(node->left);  
    freeTree(node->right);
    free(node);
}

Le problème est alors que la récursivité signifie que vous appelez à plusieurs reprises la même fonction. Cela augmente la pile. Agrandir la pile utilise plus de mémoire. La raison pour laquelle vous libérez l'arborescence est que vous souhaitez récupérer de la mémoire en utilisant plus de mémoire est contre-productif (même si vous récupérez les deux bits de mémoire).

Enfin la question:

Le problème se concentre donc sur la conversion de la version récursive ci-dessus en une solution linéaire (de sorte que vous n'ayez pas à utiliser de mémoire).

Donnez le type de nœud

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

Écrivez une fonction pour libérer un arbre de ces nœuds.

Restrictions:

• Ne peut pas utiliser la récursivité (pas même indirectement)

• Impossible d'allouer d'espace dynamique pour le suivi.

• Notez qu'il existe une solution O (n)

Gagnant:

1. Meilleure complexité.
2. Tie Break 1: première soumission
3. Tie Break 2: moins de personnages.

Semble très proche de O (n) pour moi:

Cela fait une marche en profondeur sur l'arbre et utilise le ->leftpointeur des nœuds traversés pour garder une trace du parent.

struct Node * node = root;
struct Node * up = NULL;

while (node != NULL) {
    if (node->left != NULL) {
        struct Node * left = node->left;
        node->left = up;
        up = node;
        node = left;
    } else if (node->right != NULL) {
        struct Node * right = node->right;
        node->left = up;
        node->right = NULL;
        up = node;
        node = right;
    } else {
        if (up == NULL) {
            free(node);
            node = NULL;
        }
        while (up != NULL) {
            free(node);
            if (up->right != NULL) {
                node = up->right;
                up->right = NULL;
                break;
            } else {
                node = up;
                up = up->left;
            }
        }
    }
}

C99, 94, O (n)

Edit: tout le monde semble se référer à struct Nodetout comme Nodecomme si l' typedefÉd, donc je l'ai fait aussi.

c'est en fait mon premier golf C. beaucoup de segfaults.

de toute façon, cela nécessite C99 car il utilise une déclaration à l'intérieur de la première instruction d'une boucle for.

void f(Node*n){for(Node*q;n;n=q)(q=n->left)?n->left=q->right,q->right=n:(q=n->right,free(n));}

n'utilisant même pas #define!

cet algorithme fonctionne en transformant l'arborescence de sorte que le nœud supérieur n'a pas d'enfant gauche, puis en le supprimant et en passant à son enfant droit.

par exemple, si nous commençons par l'arbre

 1
/ \
2 3
 \
 4

l'algorithme mute les pointeurs afin que l'arbre soit

2
 \
 1
/ \
4 3

nous pouvons maintenant supprimer facilement le nœud le plus haut.

C / C ++ / Objective-C 126 caractères (inclut la nouvelle ligne de fin requise)

#define b(t)(t->left||t->right)
void f(Node*r){while(r&&b(r)){Node**p=&r,*c=b(r);while(c)p=&c,c=b(c);free(*p);*p=0;}free(r);}

Ne fonctionne pas en temps O (n). Mais l'OP ne l'exige pas, voici donc ma solution O (n ² ).

Algorithme: descendez jusqu'à une feuille depuis la racine. Publiez-le. Répétez jusqu'à ce qu'il n'y ait pas de feuilles. Relâchez la racine.

Non golfé:

void freeTree (Node * root) {
    while (root && (root->left || root->right)) {
        Node ** prev = &root;
        Node * curr = root->left || root->right;
        while (curr != 0) {
            prev = &curr;
            curr = curr->left || curr->right;
        }
        free(*prev);
        *prev = 0;
    }
    free(root);
}

c ++ 99 O (n)

Les boucles ici sont parfaites pour enchaîner une liste mais pas pour monter et descendre des hiérarchies. user300 l'a géré (je suis impressionné) mais le code est difficile à lire.

La solution consiste à convertir l'arborescence en liste.
L'astuce consiste à le faire en même temps que vous supprimez les nœuds.

void freeNode(Node* t)
{
    if (t == NULL)
    {   return;
    }

    // Points at the bottom left node.
    // Any right nodes are added to the bottom left as we go down
    // this progressively flattens the tree into a list as we go.    
    Node* bottomLeft    = findBottomLeft(t);


    while(t != NULL)
    {
        // Technically we don't need the if (it works fine without)
        // But it makes the code easier to reason about with it here.
        if (t->right != NULL)
        {
            bottomLeft->left = t->right;
            bottomLeft = findBottomLeft(bottomLeft);
        }
        // Now just free the curent node
        Node*   old = t;
        t = t->left;
        free(old);
    }
}

Node* findBottomLeft(Node* t)
{
    while(t->left != NULL)
    {
        t = t->left;
    }
    return t;
}

Version Golf

void f(Node*t){Node*o,*l=t;for(;t;free(o)){for(;l->left;l=l->left);l->left=t->right;o=t;t=t->left;}}

Golf élargi

void f(Node* t)
{
        Node*o,*l    = t;

        for(;t;free(o))
        {
            for(;l->left;l = l->left);
            l->left = t->right;
            o = t;
            t = t->left;
        }
}

C, 150 octets

f(T*r,int s){T*t[s];t[0]=r;T**f=&t[0],**e=&t[0];while(f<=e){if(*f){if((*f)->left){*++e=(*f)->left;}if((*f)->right){*++e=(*f)->right;}}free(*f);f++;}}

Essayez-le sur JDoodle