probléme avec arbre binaire

**lanageuse56** · 12/05/2007, 19h43

Bonjour,

J'ai un problème avec les arbres binaires je n'arrive pas a monter dans mon arbre(enfin je pense)car je met des valeurs dans mon arbre et lorsque j'affiche mes valeurs il me donne toujours la dernière valeur.

Merci beaucoup pour votre aide.

**Trap D** · 12/05/2007, 23h09

Désloé, je l'ai égarée.

**LinuxUser** · 13/05/2007, 10h47

Bonjour,

tout d'abord, il suffit d'avoir une structure adequate, je me permets de t'en proposer une:

Code :

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

1
2
3
4
5
6
7
8
 
 
typedef struct sarbre
{
  int val; //Etiquette du noeud
  struct sarbre *ag; //arbre gauche
  struct sarbre *ad; //arbre droit
}Sarbre, *Arbre;  //Pointeur sur la structure

En suite lorsque tu cherches à descendre, il suffit toujours d'avoir un coup d' avance.
Je m'explique,

admettons que tu es un arbre comme celui ci:

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
 Arbre A:
                               2
                            /     \
                           4       6
                          /  \    /  \
                         2   1  0    8
 
//si tu veux le 4:
  Arbre a;
 
//Admettons que v(Arbre a) soit une fonction qui donne l'étiquette du noeud
  v(a->ag);
 
//Si tu veux le 2 et ben tu fais:
 
  Arbre b=malloc(...);
  b=a->ag;
  v(b->ag);
 
//donc si tu veux monter tu n'a plus qu'à faire
  b;
  v(b);
 
//et si tu veux monter encore
  a;
  v(a);

Le petit truc, c'est qu'il faut toujours que tu conserves une "trace" de ton passage dans l'arbre, donc il faut créer un arbre et stocker dans ce dernier, la position où tu es, puis descendre à partir de ce nouvel arbre.

Puis pour remonter tu n'a plus qu'à te mettre dans cet arbre et le tour est joué.

Je ne sais pas si ce que je dis est clair, mais si tu as des questions n'hésites pas.

**lanageuse56** · 14/05/2007, 16h34

Je ne comprend pas bien lorsque tu met un a et un b. Ca correspond a quoi?

Merci pour ton aide

**lanageuse56** · 14/05/2007, 16h38

Pour faire un affichage ça marche ?

Code :

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

printf("borneinf=%d\n",maBorne.inf);

Et le pointeur sur la structure il sert à quoi?

**Darwiz** · 14/05/2007, 16h54

Le dernier arbre binaire que j'ai fait ressemble à ceci :

Code ArbreBinaire.h :

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
typedef struct TreeDatas
{
	unsigned int Value;
	unsigned int Range;
 
	unsigned int NbIteration;
	unsigned int SleepTime;
} TreeDatas;
 
typedef struct TreeNode
{
	TreeDatas NodeDatas;
	struct TreeNode * NodeL;
	struct TreeNode * NodeR;
} TreeNode;
 
TreeNode* CreateNode(TreeNode * Racine,TreeDatas valeur);
void DeleteNode(TreeNode * NodeToDelete);
 
TreeNode* SearchValue(TreeNode * Racine, unsigned int valeur);
 
void PrintTree(TreeNode * Racine);
void PrintTreeAsc(TreeNode * Racine);
void PrintTreeDec(TreeNode * Racine);

Code ArbreBinaire.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
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include "ArbreBinaire.h"
 
#include <Windows.h>
 
#include <stdio.h>
 
TreeNode * CreateNode(TreeNode * Racine,TreeDatas valeur)
{
	if (Racine!=NULL)
	{
		if (Racine->NodeDatas.Value > valeur.Value)
		{
			Racine->NodeL = CreateNode(Racine->NodeL, valeur);
		}
		else
		{
			Racine->NodeR = CreateNode(Racine->NodeR, valeur);
		}
	}
	else
	{
		Racine=(TreeNode *)malloc(sizeof(TreeNode));
		Racine->NodeDatas = valeur;
		Racine->NodeL = NULL;
		Racine->NodeR = NULL;
	}
	return Racine;
}
 
// Recursive deletion
void DeleteNode(TreeNode * NodeToDelete)
{
	if (NodeToDelete->NodeL)
	{
		DeleteNode(NodeToDelete->NodeL);
	}
 
	if (NodeToDelete->NodeR)
	{
		DeleteNode(NodeToDelete->NodeR);
	}
 
	free(NodeToDelete);
}
 
TreeNode * SearchValue(TreeNode * Racine, unsigned int valeur)
{
	if (Racine!=NULL)
	{
		if (Racine->NodeDatas.Value > valeur)
		{
			Racine = SearchValue(Racine->NodeL, valeur);
		}
		else if (Racine->NodeDatas.Value+Racine->NodeDatas.Range < valeur)
		{
			Racine = SearchValue(Racine->NodeR, valeur);
		}
	}
 
	return Racine;
}
 
void PrintTree(TreeNode * Racine)
{
	if (Racine!=NULL)
	{
		printf("%d",Racine->NodeDatas.Value);
		if (Racine->NodeDatas.Range > 0)
		{
			printf("-%d",Racine->NodeDatas.Range);
		}
		printf("(N:%d/S%d) ", Racine->NodeDatas.NbIteration, Racine->NodeDatas.SleepTime);
 
		PrintTree(Racine->NodeL);
		PrintTree(Racine->NodeR);
	}
}
 
void PrintTreeAsc(TreeNode * Racine)
{
	if (Racine!=NULL)
	{
		PrintTreeAsc(Racine->NodeL);
		printf("%d ",Racine->NodeDatas.Value);
		PrintTreeAsc(Racine->NodeR);
	}
}
 
void PrintTreeDec(TreeNode * Racine)
{
	if (Racine!=NULL)
	{
		PrintTreeDec(Racine->NodeR);
		printf("%d ",Racine->NodeDatas.Value);
		PrintTreeDec(Racine->NodeL);
	}
}

Reste à adapter le TreeDatas au besoin car j'ai pas bien compris le problème d'origine.
Si j'ai bonne mémoire le include Windows sert juste pour avoir NULL ....

**lanageuse56** · 14/05/2007, 17h20

Je ne comprend pas ton arbre j'essaye sur un truc simple en gros le cours faux du prof et je ne peut pas remonter

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
struct Borne {
 
       int valeur;
       int inf;
       int sup;
       };
 
 
struct Noeud {
       Borne b;
       Noeud* ptrSup;
       Noeud* ptrAg;
       Noeud* ptrAd;
       };
 
struct Arbre {
       Noeud* ptrRacine;
       };
 
Noeud* allNvNoeud (Borne b)
{
       Noeud* ptrNoeud;
       ptrNoeud=(Noeud*)malloc(sizeof (Noeud));
       ptrNoeud->b.valeur=b.valeur;
       ptrNoeud->b.inf=b.inf;
       ptrNoeud->b.sup=b.sup;
       ptrNoeud->ptrSup=NULL;
       ptrNoeud->ptrAg=NULL;
       ptrNoeud->ptrAd=NULL;
       return ptrNoeud;
}
 
Noeud* allNvarbre(Borne racine)
{
       Arbre* ptrArbre;
       ptrArbre=(Arbre*)malloc(sizeof(Arbre));
       ptrArbre->ptrRacine=allNvNoeud(racine);
       return ptrArbre-> ptrRacine;
}
 
Noeud* insererAg (Borne b, Noeud* ptrNoeud)
{
       Noeud* ptrNouveaux;
       ptrNouveaux=allNvNoeud(b);
       ptrNoeud->ptrAg=ptrNouveaux;
       ptrNouveaux->ptrSup=ptrNoeud;
       return ptrNouveaux;
}
 
Noeud* insererAd (Borne b, Noeud* ptrNoeud)
{
       Noeud* ptrNouveaux;
       ptrNouveaux=allNvNoeud(b);
       ptrNoeud->ptrAd=ptrNouveaux;
       ptrNouveaux->ptrSup=ptrNoeud;
       return ptrNouveaux;
}
 
Noeud* descAg(Noeud* ptrNoeud)
{
       return ptrNoeud->ptrAg;
}
 
Noeud* descAd(Noeud* ptrNoeud)
{
       return ptrNoeud->ptrAd;
}
 
Noeud* monter(Noeud* ptrNoeud)
{
       return ptrNoeud->ptrSup;
}
 
int estVide (Arbre* ptrArbre)
{
    if(((ptrArbre->ptrRacine->ptrAg)==NULL)&&(ptrArbre->ptrRacine->ptrAd==NULL))
    return 1;
    else
    return 0;
}
 
int estFeuille(Noeud* ptrNoeud)
{
    return ((ptrNoeud->ptrAg==NULL)&&(ptrNoeud->ptrAd==NULL));
}
 
Noeud* affichage (Noeud* ptrNoeud)
{
     if (ptrNoeud!=NULL)
     {
                        affichage(descAg(ptrNoeud));
                        printf("%d",ptrNoeud->b.valeur);
                        affichage (descAd(ptrNoeud));
     }
	 return 0;
}
 
int main()
{
	int choix/*valeur*/;
  Borne maBorne;
  Noeud* ptrNoeud;
  Noeud* ptrArbre;
  printf("Entrez une opération parmi les suivantes:\n");
  printf("0 pour crée la racine\n");
  printf("1 pour insérer un noeud a gauche\n");
  printf("2 pour insérer un noeud a droite\n");
  printf("3 pour monter au noeud superieur\n");
  printf("4 pour descendre a gauche\n");
  printf("5 pour descendre a droite\n");
  printf("6 pour afficher l'ordre\n");
  printf("7 pour sortir\n");
  do
  {
      printf("votre choix\n");
      scanf("%d",& choix);
      switch (choix)
      {
             case 0:
                  printf ("entrer la valeur de la racine\n");
                  scanf ("%d",&maBorne.valeur);
                  printf("entrer la valeur de la borne inf\n");
                  scanf("%d",&maBorne.inf);
                  ptrNoeud=allNvarbre(maBorne);
                  ptrArbre=ptrNoeud;
                  break;
             case 1:
                  printf("entrez la valeur\n");
                  scanf("%d",&maBorne.valeur);
                  printf("entrer la valeur de la borne inf\n");
                  scanf("%d",&maBorne.inf);
                  ptrNoeud=insererAg(maBorne, ptrNoeud);
                  break;
             case 2:
                  printf("entrez la valeur\n");
                  scanf("%d",&maBorne.valeur);
                  printf("entrer la valeur de la borne inf\n");
                  scanf("%d",&maBorne.inf);
                  ptrNoeud=insererAd(maBorne, ptrNoeud);
                  break;
             case 3:
                  ptrNoeud=monter(ptrNoeud);
                  break;
             case 4:
                  ptrNoeud=descAg(ptrNoeud);
                  break;
             case 5:
                  ptrNoeud=descAd(ptrNoeud);
                  break;
             case 6:
                  ptrArbre=affichage(ptrNoeud);
                  break;
             case 7:break;
      }
  }
  while(choix!=7);
  return 0;
}

**Darwiz** · 14/05/2007, 17h52

Ton code est cohérent je modifierais juste ceci :

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
typedef struct Borne
{   
	int valeur; 
	int inf; 
	int sup; 
} Borne; 
 
typedef struct Noeud 
{  
	Borne b; 
	struct Noeud* ptrSup; 
	struct Noeud* ptrAg; 
	struct Noeud* ptrAd; 
} Noeud;
 
typedef struct Arbre
{  
	Noeud* ptrRacine; 
} Arbre;

J'ai testé et il semble que les résultats sont valable pour parcourir l'arbre; même si tu devrais ajouter des contrôles pour pas se retrouver sur un noeud vide.
Retourner à la racine serait pas mal aussi.

Pour tester j'ai créé l'arbre ajouté un noeud à gauche affiché l'arbre, monté au parent et affiché à nouveau l'arbre, ce qui a fonctionné. L'affichage est peut être à revoir.

**lanageuse56** · 14/05/2007, 18h14

Merci pour ton aide mais dans mon programme initial ca ne marche pas et je ne sais pas pourquoi. je vais essayer de mettre mon arbre dans un programme et de voir.

**lanageuse56** · 14/05/2007, 18h24

comment on fait pour retourner à la racine?

**lanageuse56** · 14/05/2007, 18h33

Je pens que ce programme est similaire au précedent mais pourtant il ne fonctionne pas

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
// arbre.cpp*: définit le point d'entrée pour l'application console.
//
 
//#include <stdafx.h>
#include <stdio.h>
#include <stdlib.h>
#include "malloc.h"
 
typedef struct Borne {
 
       int Vd;//ville départ
       int Va;//ville arrivée
	   int inf;
	   int sup;
	  // int matrice[][];
       }Borne;
 
 
typedef struct Noeud {
       Borne b;
       struct Noeud* ptrSup;
       struct Noeud* ptrAg;
       struct Noeud* ptrAd;
       }Noeud;
 
typedef struct Arbre {
       Noeud* ptrRacine;
       }Arbre;
 
Noeud* allNvNoeudga (Borne b)
{
       Noeud* ptrNoeud;
       ptrNoeud=(Noeud*)malloc(sizeof (Noeud));
       ptrNoeud->b.Va=b.Va;
       ptrNoeud->b.Vd=b.Vd;
       ptrNoeud->b.inf=b.inf;
       ptrNoeud->ptrSup=NULL;
       ptrNoeud->ptrAg=NULL;
       ptrNoeud->ptrAd=NULL;
       return ptrNoeud;
}
Noeud* allNvNoeuddr (Borne b)
{
       Noeud* ptrNoeud;
       ptrNoeud=(Noeud*)malloc(sizeof (Noeud));
       ptrNoeud->b.Va=b.Va;
       ptrNoeud->b.Vd=b.Vd;
       ptrNoeud->b.sup=b.sup;
       ptrNoeud->ptrSup=NULL;
       ptrNoeud->ptrAg=NULL;
       ptrNoeud->ptrAd=NULL;
       return ptrNoeud;
}
 
Noeud* allNvarbre(Borne racine)
{
       Arbre* ptrArbre;
       ptrArbre=(Arbre*)malloc(sizeof(Arbre));
       ptrArbre->ptrRacine=allNvNoeudga(racine);
       return ptrArbre-> ptrRacine;
}
 
Noeud* insererAg (Borne b, Noeud* ptrNoeud)
{
       Noeud* ptrNouveaux;
       ptrNouveaux=allNvNoeudga(b);
       ptrNoeud->ptrAg=ptrNouveaux;
       ptrNouveaux->ptrSup=ptrNoeud;
       return ptrNouveaux;
}
 
Noeud* insererAd (Borne b, Noeud* ptrNoeud)
{
       Noeud* ptrNouveaux;
       ptrNouveaux=allNvNoeuddr(b);
       ptrNoeud->ptrAd=ptrNouveaux;
       ptrNouveaux->ptrSup=ptrNoeud;
       return ptrNouveaux;
}
 
Noeud* descAg(Noeud* ptrNoeud)
{
       return ptrNoeud->ptrAg;
}
 
Noeud* descAd(Noeud* ptrNoeud)
{
       return ptrNoeud->ptrAd;
}
Noeud* monter(Noeud* ptrNoeud)
{
       return ptrNoeud->ptrSup;
}
 
int estVide (Arbre* ptrArbre)
{
       if(((ptrArbre->ptrRacine->ptrAg)==NULL)&&(ptrArbre->ptrRacine->ptrAd==NULL))
       return 1;
       else
       return 0;
}
 
int estFeuille(Noeud* ptrNoeud)
{
       return ((ptrNoeud->ptrAg==NULL)&&(ptrNoeud->ptrAd==NULL));
}
 
Noeud* affichage (Noeud* ptrNoeud)
{
       if (ptrNoeud!=NULL)
       {
              affichage(descAg(ptrNoeud));
              //printf("%d",ptrNoeud->b.valeur);
              affichage (descAd(ptrNoeud));
       }
       return 0;
}
 
int main()
{
	int choix/*valeur*/;
	int fin=0;
  Borne maBorne;
  Noeud* ptrNoeud=NULL;
  Noeud* ptrArbre=NULL;
  while(fin!=1)
  {
                  printf ("entrer la ville de départ\n");
                  scanf ("%d",&maBorne.Vd);
                  printf ("entrer la ville d'arriver\n");
                  scanf ("%d",&maBorne.Va);
                  printf("entrer la valeur de la borne inf\n");
                  scanf("%d",&maBorne.inf);
                  printf("entrer la valeur de la borne sup\n");
                  scanf("%d",&maBorne.sup);
                  ptrNoeud=allNvarbre(maBorne);
                  printf("c'est la fin?");
                  scanf("%d",&fin);
  }
  fin=0;
  while(fin!=1)
  {
               ptrNoeud=monter(ptrNoeud);
               printf("borneinf=%d\n",maBorne.inf);
  }
 
 
  return 0;
}

Si on le compile il bug
Pouvez vous me dire ou il y a une erreur
merci

**diogene** · 15/05/2007, 11h06

Quelques remarques et critiques :
- allNvNoeudga

Code :

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

1
2
3
4
5
6
Noeud* allNvNoeudga (Borne b)
{
       Noeud* ptrNoeud;
       ptrNoeud=(Noeud*)malloc(sizeof (Noeud));
       ptrNoeud->b.Va=b.Va;
....

Il faut tester le retour du malloc avant d'utilise ptrNoeud:

Code :

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

1
2
3
4
5
6
7
8
9
10
Noeud* allNvNoeudga (Borne b)
{
       Noeud* ptrNoeud=malloc(sizeof *ptrNoeud);
       if(ptrNoeud != NULL)
       {
         ptrNoeud->b.Va=b.Va;
....
       }
       return ptrNoeud;
}

- idem pour allNvNoeuddr
- duplication de code entre allNvNoeuddr et allNvNoeudga. Par exemple:

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
Noeud* allNvNoeud (Borne b, int gadr)
{
       Noeud* ptrNoeud = malloc(sizeof  *ptrNoeud);
       if(ptrNoeud != NULL)
       {
         ptrNoeud->b.Va=b.Va;
         ptrNoeud->b.Vd=b.Vd;
         ptrNoeud->ptrSup=NULL;
         ptrNoeud->ptrAg=NULL;
         ptrNoeud->ptrAd=NULL;
         if(gadr)
           {
             ptrNoeud->b.inf = b.inf;
             ptrNoeud->b.sup = ?????;
           }
           else
           {
              ptrNoeud->b.inf = ??????;             
              ptrNoeud->b.sup = b.sup;
           }
       }
       return ptrNoeud;
}

- Ta gestion de l'arbre est incorrecte.

Code :

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

1
2
3
4
5
6
7
Noeud* allNvarbre(Borne racine)
{
       Arbre* ptrArbre;
       ptrArbre=(Arbre*)malloc(sizeof(Arbre));
       ptrArbre->ptrRacine=allNvNoeudga(racine);
       return ptrArbre-> ptrRacine;
}

ptrArbre n'est pas sauvegardé en sortie : Il sera impossible de récupérer la mémoire allouée.

Code :

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

1
2
3
4
5
6
Arbre* allNvarbre(Borne racine)
{
       Arbre* ptrArbre=malloc(sizeof *ptrArbre));
       if(ptrArbre != NULL) ptrArbre->ptrRacine=allNvNoeudga(racine);
       return ptrArbre;
}

- insererAg

Code :

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

1
2
3
4
5
6
7
8
Noeud* insererAg (Borne b, Noeud* ptrNoeud)
{
       Noeud* ptrNouveaux;
       ptrNouveaux=allNvNoeudga(b);
       ptrNoeud->ptrAg=ptrNouveaux;
       ptrNouveaux->ptrSup=ptrNoeud;
       return ptrNouveaux;
}

Tester le succès de la création du nouveau noeud

Code :

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

1
2
3
4
5
6
7
8
9
10
Noeud* insererAg (Borne b, Noeud* ptrNoeud)
{
       Noeud* ptrNouveaux = allNvNoeudga(b);
       if(ptrNouveaux != NULL)
       {
         ptrNoeud->ptrAg=ptrNouveaux;
         ptrNouveaux->ptrSup=ptrNoeud;
       }
       return ptrNouveaux;
}

- idem pour insererAd
- idem pour ptrNoeud dans descAg,descAd,monter,estFeuille ou s'assurer que jamais ptrNoeud ne peut être NULL lors de l'appel
- idem pour ptrArbre et ptrArbre->ptrRacine dans estVide
- main : incohérent pour tester ce qui précéde
* ptrArbre ne sert à rien
* ptrNoeud est écrasé par chaque nouvelle entrée. Le nouveau noeud placé a ptrSup à NULL
*

Code :

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

1
2
3
4
5
  while(fin!=1)
  {
               ptrNoeud=monter(ptrNoeud);
               printf("borneinf=%d\n",maBorne.inf);
  }

boucle sans fin. Le premier monter renvoie NULL. Le second avec NULL pour argument plante (voir remarque ci-dessus)

**lanageuse56** · 16/05/2007, 23h29

Je crois que je n'ai pas tout bien compris j'ai essayer de modifiier ce que vous m'avez dit mais je ne comprend pas la fin de ce qu vous m'avez dit:

- main : incohérent pour tester ce qui précéde
* ptrArbre ne sert à rien
* ptrNoeud est écrasé par chaque nouvelle entrée. Le nouveau noeud placé a ptrSup à NULL
*
Code :
while(fin!=1)
{
ptrNoeud=monter(ptrNoeud);
printf("borneinf=%d\n",maBorne.inf);
}boucle sans fin. Le premier monter renvoie NULL. Le second avec NULL pour argument plante (voir remarque ci-dessus)

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
// pvc version 17.cpp*: définit le point d'entrée pour l'application console.
//
 
#include <stdafx.h>
#include <stdio.h>
#include <stdlib.h>
#include "malloc.h"
 
typedef struct Borne {
 
       int Vd;//ville départ
       int Va;//ville arrivée
	   int borne;
	  // int matrice[][];
       }Borne;
 
 
typedef struct Noeud {
       Borne b;
       struct Noeud* ptrSup;
       struct Noeud* ptrAg;
       struct Noeud* ptrAd;
       }Noeud;
 
typedef struct Arbre {
       Noeud* ptrRacine;
       }Arbre;
 
Noeud* allNvNoeud (Borne b)
{
       Noeud* ptrNoeud;
       ptrNoeud=(Noeud*)malloc(sizeof (Noeud));
	   ptrSup=NULL;
	   if(ptrNoeud != NULL)
       {
		ptrNoeud->b.Va=b.Va;
		ptrNoeud->b.Vd=b.Vd;
		ptrNoeud->b.borne=b.borne;
		ptrNoeud->ptrSup=NULL;
		ptrNoeud->ptrAg=NULL;
		ptrNoeud->ptrAd=NULL;
	   }
		return ptrNoeud;
}
/*Noeud* allNvNoeuddr (Borne b)
{
       Noeud* ptrNoeud;
       ptrNoeud=(Noeud*)malloc(sizeof (Noeud));
	   if(ptrNoeud != NULL)
       {
       ptrNoeud->b.Va=b.Va;
       ptrNoeud->b.Vd=b.Vd;
       ptrNoeud->b.borne=b.borne;
       ptrNoeud->ptrSup=NULL;
       ptrNoeud->ptrAg=NULL;
       ptrNoeud->ptrAd=NULL;
	   }
       return ptrNoeud;
}*/
 
Arbre* allNvarbre(Borne racine)
{
       Arbre* ptrArbre=((Arbre*)malloc(sizeof *ptrArbre));
       if(ptrArbre != NULL)
		ptrArbre->ptrRacine=allNvNoeud(racine);
       return ptrArbre;
}
 
Noeud* insererAg (Borne b, Noeud* ptrNoeud)
{
       Noeud* ptrNouveaux = allNvNoeud(b);
       if(ptrNouveaux != NULL)
       {
         ptrNoeud->ptrAg=ptrNouveaux;
         ptrNouveaux->ptrSup=ptrNoeud;
       }
       return ptrNouveaux;
}
 
Noeud* insererAd (Borne b, Noeud* ptrNoeud)
{
       Noeud* ptrNouveaux = allNvNoeud(b);
       if(ptrNouveaux != NULL)
       {
         ptrNoeud->ptrAd=ptrNouveaux;
         ptrNouveaux->ptrSup=ptrNoeud;
       }
       return ptrNouveaux;
}
 
Noeud* descAg(Noeud* ptrNoeud)
{
    if(ptrNoeud !=0)   
	return ptrNoeud->ptrAg;
}
 
Noeud* descAd(Noeud* ptrNoeud)
{
	if(ptrNoeud !=0)  
	return ptrNoeud->ptrAd;
}
Noeud* monter(Noeud* ptrNoeud)
{
    if(ptrNoeud !=0)     
	return ptrNoeud->ptrSup;
}
 
int estVide (Arbre* ptrArbre)
{
    if(ptrArbre !=0)
	{
	if(((ptrArbre->ptrRacine->ptrAg)==NULL)&&(ptrArbre->ptrRacine->ptrAd==NULL))
       return 1;
       else
       return 0;
	}
}
 
int estFeuille(Noeud* ptrNoeud)
{
    if(ptrNoeud !=0)   
	return ((ptrNoeud->ptrAg==NULL)&&(ptrNoeud->ptrAd==NULL));
}
 
Noeud* affichage (Noeud* ptrNoeud)
{
       if (ptrNoeud!=NULL)
       {
              affichage(descAg(ptrNoeud));
              //printf("%d",ptrNoeud->b.valeur);
              affichage (descAd(ptrNoeud));
       }
       return 0;
}
 
int main()
{
	int choix/*valeur*/;
	int fin=0;
  Borne maBorne;
  Noeud* ptrNoeud=NULL;
  Arbre* ptrArbre=NULL;
  printf("entrer la borne inf");
  scanf("%d",&maBorne.borne);
  maBorne.Vd=0;
                                   maBorne.Va=0;
                  ptrArbre=allNvarbre(maBorne);
  while(fin!=1)
  {
                  printf ("entrer la ville de départ\n");
                  scanf ("%d",&maBorne.Vd);
                  printf ("entrer la ville d'arriver\n");
                  scanf ("%d",&maBorne.Va);
                  printf("entrer la valeur de la borne sup\n");
                  scanf("%d",&maBorne.borne);
                  ptrNoeud=insererAd(maBorne, ptrNoeud);
                  //printf("la borne est %d, la Vd est %d, la Va est %d",ptrNouveau->b.inf,ptrNouveau->b.Vd,ptrNouveau->b.Va);
 
				  printf("entrer la valeur de la borne inf\n");
                  scanf("%d",&maBorne.borne);
 
				  //monter au noeud precedent
                  ptrNoeud=monter(ptrNoeud);
 
                  //noeud gauche
 
                  ptrNoeud=insererAg(maBorne, ptrNoeud);
                  //printf("bornesup=%d",maBorne.inf);
                  printf("c'est la fin?");
                  scanf("%d",&fin);
  }
  fin=0;
  while(fin!=1)
  {
               ptrNoeud=monter(ptrNoeud); 
               ptrNoeud=monter(ptrNoeud);
               printf("borneinf=%d\n",maBorne.borne);
               /*ptrNoeud=descAd(ptrNoeud);
               printf("bornesup=%d\n",maBorne.sup);*/
               printf("c'est la fin?");
                  scanf("%d",&fin);
  }
 
 
  return 0;
}

Mais je ne comprend pas a quoi servent les

Code :

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

if(ptrNoeud != NULL)

**diogene** · 17/05/2007, 16h50

Mais je ne comprend pas a quoi servent les if(ptrNoeud != NULL)

Code :

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

1
2
3
4
5
Noeud* allNvNoeudga (Borne b)
{
       Noeud* ptrNoeud=malloc(sizeof *ptrNoeud);
       if(ptrNoeud != NULL)
....

Sert à vérifier que les allocations demandées ont reussi

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
int main()
{
....
  Noeud* ptrNoeud=NULL;
  Noeud* ptrArbre=NULL;
  while(fin!=1)
  {
....
                  ptrNoeud=allNvarbre(maBorne);
....
  }
  fin=0;
  while(fin!=1)
  {
               ptrNoeud=monter(ptrNoeud);
               printf("borneinf=%d\n",maBorne.inf);
  }
 
 
  return 0;
}

- ptrArbre n'est pas utilisé !
-ptrNoeud=allNvarbre(maBorne); chaque nouvel élément voit son adresse toujours rangée au même endroit, donc écrase celle du précédent. Ceci ne construit pas un arbre.
Par construction, le nouveau noeud a son champ ptrSup à NULL. Le permier appel à monter renvoie donc NULL. Alors, le second appel a NULL pour argument et

Code :

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

1
2
3
4
Noeud* monter(Noeud* ptrNoeud)
{
       return ptrNoeud->ptrSup;
}

plante lorsqu'on fait NULL->ptrSup

probléme avec arbre binaire

C

Discussions similaires

Partager

Partager