Implémentation d'un arbre binaire en java [Résolu]

Signaler
Messages postés
26
Date d'inscription
dimanche 15 décembre 2019
Statut
Membre
Dernière intervention
16 septembre 2020
-
Messages postés
26
Date d'inscription
dimanche 15 décembre 2019
Statut
Membre
Dernière intervention
16 septembre 2020
-
Bonjour;
j'ai une matrice 2D qui est symétrique, je veux créer un arbre binaire, où chaque nœud représente l'indice de la colonne j,
la première étape je veux créer l'arbre de la première ligne. avec k=0 représente la racine.


j'ai créer le code suivant, mais il me semble qu'il ne fonctionne pas bien

package es_algo2;

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Arrays;

class Node
{
	int data;
	Node left;
	Node right;
	
}

class BST
{
	public Node createNode(int p)
	{
		Node a=new Node();
		a.data=p;
		System.out.println("k="+p);
		a.left=null;
		a.right=null;
		return a;
	}
	public Node insert (Node node, double[][] matrix, int j)
	{
		if(node==null)
			
		{
			return createNode(j);
		}
		
		if(matrix[0][j]==0)
		{
			node.left=insert(node.left,matrix, j);
		}
		
		else if (matrix[0][j]>0)
		{
			node.right=insert(node.right,matrix, j);
		}
		
		return node;
	}
}

public class ES_algo2 {

	
		public static void main(String[] args) throws IOException {
			double[][] matrix = Files.lines(Paths.get("matrice_sim2.csv"))
	                .map(line -> Arrays.stream(line.split(";"))
	                                   .mapToDouble(Double::parseDouble)
	                                   .toArray())
	                .toArray(double[][]::new);
			System.out.println(matrix[0][2]);
	        BST a=new BST();
			Node root=null;
			root=a.insert(root,matrix,0);

	}

}

4 réponses

Messages postés
16032
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
13 septembre 2020
2 672
Bonjour,

Je ne comprends pas dans ton image le lien entre ta matrice et ton arbre.
Est-ce que c'est censé être une matrice d'adjacence (ça n'y ressemble pas), où se trouve la symétrie dans la matrice ?
Quant à l'arbre, où se trouve la valeur 4 qui apparaît dans la matrice ?

Pour le code, la classe BST n'a aucun attribut, il serait sûrement pertinent qu'elle ait au moins un Node représentant la racine de l'arbre.
De plus je pense que la classe Node devrait être "cachée" et que les méthodes de BST n'y fasse référence ni dans les paramètres ni dans les résultats des méthodes.
Messages postés
26
Date d'inscription
dimanche 15 décembre 2019
Statut
Membre
Dernière intervention
16 septembre 2020

Bonjour;

la matrice est symétrique, c'est juste que j'ai rempli la partie inférieur par des zéros, parce que lors de la création de l'arbre j'utilise qu'une seul partie, inférieur ou supérieur.
j'ai besoin d'une aide dans la construction de l'arbre
Messages postés
16032
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
13 septembre 2020
2 672
Alors explique mieux comment fonctionne ta matrice, parce que je ne comprends pas à quoi correspondent ses valeurs, surtout vu l'arbre qui est donné en exemple.

Normalement, un arbre binaire représenté avec une matrice d'adjacence ne devrait pas avoir plus de deux valeurs par ligne (deux enfants maximum) et une valeur par colonne (un parent maximum).

Pour l'arbre de ton exemple, la matrice d'adjacence devrait être comme ceci :
  0 1 2 3
0 1 1
1 1
2
3
Ça n'a rien à voir avec la matrice de ton exemple.
Messages postés
26
Date d'inscription
dimanche 15 décembre 2019
Statut
Membre
Dernière intervention
16 septembre 2020

c'est vrai, je me suis trompé dans la matrice, j'ai modifié la matrice ainsi que l'arbre

Messages postés
16032
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
13 septembre 2020
2 672
Pour moi cette matrice ne correspond toujours à rien, d'autant que tu ne te sers que de la première ligne...

Voici un exemple d'arbre binaire :
public class Tree<D, E extends Comparable<E>> {
    private Node<D, E> root;

    public Tree(){
        root = null;
    }

    public void add(final D description, final E value) {
        if (root == null) {
            root = new Node<>(description, value);
        } else {
            root.add(description, value);
        }
    }

    @Override
    public String toString(){
        return String.valueOf(root);
    }

    private static class Node<D, V extends Comparable<V>> {
        private final D description;
        private final V value;
        private Node<D, V> left;
        private Node<D, V> right;

        public Node(final D description, final V value) {
            this.description = description;
            this.value = value;
            this.left = null;
            this.right = null;
        }

        public boolean add(final D newDescription, final V newValue) {
            final int direction = newValue.compareTo(value);
            if (direction < 0) {
                if (left == null) {
                    left = new Node<>(newDescription, newValue);
                    return true;
                } else {
                    return left.add(newDescription, newValue);
                }
            }
            if (direction > 0) {
                if (right == null) {
                    right = new Node<>(newDescription, newValue);
                    return true;
                } else {
                    return right.add(newDescription, newValue);
                }
            }
            return false;
        }

        @Override
        public String toString(){
            return (left == null ? "" : "{" + left + "} <- ") + "(" + description + "=" + value + ")" + (right == null ? "" : " -> {" + right + "}");
        }
    }
}

Si je reprends ton arbre d'exemple ça pourrait donner ce code de test :
public class Test {
    public static void main(final String[] args) {
        final Tree<String, Integer> tree = new Tree<>();
        tree.add("A", 3);
        tree.add("B", 4);
        tree.add("C", 1);
        tree.add("D", 2);
        System.out.println(tree);
    }
}

L'affichage donne
{(C=1) -> {(D=2)}} <- (A=3) -> {(B=4)}
(avec 1, 2, 3, et 4 dans l'ordre).
Ce qui correspond à ce schéma :
Messages postés
26
Date d'inscription
dimanche 15 décembre 2019
Statut
Membre
Dernière intervention
16 septembre 2020

Bonjour,
merci beaucoup KX pour ton aide, j'ai réussi à résoudre le problème.