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
   8     private class IntNode {
   9         private int data;
  10         private IntNode leftIntNode;
  11         private IntNode rightIntNode;
  12
  13         IntNode(int value) {
  14             setData(value);
  15             setLeftNode(null);
  16             setRightNode(null);
  17         }
  18
  19         IntNode(int value, IntNode leftNode, IntNode rightNode) {
  20             setData(value);
  21             setLeftNode(leftNode);
  22             setRightNode(rightNode);
  23         }
  24
  25         private int getData() {
  26             return data;
  27         }
  28
  29         private void setData(int value) {
  30             data = value;
  31         }
  32
  33         private IntNode getLeftNode() {
  34             return leftIntNode;
  35         }
  36
  37         private void setLeftNode(IntNode leftNode) {
  38             leftIntNode = leftNode;
  39         }
  40
  41         private IntNode getRightNode() {
  42             return rightIntNode;
  43         }
  44
  45         private void setRightNode(IntNode rightNode) {
  46             rightIntNode = rightNode;
  47         }
  48
  49     }
  50
  51     private IntNode rootNode;
  52
  53     ArbreBinaire() {
  54         setRootNode(null);
  55     }
  56
  57     private void setRootNode(IntNode node) {
  58         rootNode = node;
  59     }
  60
  61     private IntNode getRootNode() {
  62         return rootNode;
  63     }
  64
  65     private boolean isEmpty() {
  66         return (getRootNode() == null);
  67     }
  68
  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));
  76         } /* skip the equality case */
  77         return currentNode;
  78     }
  79
  80     public void inserer(int value) {
  81         setRootNode(inserer_rec(rootNode, value));
  82     }
  83
  84     private IntNode supprimer_rec(IntNode currentNode, int value) {
  85         if (currentNode == null) {
  86             return null;
  87         } else if (value == currentNode.getData()) {
  88             if (currentNode.getLeftNode() == null && currentNode.getRightNode() == null) {
  89                 return null;
  90             } else if (currentNode.getRightNode() == null) {
  91                 return currentNode.getLeftNode();
  92             } else if (currentNode.getLeftNode() == null) {
  93                 return currentNode.getRightNode();
  94             } else {
  95                 /*
  96                 * First, we need to find the node that will replace the deleted node.
  97                 * We’ll use the smallest node of the node to be deleted’s right sub-tree.
  98                 * Then, we assign the smallest value to the node to delete and after that,
  99                 * we’ll delete it from the right subtree.
 100                 */
 101                 int smallestValue = findSmallestData(currentNode.getRightNode());
 102                 currentNode.setData(smallestValue);
 103                 currentNode.setRightNode(supprimer_rec(currentNode.getRightNode(), smallestValue));
 104                 return currentNode;
 105             }
 106         } else if (value < currentNode.getData()) {
 107             currentNode.setLeftNode(supprimer_rec(currentNode.getLeftNode(), value));
 108         } else {
 109             currentNode.setRightNode(supprimer_rec(currentNode.getRightNode(), value));
 110         }
 111         return currentNode;
 112     }
 113
 114     public void supprimer(int value) {
 115         supprimer_rec(rootNode, value);
 116     }
 117
 118     private boolean hasDataRec(IntNode currentNode, int value) {
 119         if (currentNode == null) {
 120             return false;
 121         }
 122         if (value == currentNode.getData()) {
 123             return true;
 124         }
 125         return value < currentNode.getData() ? hasDataRec(currentNode.getLeftNode(), value) : hasDataRec(currentNode.getRightNode(), value);
 126     }
 127
 128     public boolean hasData(int value) {
 129         return hasDataRec(rootNode, value);
 130     }
 131
 132     private int findSmallestData(IntNode node) {
 133         return node.getLeftNode() == null ? node.getData() : findSmallestData(node.getLeftNode());
 134     }
 135
 136     private void afficher_rec(IntNode currentNode) {
 137         if (currentNode != null) {
 138             afficher_rec(currentNode.getLeftNode());
 139             System.out.print(currentNode.getData() + " ");
 140             afficher_rec(currentNode.getRightNode());
 141         }
 142     }
 143
 144     public void afficher() {
 145         afficher_rec(rootNode);
 146         System.out.println();
 147     }
 148
 149     private void afficher_arbre_rec(IntNode currentNode, int column) {
 150         if (currentNode != null) {
 151             afficher_arbre_rec(currentNode.getRightNode(), column + 1);
 152             for (int i = 0; i < column; i++) {
 153                 System.out.print("   ");
 154             }
 155             System.out.println(currentNode.getData());
 156             afficher_arbre_rec(currentNode.getLeftNode(), column + 1);
 157         }
 158     }
 159
 160     public void afficher_arbre() {
 161         afficher_arbre_rec(rootNode, 1);
 162     }
 163
 164     public static void main(String[] args) {
 165         ArbreBinaire bTree = new ArbreBinaire();
 166
 167         bTree.inserer(2);
 168         bTree.inserer(6);
 169         bTree.inserer(4);
 170         bTree.inserer(5);
 171         bTree.inserer(1);
 172         bTree.inserer(0);
 173
 174         bTree.afficher();
 175         bTree.afficher_arbre();
 176
 177         bTree.supprimer(4);
 178
 179         bTree.afficher();
 180         bTree.afficher_arbre();
 181
 182         bTree.supprimer(6);
 183
 184         bTree.afficher();
 185         bTree.afficher_arbre();
 186
 187         bTree.inserer(2);
 188         bTree.inserer(7);
 189         bTree.inserer(3);
 190         bTree.inserer(9);
 191         bTree.inserer(11);
 192         bTree.inserer(10);
 193         bTree.inserer(8);
 194         bTree.inserer(4);
 195
 196         bTree.afficher();
 197         bTree.afficher_arbre();
 198     }
 199
 200 }