Comment insérer des objets dans un arbre binaire complet

bonjour KX,
merci pour votre réponse, j'ai essayé d'appliquer votre méthode mais je sais pas comment (elle est un peu compliqué).
j'étais conseillé de faire toujours l'insertion à gauche pour ce type d'arbre, alors je me trouve non obligé de faire la comparaison.
voila mon code :

public void ajout(E o, Noeud b)
 {
     Noeud n=new Noeud(o,null,null);
     if(b==null)
         b=n;
     else
     {
         if(b.filsG==null)
            b.filsG=n;
         else
         {
            if(b.filsD==null && b.filsG!=null)
               b.filsD=n;
           else
             ajout(o,racine.filsG);
     }}
}

mais dans ce cas je dois coder une fonction pour tester que chaque niveau (partie gauche et partie droite) est plein

Bonsoir,

     if(b==null)
         b=n;

Tu ne peux pas modifier b dans une méthode, la modification ne sera pas répercutée dans l'appel de la méthode. Genre si tu fais ajout(x,null) ou ajout(x,y) avec y==null, il est impossible que y (donc null) soit modifié pour prendre la valeur de n.

Remarque : les modifications interne à l'objet (b.filsG et b.filsD) seront conservées, mais pas les modifications directes sur b.

bonsoir :) ,
merci beaucoup pour votre remarque,
j'ai donc remplacé le b par la racine de l'arbre :

if(this.racine==null)
         this.racine=n;

et ça marche bien ;) mercii

C'est beaucoup trop compliqué pour que ça fonctionne !

J'ai l'impression que tu ne te sers que des null pour te diriger alors effectivement ton premier code gère 2 niveaux donc il n'y a plus de null après 3 éléments, ton deuxième code gère 3 niveaux donc il n'y a plus de null après 7 éléments, et si tu prenais en compte "n" niveaux tu pourrais remplir jusqu'à 2^n-1 valeurs avant de remplir tous les null par des valeurs...

Je n'ai pas testé, mais je dirais que de la manière dont tu l'as fait, ton arbre binaire n'est pas un arbre, c'est à dire que les valeurs s'ajoutent les unes après les autres, mais l'ordre des éléments dépend de leur ordre d'insertion, pas de leur valeur... En effet, à quel moment est-ce que tu compares les éléments pour savoir si tu vas à droite ou à gauche ?

Vite fait parce qu'il est tard, une classe arbre (la plus simple possible) devrait être quelque chose comme ceci :

public class Tree<E extends Comparable<E>>
{
    private E node = null;
    private Tree<E> left = null;
    private Tree<E> right = null;
    
    public Tree()
    {
    }
    
    public boolean add(E value)
    {
        if (value == null)
            throw new IllegalArgumentException("null can't be add to tree");
        
        if (node == null)
        {
            node = value;
            return true;
        }
        else
        {
            int comp = value.compareTo(node);
            
            if (comp == 0)
                return false;
            
            if (comp < 0)
            {
                if (left == null)
                    left = new Tree<E>();
                
                return left.add(value);
            }
            else
            {
                if (right == null)
                    right = new Tree<E>();
                
                return right.add(value);
            }
        }
    }
    
    public String toString()
    {
        if (node==null)
            return "";
        
        String str = node.toString();
        
        if (left != null)
            str = left.toString() + ", " + str;
        
        if (right != null)
            str = str + ", " + right.toString();
        
        return str;
    }
    
    public static void main(String[] args)
    {
        Tree<String> tree = new Tree<String>();
        tree.add("toto");
        tree.add("tata");
        tree.add("titi");
        tree.add("tata");
        tree.add("tutu");
        System.out.println(tree); // tata, titi, toto, tutu
    }
}

Bonjour, merci beaucoup KX pour votre réponse,
<< à quel moment est-ce que tu compares les éléments pour savoir si tu vas à droite ou à gauche ?>>
le principe est que je dois remplir complètement chaque niveau de gauche à droite avant de passer au niveau plus bas. je ne peux pas pas faire la comparaison entre gauche et droite parce que j'ai un arbre d'objets (les noeuds sont des instances de classe), donc j'ai pas un critère bien déterminé pour les comparer. c'est pourquoi je trouve que mon travail est trééés compliqué :(.
je vais essayé avec votre solution.

"je dois remplir complètement chaque niveau de gauche à droite avant de passer au niveau plus bas"
Cela signifie que tu devras équilibrer ton arbre, mais les éléments doivent quand même être triés sinon l'arbre n'a aucun intérêt !

j'ai pensé que le faite de trier les élément de mon arbre n'est pas nécessaire puisque je suis entrain de coder un arbre de façon générale.
je vais suivre, alors, votre proposition.
merci beaucoup :)

Un arbre, par définition, est trié. C'est lié à la recherche par dichotomie.
Le but est de pouvoir se diriger dans l'arbre en comparant les noeuds en fonction de leur valeur, et ainsi pouvoir à chaque comparaison éliminer toute une sous-partie de l'arbre.
Si tes éléments ne sont pas triés tu ne pourras pas rechercher une valeur particulière autrement qu'en parcourant l'intégralité de l'arbre, cela n'a donc aucun intérêt, pour faire ça une liste suffirait.