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         }
  73         if (value < currentNode.getData()) {
  74             currentNode.setLeftNode(inserer_rec(currentNode.getLeftNode(), value));
  75         } else if (value > currentNode.getData()) {
  76             currentNode.setRightNode(inserer_rec(currentNode.getRightNode(), value));
  77         } /* skip the equality case */
  78         return currentNode;
  79     }
  80
  81     public void inserer(int value) {
  82         setRootNode(inserer_rec(rootNode, value));
  83     }
  84
  85     private IntNode supprimer_rec(IntNode currentNode, int value) {
  86         if (currentNode == null) {
  87             return null;
  88         }
  89         if (value == currentNode.getData()) {
  90             if (currentNode.getLeftNode() == null && currentNode.getRightNode() == null) {
  91                 return null;
  92             } else if (currentNode.getRightNode() == null) {
  93                 return currentNode.getLeftNode();
  94             } else if (currentNode.getLeftNode() == null) {
  95                 return currentNode.getRightNode();
  96             } else {
  97                 /*
  98                 * First, we need to find the node that will replace the deleted node.
  99                 * We’ll use the smallest node of the node to be deleted’s right sub-tree.
 100                 * Then, we assign the smallest value to the node to delete and after that,
 101                 * we’ll delete it from the right subtree.
 102                 */
 103                 int smallestValue = findSmallestData(currentNode.getRightNode());
 104                 currentNode.setData(smallestValue);
 105                 currentNode.setRightNode(supprimer_rec(currentNode.getRightNode(), smallestValue));
 106                 return currentNode;
 107             }
 108         } else if (value < currentNode.getData()) {
 109             currentNode.setLeftNode(supprimer_rec(currentNode.getLeftNode(), value));
 110         } else {
 111             currentNode.setRightNode(supprimer_rec(currentNode.getRightNode(), value));
 112         }
 113         return currentNode;
 114     }
 115
 116     public void supprimer(int value) {
 117         supprimer_rec(rootNode, value);
 118     }
 119
 120     private boolean hasDataRec(IntNode currentNode, int value) {
 121         if (currentNode == null) {
 122             return false;
 123         }
 124         if (value == currentNode.getData()) {
 125             return true;
 126         }
 127         return value < currentNode.getData() ? hasDataRec(currentNode.getLeftNode(), value) : hasDataRec(currentNode.getRightNode(), value);
 128     }
 129
 130     public boolean hasData(int value) {
 131         return hasDataRec(rootNode, value);
 132     }
 133
 134     private int findSmallestData(IntNode node) {
 135         return node.getLeftNode() == null ? node.getData() : findSmallestData(node.getLeftNode());
 136     }
 137
 138     private void afficher_rec(IntNode currentNode) {
 139         if (currentNode != null) {
 140             afficher_rec(currentNode.getLeftNode());
 141             System.out.print(currentNode.getData() + " ");
 142             afficher_rec(currentNode.getRightNode());
 143         }
 144     }
 145
 146     public void afficher() {
 147         afficher_rec(rootNode);
 148         System.out.println();
 149     }
 150
 151     private void afficher_arbre_rec(IntNode currentNode, int column) {
 152         if (currentNode != null) {
 153             afficher_arbre_rec(currentNode.getRightNode(), column + 1);
 154             for (int i = 0; i < column; i++) {
 155                 System.out.print("   ");
 156             }
 157             System.out.println(currentNode.getData());
 158             afficher_arbre_rec(currentNode.getLeftNode(), column + 1);
 159         }
 160     }
 161
 162     public void afficher_arbre() {
 163         afficher_arbre_rec(rootNode, 1);
 164     }
 165
 166     public static void main(String[] args) {
 167         ArbreBinaire bTree = new ArbreBinaire();
 168
 169         bTree.inserer(2);
 170         bTree.inserer(6);
 171         bTree.inserer(4);
 172         bTree.inserer(5);
 173         bTree.inserer(1);
 174         bTree.inserer(0);
 175
 176         bTree.afficher();
 177         bTree.afficher_arbre();
 178
 179         bTree.supprimer(4);
 180
 181         bTree.afficher();
 182         bTree.afficher_arbre();
 183
 184         bTree.supprimer(6);
 185
 186         bTree.afficher();
 187         bTree.afficher_arbre();
 188
 189         bTree.inserer(2);
 190         bTree.inserer(7);
 191         bTree.inserer(3);
 192         bTree.inserer(9);
 193         bTree.inserer(11);
 194         bTree.inserer(10);
 195         bTree.inserer(8);
 196         bTree.inserer(4);
 197
 198         bTree.afficher();
 199         bTree.afficher_arbre();
 200     }
 201
 202 }