IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Vous êtes nouveau sur Developpez.com ? Créez votre compte ou connectez-vous afin de pouvoir participer !

Vous devez avoir un compte Developpez.com et être connecté pour pouvoir participer aux discussions.

Vous n'avez pas encore de compte Developpez.com ? Créez-en un en quelques instants, c'est entièrement gratuit !

Si vous disposez déjà d'un compte et qu'il est bien activé, connectez-vous à l'aide du formulaire ci-dessous.

Identifiez-vous
Identifiant
Mot de passe
Mot de passe oublié ?
Créer un compte

L'inscription est gratuite et ne vous prendra que quelques instants !

Je m'inscris !

Apprendre à programmer les arbres binaires en langage C,
Un tutoriel de CGi

Le , par Community Management

0PARTAGES

3  0 
Bonjour, je vous présente ce tutoriel de CGi pour apprendre à programmer des arbres binaires en langage C.

Tout comme les listes chaînées, les arbres servent à mémoriser des données. Ils sont constitués d'éléments que l'on appelle souvent des nœuds (node). Ils sont semblables aux listes chaînées par le fait que les éléments sont chaînés les uns avec les autres, mais avec la possibilité que plusieurs branches partent d'un nœud, d'où leur nom (on pourrait très bien voir une liste chaînée comme un arbre à une seule branche). Il est courant d'appeler le premier élément d'un arbre la racine. La racine est un nœud qui n'a pas de parent. On peut aussi entendre parler de feuilles, ce sont les nœuds qui sont au bout des branches et qui n'ont donc pas d'enfants.

Ce tutoriel étant destiné à aborder les arbres, nous allons donc en créer un qui sera le plus simple possible, ce sera un arbre binaire.
Bonne lecture

Une erreur dans cette actualité ? Signalez-nous-la !

Avatar de picodev
Membre émérite https://www.developpez.com
Le 10/03/2017 à 19:52
static est, en C concernant les fonctions, à opposer à extern. Par défaut les fonctions sont visibles de l'extérieur d'un module : elles sont par défaut déclarées en extern (implicite). Déclarer une fonction C en static permet d'en réduire la visibilité au module où elle est déclarée, elle ne pourra plus être accessible d'un autre module. Cela concerne les fonctions qui n'ont rien à faire dans un API et qui ne servent qu'en interne à un module.
Les deux fonctions que tu cites ont cette propriété, personne n'a à les utiliser en dehors du module, d'où le static.

static est également très utile pour créer des fonctions qui remplaceront avantageusement les macros ; ce sont les fonctions static inline dans les headers.
2  0 
Avatar de Matt_Houston
Expert confirmé https://www.developpez.com
Le 03/05/2018 à 15:30
On a choisi de représenter un arbre vide par un pointeur nul de type nœud (c'est une conception courante). Si l'on veut pouvoir ajouter un nœud à un arbre vide, et donc attribuer une autre valeur que NULL à son pointeur de nœud racine, il faut passer ce dernier par référence. En C, on passe une variable par référence en passant son adresse et donc en augmentant le niveau d'indirection.

Si l'on passait par copie :

Code : Sélectionner tout
1
2
3
4
5
6
7
8
void add_node(node *tree, int value);

// ...

{
    node *tree = NULL; // arbre vide
    add_node(tree, 42); // par copie..
    assert(tree == NULL); // fail, tree n'est pas modifié !
Puisque l'on passe par référence :

Code : Sélectionner tout
1
2
3
4
5
6
7
8
void add_node(node **tree, int value);

// ...

{
    node *tree = NULL; // arbre vide
    add_node(&tree, 42); // par référence..
    assert(tree != NULL); // ok, tree n'est plus vide
1  0 
Avatar de Médinoc
Expert éminent sénior https://www.developpez.com
Le 25/02/2016 à 13:30
C'est bizarre, avec ce paragraphe d'introduction on s'attend plutôt à voir un article sur les arbres binaires de recherche auto-équilibrés qu'un article sur les tas...

En même temps, je te remercie pour cet article, très instructif. Je n'avais jamais compris le principe des arbres "tas" avant...
0  0 
Avatar de bob95200
Nouveau Candidat au Club https://www.developpez.com
Le 10/03/2017 à 19:02
Bonjour,
Tout d'abord grand merci pour ces deux tutos sur les arbres, c'est pour bonne entrée en matière pour me replonger dans le Cormen (Algorithmes).
Donc ma question à propos de static sur les deux fonctions reorganizeHeap et HeapRealloc : en C++ Ok mais je n'ai jamais compris l'intérêt en C et encore moins vu en pratique.
Merci par avance
0  0 
Avatar de yassine316
Nouveau Candidat au Club https://www.developpez.com
Le 03/05/2018 à 13:41
bojour
d'abord je remerci tous ceux qui participer pour construire cette article.
je suis un debutant, ce qui fait que mon question EST un peu basique, ma question es la suivante :
pour quoi on passe un pointeure de pointeur en paramatre dans la fonction addNode , je pence que on aurait pu lui passer que un pointeure
0  0 
Avatar de Sve@r
Expert éminent sénior https://www.developpez.com
Le 04/05/2018 à 20:10
Citation Envoyé par yassine316  Voir le message
pour quoi on passe un pointeure de pointeur en paramatre dans la fonction addNode , je pence que on aurait pu lui passer que un pointeure

Bonjour

Une fonction qui reçoit un élément en paramètre ne reçoit qu'une copie de ce qu'on lui envoie. N'oublie jamais ce point et tu t'en sortiras en C.
Exemple
Code c : Sélectionner tout
1
2
3
4
5
6
7
8
9
10
int main() { 
	int x=500; 
	fct(x);	// Ici la fonction ne reçoit qu'une copie de "x" (même si cette copie est stockée dans une variable portant le même nom) 
	// Ici "x" est resté inchangé 
	printf("x=%d\n", x); 
} 
  
void fct(int x) { 
	x=123;	// Ici affectation de "123" dans la variable locale "x" (qui ne contient qu'une copie de ce qu'on a envoyé à la fonction). Quel que soit ce qu'on lui envoie, ça reste inchangé 
}

Si on veut qu'une fonction modifie une variable, alors il faut lui passer l'adresse de cette variable. La fonction stockera une copie de cette adresse mais les adresses étant communes à tout le code, même avec une copie de l'adresse on peut quand-même aller à cette adresse et modifier ce qui s'y trouve.
Et une adresse est stockée dans un pointeur (pointeur du type de la variable d'origine)
Exemple
Code c : Sélectionner tout
1
2
3
4
5
6
7
8
9
10
int main() { 
	int x=500; 
	fct(&x);	// Ici la fonction reçoit une copie de l'adresse de "x". Mais même une copie de l'adresse reste l'adresse réelle de "x". 
	// Ici "x" a été modifié 
	printf("x=%d\n", x); 
} 
  
void fct(int *pt) { 
	*pt=123;	// Ici affectation de "123" à l'adresse copiée dans "pt". Si cette adresse est l'adresse d'une variable réelle, alors cette variable est modifiée 
}

Donc la règle est la suivante: une fonction qui doit modifier une variable de type truc reçoit l'adresse de cette variable et stocke cette adresse dans un truc étoile.

Si maintenant le type "truc" est déjà un pointeur (de type donc xxx étoile), la règle ne change pas. On lui passe l'adresse de cette variable. Et cette adresse sera alors stockée dans un xxx étoile étoile.

Exemple avec "tree" de type "node étoile"...

Code c : Sélectionner tout
1
2
3
4
5
6
7
8
9
10
11
int main() { 
	node* tree=NULL; 
	fct(&tree);		// Ici, comme avant, la fonction reçoit une copie de l'adresse de "tree". Mais "tree" étant un "node étoile", cette adresse sera stockée dans un "node étoile étoile" 
  
	// Ici "tree" a été modifié 
	printf("tree=%p\n", tree); 
} 
  
void fct(node* *pt /* Qu'on écrit plutôt "node **pt") */ { 
	*pt=malloc(sizeof(node));	// Ici le retour de "malloc" est stocké à l'adresse placée dans "pt" (donc à l'adresse référencée par la variable "node" 
}
0  0