Fix the Compactable implementation in Entiers and Listes classes.

[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 class IntNode {
        private int data;
        private IntNode leftIntNode;
        private IntNode rightIntNode;

        IntNode(int value) {
            setData(value);
            setLeftNode(null);
            setRightNode(null);
        }

        IntNode(int value, IntNode leftNode, IntNode rightNode) {
            setData(value);
            setLeftNode(leftNode);
            setRightNode(rightNode);
        }

        private int getData() {
            return data;
        }

        private void setData(int value) {
            data = value;
        }

        private IntNode getLeftNode() {
            return leftIntNode;
        }

        private void setLeftNode(IntNode leftNode) {
            leftIntNode = leftNode;
        }

        private IntNode getRightNode() {
            return rightIntNode;
        }

        private void setRightNode(IntNode rightNode) {
            rightIntNode = rightNode;
        }

    }

    private IntNode rootNode;

    ArbreBinaire() {
        setRootNode(null);
    }

    private void setRootNode(IntNode node) {
        rootNode = node;
    }

    private IntNode getRootNode() {
        return rootNode;
    }

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

    private IntNode inserer_rec(IntNode currentNode, int value) {
        if (currentNode == null) {
            return new IntNode(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 IntNode supprimer_rec(IntNode 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(IntNode 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(IntNode node) {
        return node.getLeftNode() == null ? node.getData() : findSmallestData(node.getLeftNode());
    }

    private void afficher_rec(IntNode 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(IntNode 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();
    }

}