Création d'arbre binaire en Java

Version imprimable

Bonjour à tous !

Je suis à la recherche d'une méthode pour demander à l'utilisateur de créer un arbre.

J'ai ma classe dans un fichier Arbre.java
Code:

1 2 3 4 5 6 7 8 9 10 public class Arbre { int racine; Arbre sag, sad; public Arbre(int x, Arbre g, Arbre d) { racine = x; sag = g; sad = d; } }
Je veux pouvoir écrire une fonction dans mon main (fichier main.java) ou dans mon fichier Arbre.java qui me permettrait de créer un Arbre de manière interactive.

Je ne veux donc pas :
Code:

1 2 3 public static void main (String[], args) { Arbre A = new Arbre(1, new Arbre(2, null, null), new Arbre(3, null, null)); }
par exemple..

Du coup je pensais utiliser une fonction du style :
Code:

1 2 3 4 5 6 7 8 9 10 11 public static Arbre creerArbre() { System.out.print("Feuille ? 1 oui 0 non "); int f = new Scanner(System.in).nextInt(); if (f == 0) { return null; } System.out.print("Racine : "); int rac = new Scanner(System.in).nextInt(); Arbre A = new Arbre(rac, creerArbre(), creerArbre()); return A; }
Mais le problème c'est que dans ce cas là, je ne peux pas savoir où je suis exactement dans l'arbre.

Je pense être sur la voie mais j'aimerais avoir un petit coup de main si jamais vous avez d'autres idées.

Merci d'avance !

Maxime

Bonjour,

Cela semble une bonne façon. Une idée pour savoir ou l'utilisateur est est en utilisant un "Breadcrumb". Par exemple:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
public static Arbre creerArbre(String contexte) {
    System.out.println(contexte);
    System.out.print("Feuille ? 1 oui 0 non ");
    int f = new Scanner(System.in).nextInt();
    if (f == 0) {
        return null;
    }
    System.out.print("Racine : ");
    int rac = new Scanner(System.in).nextInt();
    Arbre A = new Arbre(rac, creerArbre(contexte+" > "+rac+"G"), creerArbre(contexte+" > "+rac+"D"));
    return A;
}

27/11/2017, 10h45
hwoarang

Un arbre binaire est plutot compliqué à remplir à la main. Si tu restes sur cette idée, il faudra avoir un systeme hyper rigide qui permet de remplir l'arbre noeud après noeud.
Typiquement, tu peux faire une boucle ou tu demanderas un entier. Ensuite, tu crées une branche et tu l'ajoutes à gauche de la branche précédente. Tu continues cela jusqu'à la premiere entrée vide.
Lorsque l'utilisateur entre une valeur vide, tu passes sur la branche de droite de la derniere branche crée et tu refais ta boucle pour la peupler. Si la l'entrée est encore vide, la branche est une feuille et tu peux passer sur la branche de droite de la branche précédente.

Mais en général, pour ce genre de problématique, on lit plutot un fichier qui contient les infos dont on a besoin. Un fichier genre json est plutot adapté et te permettra de rentrer des arbres beaucoup plus simplement. En rentrant à la main, un simple arbre avec 10 branches est compliqué à remplir...

J'ai réussi à créer un arbre avec des valeurs saisies par l'utilisateur mais je me retrouve avec un arbre de type peigne (chaque noeud du sous-arbre gauche a une feuille en sous-arbre droit, même la racine).

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
    public static Arbre creerArbre() {
        Arbre A, root;
        int n, x;
        // Crée un peigne avec les valeurs
        System.out.print("Quel est le nombre de noeuds de votre arbre ? (racine + noeuds internes + feuilles) ");
        n = new Scanner(System.in).nextInt();
        System.out.print("Quelle est la valeur de la racine ? ");
        x = new Scanner(System.in).nextInt();
        n--;
        root = new Arbre(x, null, null);
        A = root;
        while (n > 0) {
            while ((A.sag == null || A.sad == null) && n > 0) {
                System.out.print("Valeur : ");
                x = new Scanner(System.in).nextInt();
                n--;
                if (A.sag != null) {
                    A.sad = new Arbre(x, null, null);
                }
                else {
                    A.sag = new Arbre(x, null, null);
                }
            }
            A = A.sag;
        }
        return root;
    }

J'ai vu avec mon prof, apparemment il y aurait une solution pour créer un arbre parfait en fonction des valeurs saisies mais je vois pas trop comment faire ça ... J'ai l'impression qu'il va y avoir énormément de tests à faire.

On n'utilise pas de fichier json, c'est pour un projet de cours uniquement en java :/

28/11/2017, 12h54
Mat.M

Citation:

Envoyé par Mastyxx

Je suis à la recherche d'une méthode pour demander à l'utilisateur de créer un arbre.

je ne voudrais pas faire du Hors-sujet (quoique...) mais tout dépend de la pertinence des données.
Un arbre binaire qu'est-ce que c'est ? C'est mettre en équation quelque part des noeuds conceptualisant des dilemmes/dichotomies bref des choix.
L'exemple "typique" d'utilisation d'arbre binaire c'est par exemple un système expert.
Par exemple pour déterminer une espèce animale on peut poser la question à l'utilisateur , la couleur, la taille, si c'est un mammifère ou oiseau etc....
donc oui on risque d'être contraint de remplir l'arbre à la main d'abord

Citation:

Envoyé par hwoarang

Un arbre binaire est plutot compliqué à remplir à la main

d'accord on peut remplir un arbre binaire on peut le faire de manière automatique.
Mais à partir de quel critère se fonde-t-on pour définir la dichotomie des données saisies en entrée et qui constituent l'arbre binaire ?

Citation:

Envoyé par hwoarang

Typiquement, tu peux faire une boucle ou tu demanderas un entier

quel intérêt de stocker dans chaque noeud de l'arbre binaire un entier ? Stocker un entier dans un arbre binaire c'est donc induire une dichotomie sous-jacente sur cet entier.
Or de quelle nature peut être cette dichotomie ? Supériorité ou infériorité ? Si c'est le cas une simple liste triée suffit , un arbre binaiire va compliquer les choses
28/11/2017, 13h11
provirus
Citation:

il y aurait une solution pour créer un arbre parfait en fonction des valeurs saisies

en fait, c'est encore plus simple comme ça :)

Il suffit de faire une boucle ainsi:
- demander un nombre à l'utilisateur
- si le noeud racine n'existe pas, le créer avec la valeur de l'utilisateur
- si le noeud racine existe, traverser l'arbre selon la valeur de l'utilisateur et l'insérer comme nouveau noeud enfant au bon endroit
Une façon simple de traverser l'arbre est en créant une méthode qui est récursive. Elle prend un noeud et la valeur de l'utilisateur. Ensuite, elle regarde si la valeur est déjà celle du noeud (dans ce cas, on ne fait rien), puis si elle irait à gauche ou à droite.
Si le sous-noeud n'existe pas, on le crée avec la valeur. Si le sous-noeud existe, on appelle cette meme méthode avec ce sous-noeud et la valeur en paramètres.

Amuses-toi bien
28/11/2017, 18h22
hwoarang

Citation:

Envoyé par Mat.M

d'accord on peut remplir un arbre binaire on peut le faire de manière automatique.
Mais à partir de quel critère se fonde-t-on pour définir la dichotomie des données saisies en entrée et qui constituent l'arbre binaire ?

Bah visiblement, il veut créer un arbre binaire. C'est un projet scolaire, je suis parti du principe qu'il voulait le peupler à la main et voir ce que ca donne (et ne pas avoir forcement un arbre classé pour voir ce que ca fait).

Citation:

Envoyé par Mat.M

quel intérêt de stocker dans chaque noeud de l'arbre binaire un entier ? Stocker un entier dans un arbre binaire c'est donc induire une dichotomie sous-jacente sur cet entier.

C'est le code original qui fait ca. Encore une fois, c'est un exercice scolaire, on ne cherche pas à faire un programme qui sert à quelque chose. Son arbre utilise des entiers, c'est comme ca.

Pour en revenir à la question originale, non, il ne suffit pas de remplir ton arbre de maniere recursive pour qu'il soit parfait (dans le pire ordre, tu te retrouves avec un arbre dont toutes les branches ont une et une seule branche, ce qui ruine completement l'interet de l'arbre binaire.
La solution est de demander à l'utilisateur des données, de les classer, puis de créer ton arbre binaire avec les données classées. De cette manière, tu obtiens un arbre parfait. Sinon, tu peux les ajouter au fur et à mesure mais ca implique de déplacer des branches, ce qui est plus compliqué.

Au passage, JSON n'est pas un langage de programmation mais un format de données (c'est equivalent à avoir un fichier texte dans lequel tu entres tes valeurs utilisateur les unes après les autres). Utiliser un fichier en entrée serait beaucoup plus simple pour toi pour tester ton programme. Lorsque tu auras fait le code, que tu testeras et que tu trouveras des bugs, ca éviterait de devoir retaper tes valeurs à chaque fois.
30/11/2017, 16h33
Mastyxx

Donc, ce qui serait plus simple serait de demander à l'utilisateur des valeurs, les enregistrer dans un tableau, puis à partir de ce tableau, créer un arbre binaire de recherche (beaucoup plus simple) ?

Parce qu'avec des valeurs quelconques, dans un arbre binaire qui n'est pas un ABR, je galère ...