Code cleanup.

[TP_POO.git] / Arbres / ArbreBinaire.java

/**
 * Binary tree class.
 * A binary tree is a ordered value tree with only two childs per node
 */
public class ArbreBinaire {
    private Node<Integer> rootNode;

    ArbreBinaire() {
        setRootNode(null);
    }

    private void setRootNode(Node<Integer> node) {
        rootNode = node;
    }

    private Node<Integer> getRootNode() {
        return rootNode;
    }

    private boolean isEmpty() {
        return (getRootNode() == null);
    }

    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;
    }

    public void inserer(int value) {
        setRootNode(inserer_rec(rootNode, value));
    }

    private Node<Integer> supprimer_rec(Node<Integer> currentNode, int value) {
        if (currentNode == null) {
            return null;
        }
        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;
    }

    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 int findSmallestData(Node<Integer> node) {
        return node.getLeftNode() == null ? node.getData() : findSmallestData(node.getLeftNode());
    }

    private void afficher_rec(Node<Integer> currentNode) {
        if (currentNode != null) {
            afficher_rec(currentNode.getLeftNode());
            System.out.print(currentNode.getData() + " ");
            afficher_rec(currentNode.getRightNode());
        }
    }

    public void afficher() {
        afficher_rec(rootNode);
        System.out.println();
    }

    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);
        }
    }

    public void afficher_arbre() {
        afficher_arbre_rec(rootNode, 1);
    }

    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);

        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();
    }

}