89fccc761ccfcfe98c352e1c027e9e5c25c00cb9
4 * A binary tree is a ordered value tree with only two childs per node
6 public class ArbreBinaire
{
7 private Node
<Integer
> rootNode
;
13 private void setRootNode(Node
<Integer
> node
) {
17 private Node
<Integer
> getRootNode() {
21 private boolean isEmpty() {
22 return (getRootNode() == null);
25 private Node
<Integer
> inserer_rec(Node
<Integer
> currentNode
, int value
) {
26 if (currentNode
== null) {
27 return new Node
<Integer
>(value
);
29 if (value
< currentNode
.getData()) {
30 currentNode
.setLeftNode(inserer_rec(currentNode
.getLeftNode(), value
));
31 } else if (value
> currentNode
.getData()) {
32 currentNode
.setRightNode(inserer_rec(currentNode
.getRightNode(), value
));
33 } /* skip the equality case */
37 public void inserer(int value
) {
38 setRootNode(inserer_rec(rootNode
, value
));
41 private Node
<Integer
> supprimer_rec(Node
<Integer
> currentNode
, int value
) {
42 if (currentNode
== null) {
45 if (value
== currentNode
.getData()) {
46 if (currentNode
.getLeftNode() == null && currentNode
.getRightNode() == null) {
48 } else if (currentNode
.getRightNode() == null) {
49 return currentNode
.getLeftNode();
50 } else if (currentNode
.getLeftNode() == null) {
51 return currentNode
.getRightNode();
54 * First, we need to find the node that will replace the deleted node.
55 * We’ll use the smallest node of the node to be deleted’s right sub-tree.
56 * Then, we assign the smallest value to the node to delete and after that,
57 * we’ll delete it from the right subtree.
59 int smallestValue
= findSmallestData(currentNode
.getRightNode());
60 currentNode
.setData(smallestValue
);
61 currentNode
.setRightNode(supprimer_rec(currentNode
.getRightNode(), smallestValue
));
64 } else if (value
< currentNode
.getData()) {
65 currentNode
.setLeftNode(supprimer_rec(currentNode
.getLeftNode(), value
));
67 currentNode
.setRightNode(supprimer_rec(currentNode
.getRightNode(), value
));
72 public void supprimer(int value
) {
73 supprimer_rec(rootNode
, value
);
76 private boolean hasDataRec(Node
<Integer
> currentNode
, int value
) {
77 if (currentNode
== null) {
80 if (value
== currentNode
.getData()) {
83 return value
< currentNode
.getData() ?
hasDataRec(currentNode
.getLeftNode(), value
) : hasDataRec(currentNode
.getRightNode(), value
);
86 public boolean hasData(int value
) {
87 return hasDataRec(rootNode
, value
);
90 private int findSmallestData(Node
<Integer
> node
) {
91 return node
.getLeftNode() == null ? node
.getData() : findSmallestData(node
.getLeftNode());
94 private void afficher_rec(Node
<Integer
> currentNode
) {
95 if (currentNode
!= null) {
96 afficher_rec(currentNode
.getLeftNode());
97 System
.out
.print(currentNode
.getData() + " ");
98 afficher_rec(currentNode
.getRightNode());
102 public void afficher() {
103 afficher_rec(rootNode
);
104 System
.out
.println();
107 private void afficher_arbre_rec(Node
<Integer
> currentNode
, int column
) {
108 if (currentNode
!= null) {
109 afficher_arbre_rec(currentNode
.getRightNode(), column
+ 1);
110 for (int i
= 0; i
< column
; i
++) {
111 System
.out
.print(" ");
113 System
.out
.println(currentNode
.getData());
114 afficher_arbre_rec(currentNode
.getLeftNode(), column
+ 1);
118 public void afficher_arbre() {
119 afficher_arbre_rec(rootNode
, 1);
122 public static void main(String
[] args
) {
123 ArbreBinaire bTree
= new ArbreBinaire();
133 bTree
.afficher_arbre();
138 bTree
.afficher_arbre();
143 bTree
.afficher_arbre();
155 bTree
.afficher_arbre();