return (getRootNode() == null);
}
+ private IntNode inserer_rec(IntNode currentNode, int value) {
+ if (currentNode == null) {
+ return new IntNode(value);
+ } else if (value < currentNode.getData()) {
+ currentNode.setLeftNode(inserer_rec(currentNode.getLeftNode(), value));
+ } else if (value > currentNode.getData()) {
+ currentNode.setRightNode(inserer_rec(currentNode.getRightNode(), value));
+ } /* skip the equality case */
+ return currentNode;
+ }
+
public void inserer(int value) {
+ setRootNode(inserer_rec(rootNode, value));
+ }
+ private IntNode supprimer_rec(IntNode currentNode, int value) {
+ if (currentNode == null) {
+ return null;
+ } else if (value == currentNode.getData()) {
+ if (currentNode.getLeftNode() == null && currentNode.getRightNode() == null) {
+ return null;
+ } else if (currentNode.getRightNode() == null) {
+ return currentNode.getLeftNode();
+ } else if (currentNode.getLeftNode() == null) {
+ return currentNode.getRightNode();
+ } else {
+ /*
+ * First, we need to find the node that will replace the deleted node.
+ * We’ll use the smallest node of the node to be deleted’s right sub-tree.
+ * Then, we assign the smallest value to the node to delete and after that,
+ * we’ll delete it from the right subtree.
+ */
+ int smallestValue = findSmallestData(currentNode.getRightNode());
+ currentNode.setData(smallestValue);
+ currentNode.setRightNode(supprimer_rec(currentNode.getRightNode(), smallestValue));
+ return currentNode;
+ }
+ } else if (value < currentNode.getData()) {
+ currentNode.setLeftNode(supprimer_rec(currentNode.getLeftNode(), value));
+ } else {
+ currentNode.setRightNode(supprimer_rec(currentNode.getRightNode(), value));
+ }
+ return currentNode;
}
public void supprimer(int value) {
+ supprimer_rec(rootNode, value);
+ }
+
+ private boolean hasDataRec(IntNode currentNode, int value) {
+ if (currentNode == null) {
+ return false;
+ }
+ if (value == currentNode.getData()) {
+ return true;
+ }
+ return value < currentNode.getData() ? hasDataRec(currentNode.getLeftNode(), value) : hasDataRec(currentNode.getRightNode(), value);
+ }
+
+ public boolean hasData(int value) {
+ return hasDataRec(rootNode, value);
+ }
+
+ private int findSmallestData(IntNode node) {
+ return node.getLeftNode() == null ? node.getData() : findSmallestData(node.getLeftNode());
+ }
+
+ private void afficher_rec(IntNode currentNode) {
+ if (currentNode != null) {
+ afficher_rec(currentNode.getLeftNode());
+ System.out.print(currentNode.getData() + " ");
+ afficher_rec(currentNode.getRightNode());
+ }
+ }
+
+ public void afficher() {
+ afficher_rec(rootNode);
+ System.out.println();
+ }
+
+ private void afficher_arbre_rec(IntNode currentNode, int column) {
+ int i;
+
+ if (currentNode != null) {
+ afficher_arbre_rec(currentNode.getRightNode(), column + 1);
+ for (i = 0; i < column; i++) {
+ System.out.print(" ");
+ }
+ System.out.println(currentNode.getData());
+ afficher_arbre_rec(currentNode.getLeftNode(), column + 1);
+ }
+ }
+
+ public void afficher_arbre() {
+ afficher_arbre_rec(rootNode, 1);
+ }
+
+ public static void main(String[] args) {
+ ArbreBinaire bTree = new ArbreBinaire();
+
+ bTree.inserer(2);
+ bTree.inserer(6);
+ bTree.inserer(4);
+ bTree.inserer(5);
+ bTree.inserer(1);
+ bTree.inserer(0);
+
+ bTree.afficher();
+ bTree.afficher_arbre();
+
+ bTree.supprimer(4);
+
+ bTree.afficher();
+ bTree.afficher_arbre();
+
+ bTree.supprimer(6);
+
+ bTree.afficher();
+ bTree.afficher_arbre();
+
+ bTree.inserer(2);
+ bTree.inserer(7);
+ bTree.inserer(3);
+ bTree.inserer(9);
+ bTree.inserer(11);
+ bTree.inserer(10);
+ bTree.afficher();
+ bTree.afficher_arbre();
}
}