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);
}
}
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.
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
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.
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 :
