Arbre binaire equilibre

Version imprimable

Bonjour,
J essaye depuis ce matin de creer a partir d une liste chaine un arbre binaire equilibre. J ai reussi a faire quelque fonction dont une qui, en fonction du noeud envoye en parametre place l element voulu a gauche si y a de la place a droite sinon.

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
 
t_btree         *add_node_in_tree(t_btree *father, char *data)
{
  t_btree       *node;
 
  node = new_btree_node(data);
  if (father)
    if(!(father->left))
      {
          printf("Gauche : %s \n",data); //pour voir ou je cree
        father->left = node;
      }
    else
      if (!(father->right))
        {
          printf("Droite : %s \n",data); // pour voir ou je cree
          father->right = node;
        }
      else
        {
          free(node);
        }
  return (node);
}

j ai ensuite fait ma fonction sorted_list_to_btree et pour le momen je place au maximun 7 element correctement. Je n arrive pa a voir la recurence qui me permettrai d en ajouter plus
voici ma fonction

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
32
33
34
35
36
37
38
t_btree         *sorted_list_to_btree(t_list *l, int size)
{
  t_btree       *tree;
  t_btree       *tmp_tree;
  t_btree       *tmp2_tree;
  int           nbran;
  int           compt;
 
  compt = 1;
  nbran = calcul_nb_brch(size); // pour connaitre le nombre de niveau
  tree = new_btree_node(l->data);
  l = l->next;
  init_tree = tree;
  while (l)
    {
      tmp_tree = tree;
      while (compt < nbran && l)
        {
          printf(" Noeud courant : %s \n", tree->item); // pour connaitre le pere
          tmp2_tree = tree;
          tree = add_node_in_tree(tree, l->data);
          l = l->next;
          compt ++;
        }
      tree = tmp2_tree;
      compt --;
      while (compt < nbran && l)
        {
          printf(" Noeud courant : %s \n", tmp2_tree->item);
          tree = add_node_in_tree(tree, l->data);
          l = l->next;
          compt ++;
        }
      compt = 1;
      tree = init_tree;
    }
  return (tree);
}

je m arrache les cheveux aide moi please

23/10/2008, 16h45
Médinoc
Tu dois appeler récursivement sorted_list_to_btree() en lui passant en paramètre des sous-listes.

Typiquement, dans ta fonction:
- Tu crées un nœud
- Tu prends le milieu de la liste, tu le mets dans le nœud
- Tu passes le début de la liste (avant le milieu) à sorted_list_to_btree(), tu mets le noeud retourné en fils gauche de ton nœud
- Tu passes la fin de la liste (après le milieu) à sorted_list_to_btree(), tu mets le nœud retourné en fils droit de ton nœud
- Tu retourne le nœud
Plus gestion des cas particuliers (typiquement, liste vide--> retourner NULL).
23/10/2008, 19h08
toams69

deja merci de repondre si vite,

je suis vraiment un boulet en recursif, je ne vois pas trop ce comment appliquer ce que tu me dit
24/10/2008, 19h01
Climoo

Il y plusieurs trucs très bizarre que je ne comprend pas dns ton code...
Dans la fonction add_node_in_tree, s'il n'y a de place ni à gauche ni à droite, tu liberes le noeud et tu retourne son adresse (retourner une adresse qui n'est plus allouée, cest plutot dangereux...)

Dans l'autre fonction tu as un "init_tree" non déclarée. Variable globale? Enfin bon ca encore, cest pas trop bizarre.

Ensuite, est-ce que tu pourrais préciser ce qu'est censé faire la 2eme fonction? S'il sagit d'inserer des elements dans un arbre binaire, cest pas trop compliqué à faire (mais ta fonction ne fera jamais ca vu comment c'est écrit),
si l'arbre doit etre équilibré, ca complique pas mal les choses (AVL ?). En fait, j'aimerais bien savoir si ton arbre est un arbre binaire de recherche TRIE, ou si peu importe comment les éléments sont dans ton arbre, du moment que l'arbre est équilibré.

Mais dans tous les cas, je crois que pour t'en sortir, tu devrais prendre ton temps et écrire calmement ton algo sur papier (si si...). Parce que là, vu comment c'est parti (plein de tmp_tree partout, de variable bizarres...), et aussi tes deux boucles imbriquées qui ont exactement la meme condition d'arret, sauf que entre les deux tu fais un "compt--", je trouve ca TRES bizarre....

Bon courage...

EDIT : je comprend la logique de Medinoc, et son idée me semble bonne. Sauf que étant donné que tu as une liste chaînée, tu vas avoir du mal à accéder au milieu de la liste (enfin ca reste faisable). Mais dans le principe, le suis tout à faire d'accord avec Medinoc, et a la fin tu aurais bien un arbre binaire équilibré et trié.
25/10/2008, 14h26
Médinoc

Chaînée ? Merde.
J'avais simplement regardé le prototype, avec pointeur + taille, je pensais que tu avais un tableau...

Surtout qu'un conteneur "sorted list" est justement supposé être un tableau (une ArrayList, quoi) (les SortedList de .Net en sont), car l'intérêt d'un tableau trié est la possibilité de faire une recherche dichotomique dessus...