Discussion :

[lanageuse56]

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]

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

[LinuxUser]

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]

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

Merci pour ton aide

[lanageuse56]

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]

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]

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;
}