/**
* 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();
}
}
repositories / TP_POO.git / blobdiff