Arbres binaires [Sources]

[wincher]

je pense qu'une partie consacrée aux arbres serait la bienvenue !!
- comment créer un arbre binaire ?
- quelles sont les fonctions de bases pour manipuler des arbres binaires ?

j'ai moi même besoin d'aide concernant les arbres en C notamment à cause des pointeurs et j'ai du mal à m'en sortir !

réponses aux 2 questions :

+ Un abre binaire est une suite de pointeurs, chaque pointeurs pointe une structure dans laquelle on peut mettre une valeur (int ou char par exemple) ainsi que 2 champs pointant les structures suivantes (appelées fils gauche et fils droit). En clair : un arbre généalogique est un arbre binaire à l'envers.

Code :

1
2
3
4
5
6
7
struct elem{
	char lettre;
	struct elem* fg;
	struct elem* fd;
} t_noeud;
typedef struct elem noeud;
typedef struct elem *arbre;

+ Voila les fonctions de base :

Code :

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
boolean estvide(arbre a)
	{return a==NULL;}
 
/*** A noter qu'en C le type booleen n'est pas defini il faut donc le definir auparavent comme ceci par exemple : 
#define FALSE 0
#define TRUE  1
typedef unsigned char boolean; 
***/
 
arbre gauche(arbre a)
	{return a->fg;}
 
arbre droit(arbre a)
	{return a->fd;}
 
char valeur(arbre a)
	{return a->lettre;}
 
arbre cons(char c, arbre filsg, arbre filsd)
	{
	arbre p;
	p=(arbre)malloc(sizeof(noeud));
	p->lettre=c;
	p->fg=filsg;
	p->fd=filsd;
	return p;
	}
 
/*** Cette fonction sert a construire un arbre exemple : cons(T,cons(A,NULL,NULL),cons(W,NULL,NULL));
ici T pointe vers A vers la gauche et W vers à droite, A et W pointant vers NULL pour signaler la fin de l'arbre.
***/

[PRomu@ld]

Personnellement, je ne pense pas que celà devrait faire partie de la fac, ce n'est pas un problème du langage, tout ceci devrai être dans la partie source.

[gl]

Envoyé par PRomu@ld

Personnellement, je ne pense pas que celà devrait faire partie de la fac, ce n'est pas un problème du langage, tout ceci devrai être dans la partie source.

Entierement d'accord avec toi. J'ai d'ailleur modifier le TAG de la question

[millie]

Envoyé par wincher

Code :

Je trouve que ce genre de declaration (desole, je suis sur qwerty) est a eviter, sans connaitre l'implementation, on pourrait croire que l'arbre a est mis entierement sur la pile (alors que ce n'est qu'un pointeur).

p=(arbre)malloc(sizeof(noeud));

Le cast est inutile.

Tu n'as definis aucun destructeur... Je trouves qu'il manque des operations tel que : estFeuille.

Une operation de parcours serait egalement utile, car ici, sans connaitre l'implementation, on serait oblige d'effectuer des appels recursifs (a eviter en C, il peut vite y avoir un debordement de pile).

[Médinoc]

Pour un arbre à chaînage simple, de toute façon, il faudra forcément une pile (qu'elle soit sur la pile du programe (récursif pur) ou sur le tas("itératif avec pile")) pour faire un parcours...

[disturbedID]

Envoyé par Médinoc

Pour un arbre à chaînage simple, de toute façon, il faudra forcément une pile (qu'elle soit sur la pile du programe (récursif pur) ou sur le tas("itératif avec pile")) pour faire un parcours...

Pour quel type de parcours?
Ca ne me semble pas impossible de parcourir un arbre sans utilisé de pile, mais juste avec 1 ou 2 variable temporaires.

[Médinoc]

Pour un parcours en profondeur : Avec un chaînage simple, une pile est indispensable pour remonter.

[disturbedID]

Envoyé par Médinoc

Pour un parcours en profondeur : Avec un chaînage simple, une pile est indispensable pour remonter.

nono, si tu parle juste de parcourir un arbre bianaire, j'essayerai de donner un pseudo code si t'es pas convaincu.

[Médinoc]

Donne donc.

[disturbedID]

Envoyé par Médinoc

Pour un parcours en profondeur : Avec un chainage simple, une pile est indispensable pour remonter.

Je viens de comprendre notre différant, je suppose que dans ton arbre, tu n'as pas de champs père ? Si c'est le cas je m'excuse de pas avoir prévenu plus tôt et effectivement la pile et obligatoire.

[Médinoc]

En effet, c'est ce que je voulais dire par "avec un chaînage simple".

[Franck.H]

Ouch Il est vieux ce post dis donc Ca me semble un peu légé pour ajouter ca dans les sources, pas de structuration de la source etc...C'est un peu donné à la va-vite.

Le code lui même n'est pas au top, aucun test sur les arguments ni même sur les allocations de mémoire etc... vraiment aucun sécurité

Dommage