Sommaire

Contrôler un arbre binaire

1. Créer un arbre binaire

Les fonctions proposées ici permettent de créer des arbres soit à partir d’une description, soit de façon totalement aléatoire. Notre objectif est de les utiliser ensuite pour tester les fonctions de gestion des arbres.

a. Créer un arbre à partir d’un schéma descriptif

Voici l’arbre à créer :

images/06ri61.PNG

Créer l’arbre "à la main", avec une fonction de création de nœud

Nous allons créer un arbre dynamique. Nous avons besoin d’un tableau de caractères pour stocker une chaîne (ou éventuellement juste un caractère puisqu’il n’y a que des caractères à stocker) et de deux pointeurs, un pour le fils gauche et un pour le fils droit. La structure de données est la suivante :

typedef struct noeud{ 
   char dat[80]; 
   struct noeud*g, *d; 
}t_noeud;

Voici une fonction pour initialiser un nœud de l’arbre :

t_noeud* CN(char s[],t_noeud*g, t_noeud*d) 
{ 
t_noeud*n; 
   n=(t_noeud*)malloc(sizeof(t_noeud)); 
   strcpy(n->s, s); 
   n->g=g; 
   n->d=d; 
   return n; 
}

et la fonction pour créer l’arbre :

t_noeud* creerArbre1() 
{ 
   return CN("A", 
                  CN("B", 
                        CN("D",NULL,NULL), 
                        CN("E",NULL,NULL)), 
                  CN("C", 
                        CN("F", 
                               CN("H",NULL,NULL), 
                               NULL), 
                        CN("G",NULL,NULL))  ...