Arbre de prefixe binaire

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!!!

Bonjour,

Citation:

---

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.

Citation:

---

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.

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

Code:

---

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

Merci Mako

Citation:

---

Envoyé par Mako 5013

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)

Citation:

---

Envoyé par Mako 5013

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

---

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

Mercii
je l'ai finalement fait avec String

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 ;-)