TP2: cast double to int the compare method returned value.

[TP_POO.git] / Arbres / ArbreBinaire.java

diff --git a/Arbres/ArbreBinaire.java b/Arbres/ArbreBinaire.java
index ca569c287d1f2d2423a7a342d0ecb7ba335ca073..fc19203a7e4b9025a49e3628be08079abc12629e 100644 (file)
--- a/Arbres/ArbreBinaire.java
+++ b/Arbres/ArbreBinaire.java
@@ -1,7 +1,7 @@
 
 /**
  * Binary tree class.
 
 /**
  * Binary tree class.

- * A binary tree is a ordered value tree with only two childs by node
+ * A binary tree is a ordered value tree with only two childs per node

  */
 public class ArbreBinaire {
 
  */
 public class ArbreBinaire {
 


@@ -69,14 +69,12 @@ public class ArbreBinaire {
     private IntNode inserer_rec(IntNode currentNode, int value) {
         if (currentNode == null) {
             return new IntNode(value);
     private IntNode inserer_rec(IntNode currentNode, int value) {
         if (currentNode == null) {
             return new IntNode(value);

-        } else if (value < currentNode.getData()) {
+        }
+        if (value < currentNode.getData()) {

             currentNode.setLeftNode(inserer_rec(currentNode.getLeftNode(), value));
         } else if (value > currentNode.getData()) {
             currentNode.setRightNode(inserer_rec(currentNode.getRightNode(), value));
             currentNode.setLeftNode(inserer_rec(currentNode.getLeftNode(), value));
         } else if (value > currentNode.getData()) {
             currentNode.setRightNode(inserer_rec(currentNode.getRightNode(), value));

-        } else {
-            /* equality */
-            return currentNode;
-        }
+        } /* skip the equality case */

         return currentNode;
     }
 
         return currentNode;
     }
 


@@ -87,7 +85,8 @@ public class ArbreBinaire {
     private IntNode supprimer_rec(IntNode currentNode, int value) {
         if (currentNode == null) {
             return null;
     private IntNode supprimer_rec(IntNode currentNode, int value) {
         if (currentNode == null) {
             return null;

-        } else if (value == currentNode.getData()) {
+        }
+        if (value == currentNode.getData()) {

             if (currentNode.getLeftNode() == null && currentNode.getRightNode() == null) {
                 return null;
             } else if (currentNode.getRightNode() == null) {
             if (currentNode.getLeftNode() == null && currentNode.getRightNode() == null) {
                 return null;
             } else if (currentNode.getRightNode() == null) {


@@ -95,6 +94,12 @@ public class ArbreBinaire {
             } else if (currentNode.getLeftNode() == null) {
                 return currentNode.getRightNode();
             } else {
             } 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));
                 int smallestValue = findSmallestData(currentNode.getRightNode());
                 currentNode.setData(smallestValue);
                 currentNode.setRightNode(supprimer_rec(currentNode.getRightNode(), smallestValue));


@@ -123,33 +128,75 @@ public class ArbreBinaire {
     }
 
     public boolean hasData(int value) {
     }
 
     public boolean hasData(int value) {

-        return hasDataRec(rootNote, value);
+        return hasDataRec(rootNode, value);

     }
 
     private int findSmallestData(IntNode node) {
         return node.getLeftNode() == null ? node.getData() : findSmallestData(node.getLeftNode());
     }
 
     }
 
     private int findSmallestData(IntNode node) {
         return node.getLeftNode() == null ? node.getData() : findSmallestData(node.getLeftNode());
     }
 

-    public afficher_rec(IntNode currentNode) {
-        if (currentNode.getLeftNode() != null) {
+    private void afficher_rec(IntNode currentNode) {
+        if (currentNode != null) {

             afficher_rec(currentNode.getLeftNode());
             afficher_rec(currentNode.getLeftNode());

-        } else if (currentNode.getRightNode() != null) {
+            System.out.print(currentNode.getData() + " ");

             afficher_rec(currentNode.getRightNode());
         }
             afficher_rec(currentNode.getRightNode());
         }

-        System.out.println("Valeur dans le noeud : ");
+    }
+
+    public void afficher() {
+        afficher_rec(rootNode);
+        System.out.println();
+    }
+
+    private void afficher_arbre_rec(IntNode currentNode, int column) {
+        if (currentNode != null) {
+            afficher_arbre_rec(currentNode.getRightNode(), column + 1);
+            for (int 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) {
     }
 
     public static void main(String[] args) {

-        ArbreBinaire Btree = new ArbreBinaire();
+        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.inserer(5);
-        Btree.inserer(2);
-        Btree.inserer(7);
-        Btree.inserer(1);
+        bTree.afficher();
+        bTree.afficher_arbre();

 
 

-        String Btreeout = Btree.toString();
-        System.out.println(Btreeout);
+        bTree.inserer(2);
+        bTree.inserer(7);
+        bTree.inserer(3);
+        bTree.inserer(9);
+        bTree.inserer(11);
+        bTree.inserer(10);
+        bTree.inserer(8);
+        bTree.inserer(4);

 
 

+        bTree.afficher();
+        bTree.afficher_arbre();

     }
 
 }
     }
 
 }