Discussion :

[imy13]

salut
comment transformer un tableau en un arbre utilisant la recherche dichotomique j'ai implémenté un programme mais il ne calcule pas juste : il manque des elements

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct maillon *arbre; //Déclaration de pointeur sur maillon
struct maillon //Déclaration de maillon
{
       int val;
       arbre g;
       arbre d;
       };
arbre ajout_feuille(arbre A,int e)  //Déclaration de fonction qui ajoute une feuille
{
      arbre p;
      if(A == NULL)
      {
           A = (arbre)malloc(sizeof(struct maillon));//allouer de la mémoire
           if(A == NULL)
           {
                printf("impossible d'allouer");
                }
           else
           {
 
           A->val=e;
           A->g=NULL;
           A->d=NULL;
           }
 
           }
      else
      {
           if(e <= (A->val))
           {
 
                A->g = ajout_feuille(A->g ,e);
                }
           else
           {
               A->d = ajout_feuille(A->d ,e);
               }
      }
      return A;
}
 
void affichpe_arbre(arbre A)//Déclaration de fonction qui affiche un arbre
{
     if(A != NULL)
     {
          printf("\t[%p]\n",A);
          printf("[%p][%d][%p] \n\n",A->g,A->val,A->d);
          affichpe_arbre(A->g);
          affichpe_arbre(A->d);
          }
}
 
arbre convert(int tab[],arbre A,int debut,int fin)
{
    if(debut != (fin/2)+(debut/2) && fin != (fin/2)+(debut/2) && debut != fin)
    {
        A = ajout_feuille(A,tab[(fin+debut)/2]);
        printf("\t[%d]\n",tab[(fin/2)+(debut/2)-1]);
        printf("\t%d\t%d\t%d\t%d\n",debut,(fin/2)+(debut/2)-1,(fin/2)+(debut/2)+1,fin);
        //system("pause");
        convert(tab,A,debut,((fin+debut)/2)-1);
        convert(tab,A,((fin+debut)/2)+1,fin);
    }
    return A;
}
 
int main (void)
{
     arbre A = NULL; //Déclaration d'un arbre et initialisation a Nil
     int tab[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27};
     A = convert(tab,A,0,26);
    // printf("arbre par infixe:\n\n");
    // affichin_arbre(A);
     printf("arbre par preordre:\n\n");
     affichpe_arbre(A);
 
     system("pause");
             return 0;
}

quelqu'un pourrait me corriger le code ?
Merci

[Neckara]

Bonjour,
Les balises doivent se mettre entre '[', ']' et non entre '<', '>'.

Sinon j'ai regardé les deux premières fonctions, elles semblent êtres justes.
Essaye aussi de voir ce qu'il se passe un utilisant un débogueur et en exécutant pas à pas.

[ternel]

Pour des raisons de sémantiques, je préconise un typedef int valeur_t; et une fonction d'allocation d'arbre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
arbre creer_arbre(valeur_t valeur)
{
	arbre A = malloc(sizeof(struct maillon));//allouer de la mémoire
	if(A == NULL)
	{
		return NULL;
	}
	A->val=valeur;
	A->g=NULL;
	A->d=NULL;
	return A;
}

Cela dis, ca ne résoud pas ton probleme.
a tout hasard, regarde du coté des arbres dits AVL ou rouge et noir.
Tu auras alors besoin de savoir faire une rotation dans un arbre binaire de recherche

[Sve@r]

Pour des raisons de sémantiques, je préconise un typedef int valeur_t;

Bonjour
Pour de mêmes raisons, je préconise

• de ne pas masquer l'étoile (les pros du C lisent mieux un code avec des étoiles où il faut qu'un code où l'étoile est cachée)
• de donner des noms adéquats et plus normalisés aux structures et de définir une vraie structure arbre permettant de manipuler un arbre

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
typedef struct s_feuille {
       int val;
       struct s_feuille *g;
       struct s_feuille *d;
} t_feuille;
 
typedef struct {
       t_feuille *racine;
} t_arbre;

Ca peut paraitre idiot de créer une structure juste pour la racine de l'arbre mais ensuite on peut facilement la compléter d'outils comme la profondeur, un pointeur de lecture etc. Comme je le dis souvent, on peut tenir une chemise par le col mais ça va beaucoup mieux si on la met sur un cintre...

Cela dis, ca ne résoud pas ton probleme.

Moi non plus mais ça permet ensuite de poser des fonctions bien propres et bien solides et soit le bug disparait parce que les nouvelles fonctions sont mieux écrites, soit il ressort plus facilement...

[ternel]

On en revient à Boileau et son "Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire viennent facilement."

Si le code est sémantiquement limpide, les bugs deviennent apparents.

[diogene]

Le test dans convert() if(debut != (fin/2)+(debut/2) && fin != (fin/2)+(debut/2) && debut != fin) est faux.
Exemple :
Tu arrive dans convert() avec debut = 0 et fin = 26 (0,26)
Tu le rappelles avec convert(tab,A,debut,((fin+debut)/2)-1); pour (0,12) puis (0,5) puis (0,1).
A ce stade, debut != (fin/2)+(debut/2) est faux et on sort immédiatement de la fonction sans avoir traité le segment (0,1)

Essaye avec le test if(debut <= fin)....

[Médinoc]

Ce que tu veux, c'est convertir ce tableau déjà trié en arbre binaire de recherche correctement équilibré, c'est ça?

Franchement, j'ai l'impression que c'est plus simple si on se base sur un couple {offset début, longueur} plutôt qu'un couple {offset début, offset fin}.

Et je plussoie Sve@r, pour la création d'une structure t_arbre.

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void ajouterTableau(t_arbre* arbre, valeur_t const valeurs[], size_t ixDebut, size_t longueur)
{
	if(longueur < 1)
		return;
	else if(longueur < 2)
	{
		ajouterValeur(arbre, valeurs[ixDebut]);
	}
	else
	{
		size_t longueurGauche = longueur / 2;
		size_t longueurDroite = longueur - longueurGauche;
		size_t ixDebutDroite = ixDebut + longueurGauche;
		/*Ajoute l'élément du milieu*/
		ajouterValeur(arbre, valeurs[ixDebutDroite]);
		ixDebutDroite++;
		longueurDroite--;
		/*Ajoute le sous-arbre gauche*/
		ajouterTableau(arbre, valeurs, ixDebut, longueurGauche);
		/*Ajoute le sous-arbre droit*/
		ajouterTableau(arbre, valeurs, ixDebutDroite, longueurDroite);
	}
}