Bonjour,

J'essaie d'implémenter un arbre binaire générique afin de comprendre l'utilisation de la généricité en Java. 

Dans le code, on retrouvera la classe GenericTree

package code;

public class GenericTree<T extends Comparable<T>> {

	//Fields
	private T value;
	private GenericTree<T> leftSon;
	private GenericTree<T> rightSon;
	
	//Constructors
	public GenericTree(){};
	
	public GenericTree(T element, GenericTree<T> leftSon, GenericTree<T> rightSon){
		this.value = element;
		this.leftSon = leftSon;
		this.rightSon = rightSon;
	}
	
	//Get & set methods
	
	public T getValue() {
		return value;
	}

	public void setValue(T value) {
		this.value = value;
	}

	public GenericTree<T> getLeftSon() {
		return leftSon;
	}

	public void setLeftSon(GenericTree<T> leftSon) {
		this.leftSon = leftSon;
	}

	public GenericTree<T> getRightSon() {
		return rightSon;
	}

	public void setRightSon(GenericTree<T> rightSon) {
		this.rightSon = rightSon;
	}
	
	//methods
	public void add(GenericTree<T> node){
		if(this == null){
			this.value = node.value;
			this.leftSon = node.leftSon;
			this.rightSon = node.rightSon;
		}
		else if(node.value.compareTo(this.value) <0){
			this.leftSon.add(node);
		}
		else{
			this.rightSon.add(node);
		}	
	}

	public void delete(T element){
		if(element.compareTo(this.value) == 0){
			this.leftSon = this;
		}
		else{
			if(element.compareTo(this.value)<0){
				this.leftSon.delete(element);
			}
			else{
				this.rightSon.delete(element);
			}
		}
	}	
	
}

On a donc: 

• Un élément "T" comparable puisqu'il hérite de la classe "Comparable"
• Des Getters et des Setters
• Une méthode d'ajout et de suppression de noeuds dans l'arbre.

Concernant l'ajout, Il y a trois cas

• L'arbre pointe sur null ? on ajoute les champs du noeuds à ceux de l'arbre
• Le contenu du noeud que l'on ajoute est inférieur à celui de l'arbre ? On appelle la fonction sur le fils gauche
• On appelle sur le fils droit si le contenu est supérieur.

Cependant, lors des test unitaires sur la fonction "add" , il y a des erreurs au niveau la fonction "CompareTo"

Voici l'implémentation du test unitaire:

package tests;

import static org.junit.Assert.*;

import org.junit.Test;

import code.GenericTree;

public class TreeTests {

	@Test
	public void test() {
		Integer j = new Integer(5);
		GenericTree<Integer> GTree = new GenericTree<Integer>();
		GTree.add(new GenericTree<Integer>(j, null, null));
		j = 4;
		GTree.add(new GenericTree<Integer>(j,null,null));
		assertEquals(GTree.getLeftSon().getValue(), new Integer(4));
	}

}

Et les erreurs retournées:

En remerciant d'avance ceux qui m'aideront

this == null est impossible. Si tu es dans un objet, il est forcément non null. Je suppose que tu voulais plutôt tester si this.value == null.

Dans delete, tu as aussi oublié de traiter le cas value == null, c à d si l'élément n'est pas dans l'arbre.

Deux dernières remarques.

Ajouter des setters tue complètement ton implémentation car tu ne respectes plus les invariants de ta classe, à savoir que les objets que tu mets dedans sont triés. Exemple : tu as un gros arbre plein de nombres positifs et tout à coup, tu fais racine.setValue(-10). BADABOUM ! C'est fichu.

Idem pour tes get...Son car ton type arbre est mutable (c à d qu'on peut le modifier).

Deuxième remarque, il est plus logique d'ajouter un élément à l'arbre plutôt qu'un autre arbre (comme tu l'as fait pour delete). Ou alors, si tu veux ajouter un arbre à un autre, il faut ajouter ses valeurs une à une, pas l'arbre en bloc.

a =
   3
  / \
 1   5

b =
   4
  / \
 0   6

Exemple : Si tu fais a.add(b), tu le mets où b ? Ca ne marche pas.

-
Edité par brubru777 14 mars 2015 à 15:43:57

Je vois la chose, merci bien, j'ai pu modifier mon code add désormais, il fonctionne à moitié 

L'ajout à gauche se fait très bien mais pas l'ajout à droite. 

public void add(T element){
		if(this.value == null){
			this.value = element;
		}
		else {
			GenericTree<T> GTree = new GenericTree<T>();
			GTree.value = element;
			if(element.compareTo(this.value)<0){
				if(this.leftSon == null){
					this.leftSon = GTree;
				}
				else{
					this.leftSon.add(element);
				}
			}
			else if (element.compareTo(this.value)>0){
				if (this.rightSon == null) {
					GTree.rightSon = GTree;
				} 
				else {
					this.rightSon.add(element);
				}
			}
		}	
	}

Et c'est vrai j'ai fait une bourde pour les get set mais je peux plus réaliser de test unitaires si je les enlève 

Tu as mis GTree.rightSon au lieu de this.rightSon.

Sinon, c'est mieux de créer gtree à l'endroit où tu l'ajoutes. Sinon, tu crées un tas d'arbres inutilisés proportionnel à la profondeur de ton élément.

En fait il faut voir la POO de 2 points de vue :
- le point de vue utilisation, où tu n'auras en publique que : add, delete et le constructeur VIDE.
- le point de vue implémentation, où tu pourras avoir en privé : des getters, le constructeur avec les 3 valeurs du noeud (ou setter).

Lors de la suppression tu devras remanier tes branches, donc surement jouer avec les setters.
Comme ce remaniement a lieu en interne, les setters doivent donc être privés.
Je dirai même plus : tu peux directement attaquer les attributs sans passer par les setters.

Merci pour votre aide !

En effet, je vais plutôt créer de Gtree au moment de l'ajout, ça me paraît plus propre