Arbre Fermé

Question

Bonjour, 
J'ai construit un arbre de la façon suivante.
Chaque objet a comme attribue deux objets de cette même classe (ie. deux branches), sauf  ceux en bas qu'on peut appeler les feuilles qui n'ont pas de descendants. Je n'ai accès directement qu'à la racine (celui qui n'a pas de parents).

Je voudrais maintenant coder mon arbre en binaire de manière à ce que chaque feuille ait un code binaire correspondant au chemin parcouru.

Illustration simple
-------------------------racine-----------------------
------------------/-----------------------\------------
-------parentDe1&2--------------------\----------
------/----------------\----------------------\---------
objet1------------objet2--------------objet3------

J'ai accès à racine. Je sais que son leftChild est parentDe1&2 et son rightChild est objet3 (ce son ses attributs). De même je ais que le leftChild du leftChild de racine est objet 1 etc...
Je voudrais donc avoir par exemple le code binaire '00' pour objet 1, '01' pour objet 2 et '1' pour objet3.

Je n'arrive pas à donner ses valeurs aux objets. Je pense que c'est une histoire de récurrence mais je tourne en rond depuis un moment.
Pouvez-vous m'aider ? merci

KX · Answer

Si tu as "01" pour objet 2, et "1" pour objet 3, tu auras le même code binaire pour deux feuilles différentes ce n'est pas logique. De plus pourquoi numéroter seulement les feuilles ? Il serait plus logique de numéroter tous les noeuds !

        1        
      /   \      
   10       11   
  /  \     /  \  
100  101 110  111

public static void setBinaries(Tree t)
{
    if (t.father==null)
        setBinaries(t,"1");
    else
        setBinaries(t.father);
}

private static void setBinaries(Tree t,String s)
{
    if (t!=null)
    {
        t.binaryValue = s;
        setBinaries(t.leftChild,s+"0");
        setBinaries(t.rightChild,s+"1");
    }
}

ghhha · Answer

wooo j'ai passé plusieurs heures à essayer de trouver cette opération récursive (presque élémentaire) mais je ne sais pas pourquoi ça ne venait pas ! Je viens de l'implémenter dans mon code et ça marche ! super ! et dire que j'étais en train de faire ça par des opération non récursive 100 fois plus compliqués^^

merci beaucoup !!


remarque : sisi je veux 01 pour un objet et 1 pour l'autre objet : c'est dans l'optique de faire le codage Huffman en fait ;)

Arbre

2 réponses

Discussions similaires