qq'un pourrait m'expliquer comment ca marche...
parce que la je capte rien du tout...

[edit]--Message édité par swich--[/edit]

précise ce que tu veux...

Tu veux dire binaire ?
Arbre binaire de recherche ?

vi arbre binaire de recherche sur des chaine de caractere.
ex :
 
  a
   \
   an
     \
      annuel
     /
    anne
 
etc

[edit]--Message édité par swich--[/edit]

Alors un arbre binaire en programmation fonctionnel c'est
 
(la notation)
(/G,r,D\)  
 
avec G partie Gauche, r racine et D partie Droite
 
G et D sont considéré comme racines de sous-arbres binaires
En partant d'une racine, il ne peux y avoir que deux branches dans un arbre binaire.

vi c'est ca.
mais bon ca je le savais....

ben... voila, c kom dans les camps avec ls juifs ...
 
Les femmes a gauche et les hommes a droite

bon pour résumer, je dirai que c'est uns structure de données destinée à trier les éléments pour accélérer l'insertion et la recherche de données.
dans le cas des binaires, il y a au plus deux fils, et on détermine en fonction d'un ordre de tri le placement dans l'arbre ( généralement, c'est l'ordre > ou < qui est utilisé ).
par exemple dans le cas d'un arbre stockant des entiers, on détermine la place dans l'arbre en testant les valeurs dans le noeud courant, si c'est supérieur on cherche dans l'arbre droit, si c'est supérieur on cherche dans l'arbre gauche.
 
donc cela doit donner pour insérer un élément, on cherche d'abord dans la racine. si y'a rien dans la racine, alors on crée l'élément dans la racine.
sinon, on teste avec la valeur et si la valeur est supérieure à la valeur de la racine, on regarde si il y a quelquechose dans le fils droit. si y'a rien on crée la valeur dans le fils droit, sinon on reprend le cas de figure racine.
si c'est inférieur, on fait le même test que juste au dessus.
ceci est un algorithme récursif qui te permettra d'insérer des valeurs dans un arbre binaire de recherche. pour rechercher une valeur, c'est exactement le même algorithme, sauf qu'on insère rien. pour afficher la liste, on affiche d'abord le fils gauche, puis la racine, puis le fils droit. lorsqu'on tombe sur une feuille ( c'est à dire un noeud sans fils ) on affiche la valeur et basta.
pour supprimer un élément, c'est un peu plus compliqué, mais si tu as déjà compris le principe de l'arbre binaire, tu trouveras comment supprimer.
principal inconvénient des arbres binaires de recherche : tu n'es pas sur d'avoir un arbre bien équilibré ( comme celui que tu as fourni en exemple ). par contre là, pour rééquilibrer l'arbre, c'est nettement plus compliqué.
si tu n'as rien compris à ce que je viens de dire, ou que tu ne sais pas comment fonctionnent les pointeurs pour faire un arbre binaire de recherche, n'hésites pas à reposer d'autres questions.

watouwatou >> très douteux comme humour  
 
Sinon, ddr555 a bien expliqué le bazard, mar swich, tu ne nous as toujours pas expliquer ce que tu veux EXACTEMENT, s'il s'agit du principe, de l'implémentation, de l'algo général, du rebalancement de l'arbre...

ben le principe, c'est bon.
il me faudrait l'algo (pour le construire en normal, c'est bon, mais c'est pour le construire en recursivite terminale, et la j'ai du mal...j'y arrive pas.
 
si qq'un connait, comment faire pour eviteer l'erreur : error : could not grow, sous emacs ???

Si les noeud de ton arbres ont la structure suivante:
- valeur v
- référence/pointeur sur noeud gauche rng
- référence/pointeur sur noeud gauche rnp
 
alors tu peux utiliser la procédure suivante:
ajout( nouvelle valeur nv, référence sur un noeud rn):
 si (nv > rn-> v)
 alors
  si (rn->rnd vide)
  alors
   créer une feuille avec la valeur nv et affecter à rn->rnd une réference vers cette feuille
  sinon
   ajoute(nv, rn->rnd)
 sinon
 .... // la même chose avec le noeud fils gauche

le principe c'est bon j'ai compris, mais c'est pour ce qui est de la construction de l'arbre...
verdoux a resume l'algo en recursif normale, mais bon comme je travaille avec des grosses liste... la recursivite terminale, je crois que c'est ce qu'il y'a de mieux.et c la que ca plante.
j'y arrive pas.
donc c'est ce que je demandais, une explication pour la recursivite terminale.
pff ca fait 1semaine que je suis sur ce pb ca commence a me peter les c@@@@@@s....

Elle est pas terminale mais récursivité ?

hein ???

L'algo donné est en récursivité terminale.

ah
ben c'est pas cool ca car je comprend pas..., pourtant la recursivite, j'ai pas de pb..

exemple recursif non terminal:
compter (n) {
  if (n>0)
  return compter(n-1)+1;
  else
  return 0;
}
 
Le meme en recursif terminal:
compter (n, res) {
  if (n>0)
  return compter(n-1,res+1);
  else
  return res;
}
 
et il faut l'initialiser par un compter(n,0);
 
Tu remarqueras que dans le premier cas, il est
necessaire de memoriser le contexte d'appel de compter()
puisqu'au retour de la fonction il faudra encore effectuer l'operation +1 sur la valeur de retour.
Dans le deuxime cas par contre, pas besoin de stocker ce contexte d'appel.
en effectuant le calcul pour n avec la premiere methode,
tu mets n procedures en attente, tandis qu'avec la deuxieme, chaque procedure passe le bebe a la suivante et ne doit rien attendre.
 
A+
LEGREG

Une methode toujours efficace c'est de passer par des boucles conditionnelles, ce qui est efficace quel que soit
le compilateur utilise:
 
ajoute(insere, ref racine) {
 if (racine == null) {
  racine = nouveau noeud (insere, null, null);
 } else {
  courant = racine;
  while (true) {
   if (courant->valeur > insere) {
     if (courant->filsgauche == null) {
       courant->filsgauche = nouveau noeud(insere, null, null);
       break;
     } else {
       courant = courant->filsgauche;
     }
   } else {
     if (courant->filsdroit == null) {
       courant->filsdroit = nouveau noeud(insere, null, null);
       break;
     } else {
       courant = courant->filsdroit;
     }
   }
  }
 }
}
Legreg

legreg> Le problème du C, c'est que ce genre de boucle n'est pas super lisible, parce qu'on ne voit pas très bien le ou les endroits où on quitte la boucle. Dans ces cas-là, j'utilise 2 macros toutes simples qui éclaircissent pas mal le code (à mon avis) :
 
    #define forever() for( ; ; )
    #define EXIT_WHEN(condition) if (condition) break
 
En les utilisant, le code ci-dessus devient :
 
ajoute(insere, ref racine) {
 if (racine == null) {
  racine = nouveau noeud (insere, null, null);
 } else {
  courant = racine;
  forever() {
   if (courant->valeur > insere) {
     if (courant->filsgauche == null) {
       courant->filsgauche = nouveau noeud(insere, null, null);
 
       EXIT_WHEN(true);
     } else {
       courant = courant->filsgauche;
     }
   } else {
     if (courant->filsdroit == null) {
       courant->filsdroit = nouveau noeud(insere, null, null);
 
       EXIT_WHEN(true);
     } else {
       courant = courant->filsdroit;
     }
   }
  }
 }
}
 
Sinon, juste pour le plaisir de critiquer , pour obtenir un code le plus lisible possible, il vaut mieux limiter l'imbrication du code, et factoriser au maximum le code. Je proposerai donc la réécriture du code de legreg suivante :
 
ajoute(insere, ref racine) {
  if (racine == null) {
    racine = nouveau noeud (insere, null, null);
    return;
  }
 
  courant = racine;
  var pfils_courant;   // On déclare une variable de type "pointeur sur le type de courant".
 
  forever() {
    if (courant->valeur > insere) {
      pfils_courant = &courant->filsgauche;
    }
    else {
      pfils_courant = &courant->filsdroit;
    }
 
    if (*pfils_courant == null) {
      *pfils_courant = nouveau noeud(insere, null, null);
 
      EXIT_WHEN(true);
    }
    else {
      courant = *pfils_courant;
    }
  }
}

[edit]--Message édité par BifaceMcLeOD--[/edit]

ok merci bien zetes gentil les gars mais bon, mon pb c'est en scheme...
mais bon merci qd meme ca m'aide.
comment peut on construire un arbre binaire equilibre???

Pour les arbres binaires équilibrés c'est un peu plus compliqué je vais juste te donner quelque indications car je n'ai pas le temps et tu pourras réfléchir un peu dessus :
 
il faut que tu change ta structure d'arbre en  
{arbre *gauche; arbre *droit; arbre *pere; int coefficient_de_desequilibre} où coefficient_de_desequilibre est la différence entre la hauteur du fils droit et celle du fils gauche par exemple pour un arbre équilibré (en hauteur) ca vaudra donc -1 0 ou 1
 
Il te faudra utiliser quatre petites fonctions élémentaires:
 
arbre gauche_gauche(arbre a) {
if (a != NULL)
   {arbre temp = a-> droit;
    a->droit = temp->gauche;
    temp->gauche=a;
    a=temp;
  }
  return a;
}
 
Sur le meme principe tu construits la fonction droit_droit.
 
Ensuite;
 
arbre gauche_droit(arbre a)
{a->gauche = gauche_gauche(a->gauche);
  return droit_droit(a);
}
 
Sur le même principe tu construits la fonction droit_gauche.
 
Il te reste plus qu'à insérer tes éléments en utilisant ton coefficient de désiquilibre et tes quattre petites fonctions.
Je te conseille sérieusement de faire des schémas pour comprendre ce que font tes 4 fonctions et comment les utiliser. (Après à toi de mater ton cours de Scheme pour implémenter l'algo)

[edit]--Message édité par zeltron--[/edit]

L'Hammeral est un "bon" bouquin d'algorithmique. Tu y trouveras tout ce que tu veux sur les arbres et le rebalancement(reequilabrage si tu veux). Tu as pense a l'implementation d'un arbre dans un vecteur?

l'hammeral, ok, je le note.
j'espere qu'il est en francais...
merci bien