Discussion :

[bassirou]

Bonjour,
J'ai vraiment besoin d'aide pour implémenter un algorithme développé dans un article.
Il s'agit d'un arbre ou chaque noeud dispose de 2 fils chacun préfixé par des bit: ( le noeud racine a 2 fils, celui de gauche a comme prefix 0 et celui de droite 1) un noeud intermédiaire qui a un prefixe p voit son fils droit préfixé par p1 et son fils gauche prefixé par p0 ( par exemple le fils droit de la racine a comme prefixe 1 et son fils droit à son tour a comme prefixe 11, son fils gauche a 10 comme prefixe). Sur les noeuds feuille on stocke aussi des valeur de bit de taille D (exple D=6 entraine 0110001) et chaque noued stocke au maximum B valeurs.
EN ajoutant une nouvelle valeur, celle ci est stocké sur la feuille qui a le même prefix qu'elle ( 0110001 sera ajouté par exemple sur le noeud feuille de prefix 011)

J'ai fait un programme en utilisant le type BitSet de java mais ça ne convient pas car il m'ai impossible de controler la taille du BitSet.

S'il vous plait j'ai besoin de savoir comment faire ceci, qu'est ce que je dois utiliser comme type de données, comment déterminer si un prefixe vérifie une valeur ou pas??

Je vous remercie par avance!!!

[Mako 5013]

Bonjour,

qu'est ce que je dois utiliser comme type de données

Pourquoi ne pas utiliser simplement des String ? Tu déclares deux constantes finales qui correspondent à tes valeurs possibles (i.e. 0 et 1 dans ton cas), et suivant le cas, tu ajoutes l'une ou l'autre à la chaine du noeud père. L'avantage étant que tu peux très facilement travailler avec la taille de cette chaîne.

comment déterminer si un prefixe vérifie une valeur ou pas

Qu'entends-tu par "vérifier une valeur" ? Si tu veux savoir par exemple que ta chaîne commence, termine, ou contient une certaine séquence (ex. : 10010), tu peux travailler avec des expressions régulières (toujours dans l'optique de travailler à la base avec des String).

Mako.

[ticroch]

Tu veux faire quoi avec tes arbres en fait, j'en ai souvent fait je faisais comme ca :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
Public class Tree {
    private Tree left_children = null;
    private Tree right_children = null; // si pas d'enfant, on est une feuille
    private Tree parent = null;   // si parent est null, on est a la racine
 
    // faire getters et setters
}

Après tu peux faire tous les parcours infixe, préfixe, suffixe assez facilement avec une méthode récursive. Dans ton cas a chaque fois que c'est un fils gauche, tu inscris un 0, si c'est un fils droit, tu inscris un 1

[bassirou]

Merci Mako

Pourquoi ne pas utiliser simplement des String ? Tu déclares deux constantes finales qui correspondent à tes valeurs possibles (i.e. 0 et 1 dans ton cas), et suivant le cas, tu ajoutes l'une ou l'autre à la chaine du noeud père. L'avantage étant que tu peux très facilement travailler avec la taille de cette chaîne.
Mako.

Oui j'ai pensé à String ça m'archera mais pour une autre utilisation je dois recoder l'arbre. En effet après la première étape je vais utiliser l'arbre pour stocker des vecteur de bit (BitSet)

Qu'entends-tu par "vérifier une valeur" ?
Mako.

je veux dire si la valeur à ajouté commence par le prefix du noeud

[bassirou]

Mercii
je l'ai finalement fait avec String

[47hm4n3]

Bonjour a tous,

je voudrais savoir si quelqu'un aurait connaissance de comment on pourrait implémenter ce type d'arbres!!!
surtout que je ne suis pas très fort en java, et que c'est le langage demandé pour la réalisation du projet (exactement le même!!)

merci par avance ;-)