Insertion arbre ternaire

Version imprimable

23/05/2008, 18h05
line86

Insertion arbre ternaire

Bonsoir a vous,
J'essaye de coder en C l'insertion de mots dans un arbre ternaire...
Mais je suis bloqué au niveau de l'algorithme...

Si vous pouviez me donner des pistes.

Merci par avance
23/05/2008, 20h56
PRomu@ld

Peux-tu nous dire à quel point tu bloques ? Ce que tu as fait ?

J'ai essaye de le coder en C, mais comme je ne vois pas l'algorithme qu'il faut utiliser...

Code:

1
2
3
4
5
6
7
8
9
10
 
si le noeud est null
--- Ajouter le tout ds le fils du milieu
sinon
--- lettre < f->lettre
------on relance la fonction en descendant dans l'arbre par le fils gauche
--- lettre > f->lettre
------on relance la fonction en descendant dans l'arbre par le fils droit
--- lettre == f->lettre
------on relance la fonction en descendant dans l'arbre par le fils

voila...

Merci pour votre aide

25/05/2008, 22h33
PRomu@ld

Expliques nous ta structure de données et comment elle fonctionne. Il y a de fortes chances qu'en nous l'expliquant tu puisses trouver ton algorithme.

Il s'agit d'une structure de tri lexicographique par dichotomie.
L'ajout insert et la recherche find s'implémentent de façon assez immédiate, par exemple en OCaml (le code en marron est le type inféré par OCaml):

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
39
40
module Ternary = struct

type t =
  | Nil
  | Node of t * char * t * t

let rec insert t l =
  match t,l with
  | Nil,[] ->
      t
  | Node(less,chr,equal,more),[] ->
      t
  | Nil,c::d ->
      Node(Nil,c,insert Nil d,Nil)
  | Node(less,chr,equal,more),c::d ->
      if c < chr then Node(insert less l,chr,equal,more)
      else if c > chr then Node(less,chr,equal,insert more l)
      else Node(less,c,insert equal d,more) 

let rec find t l =
  match t,l with
  | Nil,[] ->
      true
  | Node(less,chr,equal,more),[] ->
      true
  | Nil,c::d ->
      false
  | Node(less,chr,equal,more),c::d ->
      if c < chr then find less l
      else if c > chr then find more l
      else find equal d       

end;;
module Ternary :
  sig
    type t = Nil | Node of t * char * t * t
    val insert : t -> char list -> t
    val find : t -> char list -> bool
  end

Salut!

C'est un peu tard!
Voici le code de l'ajout d'un mot dans un arbre ternaire lexicographique en langage C :

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
 
 
void ajoutMot(ArbreT *arbre,int pos,char *val){
 
	/* arbre est null => on est arrivé a un endroit ou on peut insérer la lettre => la racine devient le nouvel arbre
	 * puis continuera eventuellement son parcours dans la derniere condition si il reste des lettres a inserer 
	 * */
	if(*arbre == NULL){
		ArbreT arbreNew = creerArbreT();
		arbreNew->val = val[pos];
		*arbre = arbreNew;
 
		/*  
		 * Si la lettre parcouru n'est pas \0 donc la fin du mot alors on *continu a ajouter les lettres du mot en avant
		 * 
		 */
		if(val[pos] != '\0'){
			ajoutMot(&((*arbre)->filsMilieu),pos+1,val);
		}
	}
	/* on trouve la meme valeur dans l'arbre, alors on insere pas car cette lettre y est deja, on fait juste
	 * de continuer le parcours en avant et on passe a la lettre suivante a inserer*/
	else if((*arbre)->val == val[pos]){
		return ajoutMot(&((*arbre)->filsMilieu),pos+1,val);
	}
	/* notre lettre a insere est plus grande, alors on doit l'inserer a droite de l'arbre courant, on appel
	 * la fonction sur le fils droit avec pos et non pos+1 car on a pas encore insere la valeur*/
	else if((*arbre)->val < val[pos]){
		return ajoutMot(&((*arbre)->filsDroit),pos,val);
	}
	/* notre lettre a insere est plus petite, alors on doit l'inserer a gauche de l'arbre courant, on appel
	 * la fonction sur le fils gauche avec pos et non pos+1 car on a pas encore insere la valeur*/
	else if((*arbre)->val > val[pos]){
		return ajoutMot(&((*arbre)->filsGauche),pos,val);
	}
}

Je sais pas si C'est super bien codé mais ca marche bien en tout cas.:king: