8f79d28c48379d5f5aafab9d322f14b8a166b713
4 * A binary tree is a ordered value tree with only two childs by 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
);
72 } else if (value
< currentNode
.getData()) {
73 currentNode
.setLeftNode(inserer_rec(currentNode
.getLeftNode(), value
));
74 } else if (value
> currentNode
.getData()) {
75 currentNode
.setRightNode(inserer_rec(currentNode
.getRightNode(), value
));
76 } /* skip the equality case */
80 public void inserer(int value
) {
81 setRootNode(inserer_rec(rootNode
, value
));
84 private IntNode
supprimer_rec(IntNode currentNode
, int value
) {
85 if (currentNode
== null) {
87 } else if (value
== currentNode
.getData()) {
88 if (currentNode
.getLeftNode() == null && currentNode
.getRightNode() == null) {
90 } else if (currentNode
.getRightNode() == null) {
91 return currentNode
.getLeftNode();
92 } else if (currentNode
.getLeftNode() == null) {
93 return currentNode
.getRightNode();
96 * First, we need to find the node that will replace the deleted node.
97 * We’ll use the smallest node of the node to be deleted’s right sub-tree.
98 * Then, we assign the smallest value to the node to delete and after that,
99 * we’ll delete it from the right subtree.
101 int smallestValue
= findSmallestData(currentNode
.getRightNode());
102 currentNode
.setData(smallestValue
);
103 currentNode
.setRightNode(supprimer_rec(currentNode
.getRightNode(), smallestValue
));
106 } else if (value
< currentNode
.getData()) {
107 currentNode
.setLeftNode(supprimer_rec(currentNode
.getLeftNode(), value
));
109 currentNode
.setRightNode(supprimer_rec(currentNode
.getRightNode(), value
));
114 public void supprimer(int value
) {
115 supprimer_rec(rootNode
, value
);
118 private boolean hasDataRec(IntNode currentNode
, int value
) {
119 if (currentNode
== null) {
122 if (value
== currentNode
.getData()) {
125 return value
< currentNode
.getData() ?
hasDataRec(currentNode
.getLeftNode(), value
) : hasDataRec(currentNode
.getRightNode(), value
);
128 public boolean hasData(int value
) {
129 return hasDataRec(rootNode
, value
);
132 private int findSmallestData(IntNode node
) {
133 return node
.getLeftNode() == null ? node
.getData() : findSmallestData(node
.getLeftNode());
136 private void afficher_rec(IntNode currentNode
) {
137 if (currentNode
!= null) {
138 afficher_rec(currentNode
.getLeftNode());
139 System
.out
.print(currentNode
.getData() + " ");
140 afficher_rec(currentNode
.getRightNode());
144 public void afficher() {
145 afficher_rec(rootNode
);
146 System
.out
.println();
149 private void afficher_arbre_rec(IntNode currentNode
, int column
) {
152 if (currentNode
!= null) {
153 afficher_arbre_rec(currentNode
.getRightNode(), column
+ 1);
154 for (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();
197 Btree
.afficher_arbre();