X-Git-Url: https://git.piment-noir.org/?p=TP_POO.git;a=blobdiff_plain;f=Arbres%2FArbreBinaire.java;h=89fccc761ccfcfe98c352e1c027e9e5c25c00cb9;hp=836531272860dd88927bf4e84f1c848e62505fde;hb=ae33f914c6b8f939fcef9589c0f14bec2ba37e6b;hpb=d7dd93e3ad431005e39992df5a36bfa463641560

diff --git a/Arbres/ArbreBinaire.java b/Arbres/ArbreBinaire.java
index 8365312..89fccc7 100644
--- a/Arbres/ArbreBinaire.java
+++ b/Arbres/ArbreBinaire.java
@@ -1,77 +1,158 @@
 
 /**
  * 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 {
+    private Node<Integer> rootNode;
 
-    private class IntNode {
-        private int data;
-        private IntNode leftIntNode;
-        private IntNode rightIntNode;
+    ArbreBinaire() {
+        setRootNode(null);
+    }
 
-        IntNode(int value) {
-            setData(value);
-            setLeftNode(null);
-            setRightNode(null);
-        }
+    private void setRootNode(Node<Integer> node) {
+        rootNode = node;
+    }
 
-        IntNode(int value, IntNode leftNode, IntNode rightNode) {
-            setData(value);
-            setLeftNode(leftNode);
-            setRightNode(rightNode);
-        }
+    private Node<Integer> getRootNode() {
+        return rootNode;
+    }
 
-        private int getData() {
-            return data;
-        }
+    private boolean isEmpty() {
+        return (getRootNode() == null);
+    }
 
-        private void setData(int value) {
-            data = value;
+    private Node<Integer> inserer_rec(Node<Integer> currentNode, int value) {
+        if (currentNode == null) {
+            return new Node<Integer>(value);
         }
+        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;
+    }
 
-        private IntNode getLeftNode() {
-            return leftIntNode;
-        }
+    public void inserer(int value) {
+        setRootNode(inserer_rec(rootNode, value));
+    }
 
-        private void setLeftNode(IntNode leftNode) {
-            leftIntNode = leftNode;
+    private Node<Integer> supprimer_rec(Node<Integer> currentNode, int value) {
+        if (currentNode == null) {
+            return null;
         }
-
-        private IntNode getRightNode() {
-            return rightIntNode;
+        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;
+    }
 
-        private void setRightNode(IntNode rightNode) {
-            rightIntNode = rightNode;
+    public void supprimer(int value) {
+        supprimer_rec(rootNode, value);
+    }
+
+    private boolean hasDataRec(Node<Integer> 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 IntNode rootNode;
+    private int findSmallestData(Node<Integer> node) {
+        return node.getLeftNode() == null ? node.getData() : findSmallestData(node.getLeftNode());
+    }
 
-    ArbreBinaire() {
-        setRootNode(null);
+    private void afficher_rec(Node<Integer> currentNode) {
+        if (currentNode != null) {
+            afficher_rec(currentNode.getLeftNode());
+            System.out.print(currentNode.getData() + " ");
+            afficher_rec(currentNode.getRightNode());
+        }
     }
 
-    private void setRootNode(IntNode node) {
-        rootNode = node;
+    public void afficher() {
+        afficher_rec(rootNode);
+        System.out.println();
     }
 
-    private IntNode getRootNode() {
-        return rootNode;
+    private void afficher_arbre_rec(Node<Integer> 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);
+        }
     }
 
-    private boolean isEmpty() {
-        return (getRootNode() == null);
+    public void afficher_arbre() {
+        afficher_arbre_rec(rootNode, 1);
     }
 
-    public void inserer(int value) {
+    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);
 
-    public void supprimer(int value) {
+        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.inserer(8);
+        bTree.inserer(4);
 
+        bTree.afficher();
+        bTree.afficher_arbre();
     }
 
 }