Arbres/ArbreBinaire.java

   1
   2 /**
   3  * Binary tree class.
   4  * A binary tree is a ordered value tree with only two childs per node
   5  */
   6 public class ArbreBinaire {
   7     private Node<Integer> rootNode;
   8
   9     ArbreBinaire() {
  10         setRootNode(null);
  11     }
  12
  13     private void setRootNode(Node<Integer> node) {
  14         rootNode = node;
  15     }
  16
  17     private Node<Integer> getRootNode() {
  18         return rootNode;
  19     }
  20
  21     private boolean isEmpty() {
  22         return (getRootNode() == null);
  23     }
  24
  25     private Node<Integer> inserer_rec(Node<Integer> currentNode, int value) {
  26         if (currentNode == null) {
  27             return new Node<Integer>(value);
  28         }
  29         if (value < currentNode.getData()) {
  30             currentNode.setLeftNode(inserer_rec(currentNode.getLeftNode(), value));
  31         } else if (value > currentNode.getData()) {
  32             currentNode.setRightNode(inserer_rec(currentNode.getRightNode(), value));
  33         } /* skip the equality case */
  34         return currentNode;
  35     }
  36
  37     public void inserer(int value) {
  38         setRootNode(inserer_rec(rootNode, value));
  39     }
  40
  41     private Node<Integer> supprimer_rec(Node<Integer> currentNode, int value) {
  42         if (currentNode == null) {
  43             return null;
  44         }
  45         if (value == currentNode.getData()) {
  46             if (currentNode.getLeftNode() == null && currentNode.getRightNode() == null) {
  47                 return null;
  48             } else if (currentNode.getRightNode() == null) {
  49                 return currentNode.getLeftNode();
  50             } else if (currentNode.getLeftNode() == null) {
  51                 return currentNode.getRightNode();
  52             } else {
  53                 /*
  54                 * First, we need to find the node that will replace the deleted node.
  55                 * We’ll use the smallest node of the node to be deleted’s right sub-tree.
  56                 * Then, we assign the smallest value to the node to delete and after that,
  57                 * we’ll delete it from the right subtree.
  58                 */
  59                 int smallestValue = findSmallestData(currentNode.getRightNode());
  60                 currentNode.setData(smallestValue);
  61                 currentNode.setRightNode(supprimer_rec(currentNode.getRightNode(), smallestValue));
  62                 return currentNode;
  63             }
  64         } else if (value < currentNode.getData()) {
  65             currentNode.setLeftNode(supprimer_rec(currentNode.getLeftNode(), value));
  66         } else {
  67             currentNode.setRightNode(supprimer_rec(currentNode.getRightNode(), value));
  68         }
  69         return currentNode;
  70     }
  71
  72     public void supprimer(int value) {
  73         supprimer_rec(rootNode, value);
  74     }
  75
  76     private boolean hasDataRec(Node<Integer> currentNode, int value) {
  77         if (currentNode == null) {
  78             return false;
  79         }
  80         if (value == currentNode.getData()) {
  81             return true;
  82         }
  83         return value < currentNode.getData() ? hasDataRec(currentNode.getLeftNode(), value) : hasDataRec(currentNode.getRightNode(), value);
  84     }
  85
  86     public boolean hasData(int value) {
  87         return hasDataRec(rootNode, value);
  88     }
  89
  90     private int findSmallestData(Node<Integer> node) {
  91         return node.getLeftNode() == null ? node.getData() : findSmallestData(node.getLeftNode());
  92     }
  93
  94     private void afficher_rec(Node<Integer> currentNode) {
  95         if (currentNode != null) {
  96             afficher_rec(currentNode.getLeftNode());
  97             System.out.print(currentNode.getData() + " ");
  98             afficher_rec(currentNode.getRightNode());
  99         }
 100     }
 101
 102     public void afficher() {
 103         afficher_rec(rootNode);
 104         System.out.println();
 105     }
 106
 107     private void afficher_arbre_rec(Node<Integer> currentNode, int column) {
 108         if (currentNode != null) {
 109             afficher_arbre_rec(currentNode.getRightNode(), column + 1);
 110             for (int i = 0; i < column; i++) {
 111                 System.out.print("   ");
 112             }
 113             System.out.println(currentNode.getData());
 114             afficher_arbre_rec(currentNode.getLeftNode(), column + 1);
 115         }
 116     }
 117
 118     public void afficher_arbre() {
 119         afficher_arbre_rec(rootNode, 1);
 120     }
 121
 122     public static void main(String[] args) {
 123         ArbreBinaire bTree = new ArbreBinaire();
 124
 125         bTree.inserer(2);
 126         bTree.inserer(6);
 127         bTree.inserer(4);
 128         bTree.inserer(5);
 129         bTree.inserer(1);
 130         bTree.inserer(0);
 131
 132         bTree.afficher();
 133         bTree.afficher_arbre();
 134
 135         bTree.supprimer(4);
 136
 137         bTree.afficher();
 138         bTree.afficher_arbre();
 139
 140         bTree.supprimer(6);
 141
 142         bTree.afficher();
 143         bTree.afficher_arbre();
 144
 145         bTree.inserer(2);
 146         bTree.inserer(7);
 147         bTree.inserer(3);
 148         bTree.inserer(9);
 149         bTree.inserer(11);
 150         bTree.inserer(10);
 151         bTree.inserer(8);
 152         bTree.inserer(4);
 153
 154         bTree.afficher();
 155         bTree.afficher_arbre();
 156     }
 157
 158 }