4 * A binary tree is a ordered value tree with only two childs per node
6 public class ArbreBinaire
{
8 private class IntNode
{
10 private IntNode leftIntNode
;
11 private IntNode rightIntNode
;
19 IntNode(int value
, IntNode leftNode
, IntNode rightNode
) {
21 setLeftNode(leftNode
);
22 setRightNode(rightNode
);
25 private int getData() {
29 private void setData(int value
) {
33 private IntNode
getLeftNode() {
37 private void setLeftNode(IntNode leftNode
) {
38 leftIntNode
= leftNode
;
41 private IntNode
getRightNode() {
45 private void setRightNode(IntNode rightNode
) {
46 rightIntNode
= rightNode
;
51 private IntNode rootNode
;
57 private void setRootNode(IntNode node
) {
61 private IntNode
getRootNode() {
65 private boolean isEmpty() {
66 return (getRootNode() == null);
69 private IntNode
inserer_rec(IntNode currentNode
, int value
) {
70 if (currentNode
== null) {
71 return new IntNode(value
);
73 if (value
< currentNode
.getData()) {
74 currentNode
.setLeftNode(inserer_rec(currentNode
.getLeftNode(), value
));
75 } else if (value
> currentNode
.getData()) {
76 currentNode
.setRightNode(inserer_rec(currentNode
.getRightNode(), value
));
77 } /* skip the equality case */
81 public void inserer(int value
) {
82 setRootNode(inserer_rec(rootNode
, value
));
85 private IntNode
supprimer_rec(IntNode currentNode
, int value
) {
86 if (currentNode
== null) {
89 if (value
== currentNode
.getData()) {
90 if (currentNode
.getLeftNode() == null && currentNode
.getRightNode() == null) {
92 } else if (currentNode
.getRightNode() == null) {
93 return currentNode
.getLeftNode();
94 } else if (currentNode
.getLeftNode() == null) {
95 return currentNode
.getRightNode();
98 * First, we need to find the node that will replace the deleted node.
99 * We’ll use the smallest node of the node to be deleted’s right sub-tree.
100 * Then, we assign the smallest value to the node to delete and after that,
101 * we’ll delete it from the right subtree.
103 int smallestValue
= findSmallestData(currentNode
.getRightNode());
104 currentNode
.setData(smallestValue
);
105 currentNode
.setRightNode(supprimer_rec(currentNode
.getRightNode(), smallestValue
));
108 } else if (value
< currentNode
.getData()) {
109 currentNode
.setLeftNode(supprimer_rec(currentNode
.getLeftNode(), value
));
111 currentNode
.setRightNode(supprimer_rec(currentNode
.getRightNode(), value
));
116 public void supprimer(int value
) {
117 supprimer_rec(rootNode
, value
);
120 private boolean hasDataRec(IntNode currentNode
, int value
) {
121 if (currentNode
== null) {
124 if (value
== currentNode
.getData()) {
127 return value
< currentNode
.getData() ?
hasDataRec(currentNode
.getLeftNode(), value
) : hasDataRec(currentNode
.getRightNode(), value
);
130 public boolean hasData(int value
) {
131 return hasDataRec(rootNode
, value
);
134 private int findSmallestData(IntNode node
) {
135 return node
.getLeftNode() == null ? node
.getData() : findSmallestData(node
.getLeftNode());
138 private void afficher_rec(IntNode currentNode
) {
139 if (currentNode
!= null) {
140 afficher_rec(currentNode
.getLeftNode());
141 System
.out
.print(currentNode
.getData() + " ");
142 afficher_rec(currentNode
.getRightNode());
146 public void afficher() {
147 afficher_rec(rootNode
);
148 System
.out
.println();
151 private void afficher_arbre_rec(IntNode currentNode
, int column
) {
152 if (currentNode
!= null) {
153 afficher_arbre_rec(currentNode
.getRightNode(), column
+ 1);
154 for (int i
= 0; i
< column
; i
++) {
155 System
.out
.print(" ");
157 System
.out
.println(currentNode
.getData());
158 afficher_arbre_rec(currentNode
.getLeftNode(), column
+ 1);
162 public void afficher_arbre() {
163 afficher_arbre_rec(rootNode
, 1);
166 public static void main(String
[] args
) {
167 ArbreBinaire bTree
= new ArbreBinaire();
177 bTree
.afficher_arbre();
182 bTree
.afficher_arbre();
187 bTree
.afficher_arbre();
199 bTree
.afficher_arbre();