Affichage arbre binaire en C

[invite71e1c619]

Bonsoir !
J'ai commencé tout récemment le langage C et donc je me retrouve très souvent face à des petits ennuis.
Je dois construire un arbre binaire et l'afficher en utilisant un parcours préfixe (donc avoir les nombres dans l'ordre croissant)
mais je n'arrive pas à l'afficher malgré toutes les manipulations que j'ai essayé.
N'étant pas encore très au clair avec les pointeurs je suis presque sûre que l'ennui viens de la racine utilisée pour la fonction d'affichage.

Merci d'avance pour votre aide

 Cliquez pour afficher

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


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

Node* create_node (int v)
{
    Node *ptr = NULL;
    ptr = (Node*) malloc(sizeof(Node));
    ptr->right = NULL;
    ptr->left = NULL;
    ptr->value = v;
    return ptr;
}

Node* tree(Node* n, int v)
{
    if (n == NULL)
    {
       n = create_node(v);

    }
    else
    {
        if (n->value < v)
        {
            tree(n->right, v);
        }
        else
        {
            tree(n->left, v);
        }
    }

    return n;
}

void print_tree( Node* n )
{
    if (n != NULL)
    {
        if (n->left != NULL)
            print_tree(n->left);
        printf("%d", n->value);
        if (n->right != NULL)
            print_tree(n->right);
        printf("%d", n->value);
    }
}


int main(int argc, char *argv[])
{
    int v,i;
    srand(time(NULL));

    Node* root = NULL;

    for (i=0; i < 100; i++)
    {
        v = rand()%100;
        root = tree(root, v);
    }

    print_tree(root);//affichage de l'arbre

    return 0;
}

-----

[invite0f0afca1]

 Cliquez pour afficher

Node* tree(Node* n, int v)
{
    if (n == NULL)
    {
       n = create_node(v);

    }
    else
    {
        if (n->value < v)
        {
            tree(n->right, v); // <= Init d'un pointeur a partir de la valeur !! Il faut créer un nouveau node, le lier, et intialiser la valeur de ce node avec "v"
        }
        else
        {
            tree(n->left, v); // Idem au dessus
        }
    }

    return n;
}

int main(int argc, char *argv[])
{
    int v,i;
    srand(time(NULL));

    Node* root = NULL;

    for (i=0; i < 100; i++)
    {
        v = rand()%100;
        root = tree(root, v); // bizarre comme façon de faire. root devrait initialisé une fois pour toute. mais comme la function "tree" renvoie toujours le premier et seul node créé, ça ne change rien
    }


    print_tree(root);//affichage de l'arbre

    return 0;
}

Un seul "node" est créé dans ton arbre, et les liens left/right que tu écrases à chaque appel de "tree" ne sont pas des nodes, mais des int à valeur aléatoires. C'est un des inconvénients de la permissivité du langage C. Un compilateur plus strict aurait signalé cette erreur

[invite71e1c619]

Merci déjà d'avoir répondu !

Il faudrait donc, si j'ai bien compris, créer à chaque fois un nouveau noeud mais je ne vois pas comment le rattacher au précédent.
je serai tentée de mettre par exemple

n->right = create_node(v);

je passe du langage Pascal et j'ai donc sûrement des idées pas compatibles avec le C =/

[invite0f0afca1]

Glurp, j'ai répondu trop vite...

Ce qui n'est pas bon ce sont bien les 2 appels "tree(n->right, v)" et "tree(v->left, v)", mais le problème est différent:

Il faut tester la nullité du pointeur et l'initialiser au besoin "n->left = tree(NULL, v)", respectivement "n->right = tree(NULL, v)". Sinon left et right ne sont jamais initialisés

Il faut revoir aussi "main" pour correctement initialiser l'arbre. En passant toujours "root" en argument, ça ne peut pas marcher.

[A voir en vidéo sur Futura]

[invite0f0afca1]

Je suis un peu rouillé en C..... Voilà une fonction treesinsert qui n'utilise pas la récursivité, qui prend root comme argument d'entrée (à initialiser séparemment), et qui insère la valeur à la bonne place dans l'arbre. J'ai pas testé, mais c'est l'idée

Node* treeInsert(Node* node, int v)
{
 Node* p;

 do
 {
  p = node;
  if (v < p->v)
  {
   node = node->left;
  }
  else
  {
   node = node->right;
  }
 } while (node != null);

 node = create_node(v);
 
 if (v < p->v)
 {
  p->left = node;
 }
 else
 {
  p->right = node;
 }

 return node;
}

[invite7a96054d]

Bonsoir,

Le problème vient de ta fonction tree. Comme tu l'as construite tu dois toujours utiliser sa valeur de retour car les paramètres ne sont pas modifiés, en autre quand tu crées un fils :

Node* tree(Node* n, int v)
{
    if (n == NULL)
    {
       n = create_node(v);

    }
    else
    {
        if (n->value < v)
        {
            n->right = tree(n->right, v);
        }
        else
        {
            n->left = tree(n->left, v);
        }
    }

    return n;
}

Ensuite si tu désires effectuer un parcours préfixe d'un arbre binaire, tu commences par afficher le nœud courant puis tu affiches le fils gauche, puis le droit :

void print_tree( Node* n )
{
    if (n != NULL)
    {
        printf("%d", n->value);
        if (n->left != NULL)
            print_tree(n->left);
        /* printf("%d", n->value); */
        if (n->right != NULL)
            print_tree(n->right);
        /* printf("%d", n->value); */
    }
}

Mais cela ne va te donner les nombres par ordre croissant, pour faire cela il faut d'abord afficher ce qui est plus petit, puis le nœud courant puis ce qui est plus grand : un parcours infixe. Je te laisse écrire le code correspondant

Pour un premier jet c'est pas mal
Il faudra néanmoins penser (ce sont de bonnes pratiques) à :

* tester la valeur de retour du malloc pour gérer les erreurs d'allocations (important)
* ne pas caster le retour du malloc (les avis divergent).
* ajouter des espaces quand tu affiches ton arbre (plus lisible)

[invite71e1c619]

Merci à tous !

J'ai essayé de regrouper vos conseils et le tout marche enfin

Voila mon code si jamais

 Cliquez pour afficher

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


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


Node* create_node (int v)
{
    Node *ptr = NULL;
    ptr = (Node*) malloc(sizeof(Node));
    if (ptr==NULL)
        exit(EXIT_FAILURE);

    ptr->right = NULL;
    ptr->left = NULL;
    ptr->value = v;

    return ptr;
}


Node* tree(Node* n, int v)
{
    if (n == NULL)
    {
       n = create_node(v);

    }
    else
    {
        if (n->value < v)
        {
            if (n->right == NULL)
            {
                n->right = create_node(v);
            }
            else
            {
                tree(n->right,v);
            }
        }
        else
        {
            if (n->left == NULL)
            {
                n->left = create_node(v);
            }
            else
            {
                tree(n->left,v);
            }
        }
    }
    return n;
}


void print_tree( Node* n )
{
    if (n != NULL)
    {
        if (n->left != NULL)
            print_tree(n->left);
        printf("%d\n", n->value);
        if (n->right != NULL)
            print_tree(n->right);
    }
}


int main(int argc, char *argv[])
{
    int v,i;
    srand(time(NULL));

    Node* root = NULL;

    v = rand()%100;
    root = tree(root, v);

    for (i=0; i < 100; i++)
    {
        v = rand()%100;
        tree(root, v);
    }

    print_tree(root);

    return 0;
}

[invite7a96054d]

Juste en passant, dans le morceau :

Node* tree(Node* n, int v)
{
    if (n == NULL)
    {
       n = create_node(v);

    }
    else
    {
        if (n->value < v)
        {
            if (n->right == NULL)
            {
                n->right = create_node(v);
            }
            else
            {
                tree(n->right,v);
            }
        }
        else
        {
            if (n->left == NULL)
            {
                n->left = create_node(v);
            }
            else
            {
                tree(n->left,v);
            }
        }
    }
    return n;
}

Il est inutile de vérifier si le fils gauche ou le fils droit est NULL, car si c'est le cas un appel récusif fait le boulot, ici tu dupliques du code inutilement.
La version courte est simplement celle que j'ai postée un peu plus haut :

Node* tree(Node* n, int v)
{
    if (n == NULL)
       n = create_node(v);
    else if (n->value < v)
       n->right = tree(n->right,v);
    else
       n->left = tree(n->left,v);
    return n;
}

C'est plus compact, et avec l'habitude c'est «récursivement» plus parlant (ne traiter les cas particuliers que lorsqu'ils sont particuliers )

En tout cas un beau début avec les arbres binaires de recherche.