Implement a class for a binary tree of integers.

[TP_POO.git] / Arbres / ArbreBinaire.java

/**
 * Binary tree class.
 * A binary tree is a ordered value tree with only two childs by 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);
        } else if (value < currentNode.getData()) {
            currentNode.setLeftNode(inserer_rec(currentNode.getLeftNode(), value));
        } else if (value > currentNode.getData()) {
            currentNode.setRightNode(inserer_rec(currentNode.getRightNode(), value));
        } else {
            /* equality */
            return currentNode;
        }
        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;
        } else 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 {
                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(rootNote, value);
    }

    private int findSmallestData(IntNode node) {
        return node.getLeftNode() == null ? node.getData() : findSmallestData(node.getLeftNode());
    }

    public afficher_rec(IntNode currentNode) {
        if (currentNode.getLeftNode() != null) {
            afficher_rec(currentNode.getLeftNode());
        } else if (currentNode.getRightNode() != null) {
            afficher_rec(currentNode.getRightNode());
        }
        System.out.println("Valeur dans le noeud : ");
    }

    public static void main(String[] args) {
        ArbreBinaire Btree = new ArbreBinaire();

        Btree.inserer(5);
        Btree.inserer(2);
        Btree.inserer(7);
        Btree.inserer(1);

        String Btreeout = Btree.toString();
        System.out.println(Btreeout);

    }

}