Bonjour

Voila, j'ai un problème pour afficher une liste doublement chaîné donc le but est de faire de tri numérique dont voici le code 

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

typedef struct node
{
    int info;
    struct node *left;
    struct node *right;
}Noeud;

Noeud *head,*courant;

int push(int);
int InsertRight(Noeud *);
int InsertLeft(Noeud *);

int push(int data)
{
  Noeud *Nn;
  int res = 0;
  Nn =(Noeud *)malloc(1*sizeof(Noeud));
  Nn -> left = Nn -> right = NULL;
  Nn -> info = data;

  if (head == NULL)
  {
      head = Nn;
      return 1;
  }

  res = head -> info;
 if ( res > data )
  {
    if ( head -> left == NULL )
    {
      head -> left = Nn;
      return 1;
    }
    res = InsertLeft(Nn);
  }

  if ( res <  data )
  {
    if ( head -> right == NULL )
    {
      head -> right = Nn;
      return 1;
    }
    res = InsertRight(Nn);
  }
  return 0;
}

int InsertRight(Noeud *fils)
{
Noeud *courant;
  for(courant = head; courant ->right; courant = courant -> right )
    ;
  courant -> right = fils;
  return 1;
}

int InsertLeft(Noeud *fils)
{
Noeud *courant;

  for(courant = head; courant ->left; courant = courant -> left )
    ;

  courant -> left = fils;
  return 1;
}

void Is_Vide()
{
  if ( head == NULL )
  {
    puts("Liste est vide \n");
    exit(0);
  }
}

void print()
{
  Noeud *run  = head;
  Is_Vide();

  if (run != NULL)
  {
    print(run ->left);
    printf("%d \n", run -> info);
    print(run-> right);
  }
}
int main()
{
  head = courant = NULL;
  push(5); push(9); push(3); push(7);
  push(4); push(8); push(2); push(6);
  push(2);
  print();
  puts("\n");
  return 0;
}

Comme vous pouvez le voir,  on place le 5, puis on compare ce dernier et le nouveau arrivé à savoir le 9 et comme le 9 est plus grand, on le branche

sur le right sinon vers left

On tient ainsi l'arbre suivant

                                                                                   5

                                                                    3                         9

                                                             2          4               7         N

                                                      1         N                   6      8

Le 1, 4, 6 et 8 ont leurs pointeurs à NULL .  Le 2  a son left vers 1 mais le right sur Null

Je sais que l'affichage doit se faire en récursive pour avoir en ordre 1,2,3, ....9  mais  Erreur de segmentation (core dumped)

Quelqu'un a une idée SVP

Premièrement, ce n'est pas une liste doublement chaînée mais un arbre binaire de recherche.
Tu définis une fonction print sans paramêtre et tu l'appelles récursivement avec des paramètres.

Tu dois avoir le noeud courant comme paramètre et tu commences dans le main avec la racine.

-
Edité par PierrotLeFou 12 août 2022 à 20:26:54

Revoir aussi ton algo d'insertion : Ce qu'il fait actuellement c'est mettre le premier nœud à la racine puis les plus grands tout à gauche et les plus petits tout à droite. Ce qui fait comme si tu avait deux listes qui partent de la racine.

De plus ligne 39 tu affectes la valeur 1 à res (C'est ce que retourne InsertLeft). Ça risque de fausser le test suivant ligne 42.

Tu n'as pas besoin de deux foncions d'insertion et ta fonction d'insertion sera récursive.

Écris-toi une fonction qui génère un noeud et qui retourne son adresse. Tu vas simplifier un peu ton code.

Profites-en pour vérifier si le malloc a bien fonctionné.

Tu devrais pouvoir définir ta variable head dans le main. Évites les variables globales.

-
Edité par PierrotLeFou 13 août 2022 à 2:08:37

Merci pour ton aide.

à vrai dire, j'ai tout vérifié mais rien à faire, alors google est ton ami. Le voila un code qui veut la peine d’être vu .

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

typedef struct node { int value; struct node *left, *right; }Noeud;
Noeud *head = NULL;

Noeud *AlocNode(int value)
{
  Noeud *tmp = (Noeud *)malloc(sizeof(Noeud));
  tmp -> value = value;
  tmp -> left = tmp -> right = NULL;
  return tmp;
}

void PrintUp(Noeud *root)
{
  if (root != NULL)
  {
    PrintUp(root -> right);
    printf("%d ", root -> value);
    PrintUp(root -> left);
  }
}

void PrintDown(Noeud *root)
{
  if (root != NULL)
  {
    PrintDown(root -> left);
    printf("%d ", root -> value);
    PrintDown(root -> right);
  }
}

int FindElement(Noeud *root, int nb)
{
  if (root != NULL)
  {
    if (root -> value  == nb)
    {
      printf("%d  exist", root -> value);
      return 1;
    }
    FindElement(root -> right, nb);
    FindElement(root -> left, nb);
  }
}
Noeud* Push(Noeud* node, int value) // inserting nodes!
{
  if (node == NULL) 
    return AlocNode(value);

  if (value < node -> value)
  {
    node -> left = Push(node -> left, value);
    return node;
  }
  if (value > node -> value)
  {
    node -> right = Push(node -> right, value);
    return node;
  }
}
int main()
{
  head = Push(head, 5);
  Push(head, 9); Push(head, 3); Push(head, 7); Push(head, 4); Push(head, 8);
  Push(head, 2); Push(head, 6); Push(head, 1);

  PrintUp(head); puts("\n");
  PrintDown(head); puts("\n");
  FindElement(head, 5); puts("\n");
  return 0;
}

Merci encore

Et moi, je ne suis pas ton ami?

J'ai modifié mon code pour afficher dans les deux directions avec la même fonction.

J'ai ajouté une fonction find qui est aussi récursive.

Ce qui est intéressant avec les arbres binaires est qu'on peut presque tout faire de façon récursive.
-

#include <stdio.h>
#include<stdlib.h>
#include <time.h>
 
typedef struct Node Node;
struct Node {
    int value;
    union {
        Node *ways[2];
        struct {
            Node *left;
            Node *right;
        };
    };
};
 
void *allocate(size_t size) {
    void *area = malloc(size);
    if(area) return area;
    perror("malloc");
    fprintf(stderr, "Required: %d\n", size);
    exit(EXIT_FAILURE);
}
 
Node *create(int value) {
    Node *node = allocate(sizeof(Node));
    node->value = value;
    node->left = node->right = NULL;
    return node;
}
 
void insert(Node *node, int value) {
    //if(node->value == value) return;
    if(node->value > value)
        if(node->left) insert(node->left, value); else node->left = create(value);
    else
        if(node->right) insert(node->right, value); else node->right = create(value);
}
 
void display(Node *node, int up) {
    if(node) {
        up = (up) ? 1 : 0;
        display(node->ways[up], up);
        printf("%d ", node->value);
        display(node->ways[1-up], up);
    }
}
 
int find(Node *node, int value) {
    if(node == NULL) return 0;
    if(node->value == value) return 1;
    return (node->value > value) ? find(node->left, value) : find(node->right, value);
}
  
int main(void) {
    Node *head = NULL;
    srand(time(NULL));
    for(int i=0; i<10; i++) {
        int value = rand() % 100;
        if(head)insert(head, value); else head = create(value);
    }
    display(head, 0);
    printf("\n");
    display(head, 1);
    printf("\n");
    for(int i=0; i < 100; i++)
        if(find(head, i))
            printf("%d ", i);
    printf("\n");
    return 0;
}

-
Edité par PierrotLeFou 14 août 2022 à 17:55:36

Si si avec ton Way, tu es même mon copain  maintenant à  condition que tu fasse mieux, si si tu peux le faire .  Voila un peu d'explication.

On sait que la liste contient des Noeud avec deux pointer next et back, ou right ou left. 

Si tu prends un autre Struct disons Info

typedef struct node
{
    int info;
    struct node *next;
    struct node *back;
}Noeud;

typedef struct nodeinfo
{
    int tri; /* 0 defaut  1 incr 2 desc */
    int total; /* nombre maillon */
    Noeud * head, *fin;
}NoeudInfo;

NoeudInfo Info;

NoeudInfo *root = NULL;

Hello,

Tu devrais décider si tes variables ont un nom français ou anglais. next, back, fin, Noeud, NoeudInfo, tri, cela fait brouillon. Choisis-toi un langage, et n'emploie que celui-là.

Pourquoi la variable tri dans struct nodeinfo ? Tu as une liste doublement chaînée: si tu la parcours de head vers fin, tu as l'ordre croissant, de fin vers head l'ordre décroissant.

Edit: le contraire de next c'est previous (celui de back c'est forward) 

-
Edité par edgarjacobs 15 août 2022 à 0:11:26

Vrai pour le choix de langue mais bon, il se trouve que la copie/coller n'a pas encore l’intelligence de faire la traduction

L’intérêt de NoeudInfo est justement entre autre de ne pas parcourir la liste pour connaitre les nombre des éléments puisqu'il ne te coûte qu'une addition

à chaque insertion ou son contraire. De même, avec le flag tri, tu as pas besoin de relancer la fonction si la liste est déjà dans ce mode 

Bon, l'heure de dodo, je vais mettre un peu de l'ordre dans tout ça  avant de te le partager en Chinois 

Yaroo a écrit:

L’intérêt de NoeudInfo est justement entre autre de ne pas parcourir la liste pour connaitre les nombre des éléments puisqu'il ne te coûte qu'une addition à chaque insertion ou son contraire.

Je n'ai pas parlé de la variable total, mais pour moi la variable tri n'est pas nécessaire.

Bonne nuit avec les chinois 

Remarques que la structure ne fait pas tout.
J'ai utilisé ma structure ici pour un arbre binaire. Je l'ai déjà utilisé pour une liste doublement chaînée.
C'est plus qu'une simple question de noms de variables. J'avais appelé le tableau "ways" du nom "links".

Pour être efficace, un arbre binaire de recherche (ABR) doit être balancé.

C'est-à-dire que la différence de profondeur de tous les sous-arbres doit être au plus de 1.

Ton champs  tri  pourrait servir pour les arbres bicolores:

https://fr.wikipedia.org/wiki/Arbre_bicolore

Il y a d'autres méthodes.

https://fr.wikipedia.org/wiki/Arbre_binaire_de_recherche

Ce lien en cite quelques unes.

-
Edité par PierrotLeFou 15 août 2022 à 1:27:33

Balanced tree => arbre équilibré en français.

Le recherche dans les arbres binaires est également efficace dans les arbres quasi-équilibrés, où les hauteurs des sous-arbres gauche et droite d'un noeud sont presque de la même longueur (à un facteur constant près, pas forcément 1). Et le quasi-équilibre est moins coûteux à maintenir dans les ajouts et supressions.

-
Edité par michelbillaud 15 août 2022 à 9:15:54

Je ne suis pas le seul à faire des erreurs de français:

https://fr.wikipedia.org/wiki/Arbre_splay

«arbre binaire recherche auto-balancé»

-
Edité par michelbillaud 16 août 2022 à 7:21:54

Rebonjour mes nouveaux copains  

Et oui, google n'est plus mon ami sur  un simple problème de makefile.

Oser demander pourquoi et vous allez le payer de votre temps

Merci