ca569c287d1f2d2423a7a342d0ecb7ba335ca073
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
));
83 public void inserer(int value
) {
84 setRootNode(inserer_rec(rootNode
, value
));
87 private IntNode
supprimer_rec(IntNode currentNode
, int value
) {
88 if (currentNode
== null) {
90 } else if (value
== currentNode
.getData()) {
91 if (currentNode
.getLeftNode() == null && currentNode
.getRightNode() == null) {
93 } else if (currentNode
.getRightNode() == null) {
94 return currentNode
.getLeftNode();
95 } else if (currentNode
.getLeftNode() == null) {
96 return currentNode
.getRightNode();
98 int smallestValue
= findSmallestData(currentNode
.getRightNode());
99 currentNode
.setData(smallestValue
);
100 currentNode
.setRightNode(supprimer_rec(currentNode
.getRightNode(), smallestValue
));
103 } else if (value
< currentNode
.getData()) {
104 currentNode
.setLeftNode(supprimer_rec(currentNode
.getLeftNode(), value
));
106 currentNode
.setRightNode(supprimer_rec(currentNode
.getRightNode(), value
));
111 public void supprimer(int value
) {
112 supprimer_rec(rootNode
, value
);
115 private boolean hasDataRec(IntNode currentNode
, int value
) {
116 if (currentNode
== null) {
119 if (value
== currentNode
.getData()) {
122 return value
< currentNode
.getData() ?
hasDataRec(currentNode
.getLeftNode(), value
) : hasDataRec(currentNode
.getRightNode(), value
);
125 public boolean hasData(int value
) {
126 return hasDataRec(rootNote
, value
);
129 private int findSmallestData(IntNode node
) {
130 return node
.getLeftNode() == null ? node
.getData() : findSmallestData(node
.getLeftNode());
133 public afficher_rec(IntNode currentNode
) {
134 if (currentNode
.getLeftNode() != null) {
135 afficher_rec(currentNode
.getLeftNode());
136 } else if (currentNode
.getRightNode() != null) {
137 afficher_rec(currentNode
.getRightNode());
139 System
.out
.println("Valeur dans le noeud : ");
142 public static void main(String
[] args
) {
143 ArbreBinaire Btree
= new ArbreBinaire();
150 String Btreeout
= Btree
.toString();
151 System
.out
.println(Btreeout
);