Conception d'un arbre binaire générique
Salut à tous,
Je suis en train de réaliser un programme sur les arbres binaires génériques ... et je coince sur la réalisation d'une méthode. Voici ce que je voudrais faire :
Citation:
Un objet de type NoeudInterne doit être crée à partir de deux objets de type Feuille. La méthode ajoute(Feuille) de la classe NoeudInterne porte une valeur booléenne ajoutAGauche qui dicte la manière dont on ajoute une feuille dans un sous-arbre.
Si la valeur est vrai, la feuille est ajoutée dans le sous-arbre du fils gauche , si sa valeur est faux on l'ajoute dans le sous-arbre du fils droit.
Une fois le fils choisi, on procède de la façon suivante :
- si le fils est une feuille, un nœud interne est crée à partir de l'ancienne feuille et de la nouvelle;
- sinon, on utilise la méthode ajoute(Feuille) du fils.
Voici la conception des classes :
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
package eu.princeton.binarytree.src.main.java.eu.princeton;
/**
* Bi-Tree is a classic data structure with nodes compounded
* A node is an internal node or a leaf
*
* @param <T> represents the type of the object in the Bi-Tree
*/
public final class BinaryTree<T> {
private Node<T> root;
private BinaryTree<T> leftSubBiTree, rightSubBiTree;
private T value;
public BinaryTree(T value, BinaryTree<T> left, BinaryTree<T> right) {
this.value = value;
this.leftSubBiTree = left;
this.rightSubBiTree = right;
}
public BinaryTree(BinaryTree<T> left, BinaryTree<T> right) {
this.leftSubBiTree = left;
this.rightSubBiTree = right;
}
public BinaryTree(T value, InnerNode<T> rootNode) { // <? extends Node<T>>
this.root = rootNode;
this.value = value;
}
public BinaryTree(InnerNode<T> rootNode) {
this.root = rootNode;
}
/**
* This method display the BinaryTree's structure so the number of branches in the BinaryTree
* 27
* / \ -------- level : 1
* 14 35
* / \ / \ -------- level : 2
* 10 9 31 42
* / / \ -------- level : 4
* 5 3 1 ..... etc
* -------- level : x<=8
* @param nbLevel represents the number of levels of the BinaryTree
* @return the list of all items between the root and the n level
*/
public String display(int nbLevel) {
return "";
}
/**
* This method allow to display the item list by a right-left descending browsing
* We browse at first the left child, so the right child of the Bi-Tree
*
* @return the display of the list of items in the Bi-Tree
*/
@Override
public String toString() {
return "";
}
} |
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
|
package eu.princeton.binarytree.src.main.java.eu.princeton;
/**
* Node abstract is a generic class will allow us to access to child node of the BinaryTree
*
* @param <T> represents the type of the object in the Bi-Tree
*/
public abstract class Node<T> { // T is the generic type int, double, float, String, etc ...
protected T value;
protected Node<T> leftChild;
protected Node<T> rightChild;
/**
* This method tests whether this node is a leaf node.
*
* @return if this BinaryTree node has no children.
*/
protected abstract boolean isLeaf();
protected abstract String display(int depth);
protected String display() {
return "Node";
}
} |
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
28
29
30
31
32
33
34
35
36
37
|
package eu.princeton.binarytree.src.main.java.eu.princeton;
/**
* A leaf is the final termination of a Bi-Tree data structure
* A leaf hasn't got any children
*
* @param <T> represents the type of the object in the Bi-Tree
*/
public final class Leaf<T> extends Node {
private T value;
public Leaf(T value) {
this.value = value;
}
public T getValue() {
return value;
}
@Override
protected boolean isLeaf() {
return (this.leftChild == null && this.rightChild == null);
}
@Override
protected String display(int depth) {
return "";
}
@Override
public String toString() {
return "Leaf's value : " + value;
}
} |
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
package eu.princeton.binarytree.src.main.java.eu.princeton;
import java.util.LinkedList;
/**
* An innerNode is a node who have a left son and a right son which are nodes themselves
*
* @param <T> represents the type of the object in the BinaryTree
*/
public final class InnerNode<T> extends Node {
private boolean addLeftSide;
private LinkedList<T> children = null;
public InnerNode(boolean addLeftSide, Leaf<T> firstLeaf, Leaf<T> secondLeaf) {
this.addLeftSide = addLeftSide;
this.leftChild = firstLeaf;
this.rightChild = secondLeaf;
children = new LinkedList<>();
}
public InnerNode(Leaf<T> left, Leaf<T> right) {
this.leftChild = left;
this.rightChild = right;
children = new LinkedList<>();
}
public Node<T> getLeftChild() {
return super.leftChild;
}
public Node<T> getRightChild() {
return super.rightChild;
}
/**
* This method allow us to add a leaf to the subtree
*
* @param aLeaf a node without children (left or right)
*/
private final void add(Leaf<T> aLeaf) {
if(this.addLeftSide == true) {
if (this.getLeftChild().isLeaf()) {
} else {
}
}
}
@Override
protected boolean isLeaf() {
return (this.leftChild == null && this.rightChild == null);
}
@Override
protected String display(int depth) {
return "";
}
@Override
public String toString() {
return "Add a leaf in the subtree : " + addLeftSide;
}
} |
J'aurai besoin de quelques éclaircissements sur ma conception.
Merci par avance.
Transact.
