[Strategie]arborescence : quelle structure choisir ?

Version imprimable

14/09/2004, 17h32
iubito

[Strategie]arborescence : quelle structure choisir ?
Salut !
Je suis en train de chercher quelle structure conviendrait mieux à mon application.

Je veux avoir (en mémoire) pas de graphisme ( :!: ) une structure (Tree? TreeMap? Node ?...) qui me permette d'avoir une arborescence simple, non triée.
Par exemple :
Code:

1 2 3 4 5 6 7 Racine +- 101 Dossier 1 +- 102 Dossier 2 | +- 102/1 Sous-Dossier | +- 102/2 hop hop hop +- 200 hop là ! ...
avec à chaque fois un couple clé/texte, la clé étant un String que je défini moi même.

En gros, à chaque noeud un couple de String, et possibilité d'avoir des enfants.

Selon vous, quelle classe je devrais utiliser ? Parce qu'en regardant TreeMap et compagnie je vois que ça parle de tri et je n'en veux surtout pas !

Je n'ai pas beaucoup d'opérations à faire dessus, des ajouts d'enfants et de noeuds, et ensuite juste un parcours récursif.
14/09/2004, 18h19
Debernad

La structure des nodes est adapté à une arborescence ...
Il existe plusieurs interfaces ...
Par exemple, celle du xml : org.w3c.dom.Node
ou celle de swing : javax.swing.tree.TreeNode

Elles représentent uniquement des interfaces de structures de données ...
Pour Swing, il y a une implémentation qui javax.swing.tree.DefaultMutableTreeNode.

Qui te permettera de gérer une arborescence sans trop de difficulté incluant plusieurs méthodes trés utiles.

Cette classe est une structure de donnée et donc même si tu vois le mot swing dans le package , tu peux l'utiliser même si tu es sur un serveur Unix sans affichage graphique car il n'y a aucune dépendance graphique.

La classe suivante est destinée aux arbdres binaires et implémente directement la définition récursive de ces derniers.

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
import java.util.*;
 
public class BinaryTree extends java.util.AbstractCollection
{ protected Object root;
  protected BinaryTree left, right, parent;
  protected int size;
 
  public BinaryTree()
  {
  }
 
  public BinaryTree(Object root)
  { this.root = root;
    size = 1;
  }
 
  public BinaryTree(Object root, BinaryTree left, BinaryTree right)
  { this(root);
    if (left != null)
    { this.left = left;
      left.parent = this;
      size += left.size();
    }
    if (right != null)
    { this.right = right;
      right.parent = this;
      size += right.size();
    }
  }
 
  public boolean equals(Object object)
  { if (!(object instanceof BinaryTree)) return false;
    BinaryTree tree = (BinaryTree)object;
    return ( tree.root.equals(root)
          && tree.left.equals(left)
          && tree.right.equals(right)
          && tree.parent.equals(parent)
          && tree.size == size);
  }
 
  public int hashCode()
  { return root.hashCode() + left.hashCode() + right.hashCode() + size;
  }
 
  public java.util.Iterator iterator()
  { return new java.util.Iterator()  // anonymous inner class
    { private boolean rootDone;
      private java.util.Iterator lit, rit;  // child iterators
      public boolean hasNext()
      { return !rootDone || lit != null && lit.hasNext()
                         || rit != null && rit.hasNext();
      }
      public Object next()
      { if (rootDone)
        { if (lit != null && lit.hasNext()) return lit.next();
          if (rit != null && rit.hasNext()) return rit.next();
          return null;
        }
        if (left != null) lit = left.iterator();
        if (right != null) rit = right.iterator();
        rootDone = true;
        return root;
      }
      public void remove()
      { throw new UnsupportedOperationException(); 
      }
    };
  }
  public int size()
  { return size;
  }
}

Pour tester

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
 
public class Test
{ static public void main(String[] args)
  { BinaryTree e = new BinaryTree("E");
    BinaryTree g = new BinaryTree("G");
    BinaryTree h = new BinaryTree("H");
    BinaryTree i = new BinaryTree("I");
    BinaryTree d = new BinaryTree("D",null,g);
    BinaryTree f = new BinaryTree("F",h,i);
    BinaryTree b = new BinaryTree("B",d,e);
    BinaryTree c = new BinaryTree("C",f,null);
    BinaryTree tree = new BinaryTree("A",b,c);
    System.out.println("tree = " + tree);
  }
}

14/09/2004, 19h59
iubito

Si je me plante pas, mon arbre n'est pas binaire !
Si mes souvenirs sont bons, un arbre binaire a un tronc, et 2 branches qui peuvent avoir chacune seulement 2 branches... l'une est appelée droite, et l'autre gauche.

Dans mon cas je peux avoir des branches multiples (0, 1, 2, ... n), exactement comme dans du XML (sauf que je ne traite pas un xml dans mon appli :P )

J'essayerai donc le Node de com.w3c ou l'autre... demain au boulot !
15/09/2004, 16h32
iubito

Je pense partir sur le org.w3c.dom.Node qui me semble plus pratique.
Mais comme c'est une interface, quelle implémentation utiliser ?
Parce que le compilo n'apprécie pas

Code:

Node N = new Node();
15/09/2004, 17h31
Debernad
En effet, c'est une bonne idée comme cela, si tu souhaite stocker ton arborescence de facon persistante, tu n'aura plus qu'à l'écrire en fichier XML qui est un standard que tu peux facilement réutiliser avec d'autres applications.

Pour l'implémentation, tu peux utiliser les classes du package "javax.xml.parsers"

Exemple :
Code:

1 2 3 4 DocumentBuilderFactory dbf = DocumentBuilderFactory.newInstance(); DocumentBuilder db = dbf.newDocumentBuilder(); Document root = db.newDocument();
la classe Document est une interface qui hérite de Node, donc c'est ton noeud racine qui posséde des méthodes createXXXX() pour créer différentes types de noeud.
A toi de voir quel type de noeud te convient le mieux.
Ensuite, lorsque tes noeuds sont créés, il te suffit de les imbriquer entre eux grâce au méthodes de Node.
16/09/2004, 09h15
iubito

euh... en partant de mon root, si je veux ajouter des noeuds, c'est root.appendChile(Node monNoeud)

donc à chaque fois que j'ajoute un nouveau noeud, c'est un db.newDocument() ?

Je n'ai aucune envie de sauvegarder mon bazar en XML, c'était juste pour montrer à c-top que je voulais pas du binaire ;)

Je te donne un exemple de comment je ferais, juste à titre indicatif ...
Cet exemple produit un fichier XML afin d'avoir un visuel du résultat et donc un visuel de ton arborescence ...
Mais dans ton code tu pourras supprimer la derniére partie qui fait appelle au transformer.

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
 
import org.w3c.dom.*;
import javax.xml.transform.*;
import javax.xml.transform.stream.*;
import javax.xml.transform.dom.*;
import javax.xml.parsers.*;
import java.io.*;
 
public class Test
{
	public static void main(String[] args) throws Exception
	{
		DocumentBuilderFactory dbf = DocumentBuilderFactory.newInstance(); 
		DocumentBuilder db = dbf.newDocumentBuilder(); 
		Document document = db.newDocument();
 
		Node racine = document.createElement("Dossier");
		document.appendChild(racine);
		Node dossier1 = ajoutDossier(racine,"101", "dossier 1");
		ajoutDossier(dossier1,"101/1", "dossier 1/1");
		Node dossier2 = ajoutDossier(racine,"102", "dossier 1");
		ajoutDossier(dossier2,"102/1", "dossier 2/1");
 
		TransformerFactory tf = TransformerFactory.newInstance();
		Transformer t = tf.newTransformer();
		t.transform(new DOMSource(document),new StreamResult(new File("toto.xml")));
	}
 
	public static Node ajoutDossier(Node parent,String cle, String text)
	{
		Element element = parent.getOwnerDocument().createElement("Dossier");
		element.setAttribute("cle",cle);
		element.setAttribute("text",text);
		parent.appendChild(element);
		return element;
	}
}

ce qui donne comme résultat, test.xml :

Code:

1
2
3
4
5
6
7
8
9
10
 
<?xml version="1.0" encoding="UTF-8"?>
<Racine>
	<Dossier cle="101" text="dossier 1">
		<Dossier cle="101/1" text="dossier 1/1"/>
	</Dossier>
	<Dossier cle="102" text="dossier 1">
		<Dossier cle="102/1" text="dossier 2/1"/>
	</Dossier>
</Racine>

16/09/2004, 10h21
iubito

Super :king: je vais essayer de me débrouiller avec ça :hola:
16/09/2004, 17h59
iubito

...j'ai rien dit...

Parcours de l'arbre...

Salut !
Avec un transformateur, j'arrive bien à obtenir un fichier XML très propre, c'est le pied ! Je vois que mon arbre est OK.

Maintenant je voudrais parcourir mon arbre :

J'ai donc une fonction "affichage" récursive qui parcours mon arbre, et affiche un truc tout bête, des tabulations, suivies de CLE puis de TEXTE.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 System.out.println(affichage(doc.getFirstChild(), 0)); private String affichage(Node N, int profondeur) { String ret = ""; Node fils; NamedNodeMap nnm; if (N != null) { if (N.hasChildNodes()) { fils = N.getFirstChild(); while (fils != null) { nnm = fils.getAttributes(); ret += "\n"; for (int i = 0; i <= profondeur; i++) ret += "\t"; ret += nnm.getNamedItem("cle") + " " + nnm.getNamedItem("texte"); ret += affichage(fils, profondeur + 1); fils = fils.getNextSibling(); } } } return ret; }
Le parcours est OK :) mais le problème est pour l'affichage de la valeur de CLE et de TEXTE à chaque noeud.
J'obtiens un résultat du type :
Code:

1 2 3 4 5 6 7 cle="500" texte="Boîte de réception" cle="100" texte="Dossier Annuel 31/12/2004" cle="100" texte="Compta" cle="100" texte="Etats Comptables" cle="105" texte="Factures d'achats" ...
Comment juste afficher 500 et Boîte de réception sans tout le tralala autour ?
je galère là-dessus, j'suis sûr que c'est tout con comparé à ce que je suis arrivé à faire, mais j'trouve pas :arf:

Je propose cela pour résoudre ton probléme :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
  private String affichage(Node N, int profondeur) { 
      String ret = ""; 
      Node fils; 
      if (N != null) { 
         if (N.hasChildNodes()) { 
            fils = N.getFirstChild(); 
            while (fils != null) { 
               ret += "\n"; 
               for (int i = 0; i <= profondeur; i++) 
                  ret += "\t"; 
               ret += ((Element)fils).getAttribute("cle") + " " + ((Element)fils).getAttribute("texte"); 
               ret += affichage(fils, profondeur + 1); 
               fils = fils.getNextSibling(); 
            } 
         } 
      } 
      return ret; 
   }

20/09/2004, 14h46
iubito

:hola::hola::hola:

MERCI ! :bravo: