Les arbres binaires sont des structures de données fondamentales. Cet article explore les algorithmes courants liés à leur manipulation, en incluant la construction, le parcours, la recherche et la modification.

Définition d'un nœud d'arbre binaire

class TreeNode {
    int data;
    TreeNode leftChild;
    TreeNode rightChild;

    TreeNode(int value) {
        this.data = value;
        this.leftChild = null;
        this.rightChild = null;
    }
}

Parcours pré-ordre

class PreOrderTraversal {
    public List<integer> traverse(TreeNode root) {
        List<integer> elements = new ArrayList<>();
        collectPreOrder(root, elements);
        return elements;
    }

    private void collectPreOrder(TreeNode node, List<integer> container) {
        if (node == null) {
            return;
        }
        container.add(node.data);
        collectPreOrder(node.leftChild, container);
        collectPreOrder(node.rightChild, container);
    }
}
</integer></integer></integer>

Parcours par niveaux

class LevelOrderTraversal {
    public List<list>> traverse(TreeNode root) {
        List<list>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<treenode> processingQueue = new LinkedList<>();
        processingQueue.offer(root);

        while (!processingQueue.isEmpty()) {
            int levelSize = processingQueue.size();
            List<integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode current = processingQueue.poll();
                currentLevel.add(current.data);

                if (current.leftChild != null) {
                    processingQueue.offer(current.leftChild);
                }
                if (current.rightChild != null) {
                    processingQueue.offer(current.rightChild);
                }
            }
            result.add(currentLevel);
        }
        return result;
    }
}
</integer></treenode></list></list>

Voir depuis la droite

class RightView {
    public List<integer> getRightView(TreeNode root) {
        List<integer> visibleNodes = new ArrayList<>();
        if (root == null) {
            return visibleNodes;
        }

        Queue<treenode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int nodesInLevel = queue.size();

            while (nodesInLevel > 0) {
                TreeNode polledNode = queue.poll();
                nodesInLevel--;

                if (nodesInLevel == 0) {
                    visibleNodes.add(polledNode.data);
                }

                if (polledNode.leftChild != null) {
                    queue.add(polledNode.leftChild);
                }
                if (polledNode.rightChild != null) {
                    queue.add(polledNode.rightChild);
                }
            }
        }
        return visibleNodes;
    }
}
</treenode></integer></integer>

Moyenne des niveaux

class LevelAverage {
    public List<double> calculateAverages(TreeNode root) {
        List<double> averages = new ArrayList<>();
        if (root == null) {
            return averages;
        }

        Queue<treenode> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);

        while (!nodeQueue.isEmpty()) {
            int count = nodeQueue.size();
            double sum = 0.0;

            for (int i = 0; i < count; i++) {
                TreeNode current = nodeQueue.remove();
                sum += current.data;

                if (current.leftChild != null) {
                    nodeQueue.add(current.leftChild);
                }
                if (current.rightChild != null) {
                    nodeQueue.add(current.rightChild);
                }
            }
            averages.add(sum / count);
        }
        return averages;
    }
}
</treenode></double></double>

Inverser un arbre binaire

class TreeInverter {
    public TreeNode invert(TreeNode root) {
        if (root == null) {
            return null;
        }

        TreeNode invertedLeft = invert(root.leftChild);
        TreeNode invertedRight = invert(root.rightChild);

        root.leftChild = invertedRight;
        root.rightChild = invertedLeft;

        return root;
    }
}

Vérifier la symétrie

class SymmetryChecker {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return areSubtreesMirror(root.leftChild, root.rightChild);
    }

    private boolean areSubtreesMirror(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) {
            return true;
        }
        if (node1 == null || node2 == null) {
            return false;
        }
        if (node1.data != node2.data) {
            return false;
        }

        boolean outerMatch = areSubtreesMirror(node1.leftChild, node2.rightChild);
        boolean innerMatch = areSubtreesMirror(node1.rightChild, node2.leftChild);

        return outerMatch && innerMatch;
    }
}

Vérifier l'égalité de deux arbres

class TreeComparator {
    public boolean areEqual(TreeNode tree1, TreeNode tree2) {
        if (tree1 == null && tree2 == null) {
            return true;
        }
        if (tree1 == null || tree2 == null) {
            return false;
        }
        if (tree1.data != tree2.data) {
            return false;
        }

        boolean leftSubtreeEqual = areEqual(tree1.leftChild, tree2.leftChild);
        boolean rightSubtreeEqual = areEqual(tree1.rightChild, tree2.rightChild);

        return leftSubtreeEqual && rightSubtreeEqual;
    }
}

Profondeur maximale

class MaxDepthCalculator {
    public int calculate(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftDepth = calculate(root.leftChild);
        int rightDepth = calculate(root.rightChild);

        return Math.max(leftDepth, rightDepth) + 1;
    }
}

Profondeur minimale

class MinDepthCalculator {
    public int calculate(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // Si un sous-arbre est vide, l'autre détermine la profondeur minimale.
        if (root.leftChild == null) {
            return calculate(root.rightChild) + 1;
        }
        if (root.rightChild == null) {
            return calculate(root.leftChild) + 1;
        }

        int leftMin = calculate(root.leftChild);
        int rightMin = calculate(root.rightChild);

        return Math.min(leftMin, rightMin) + 1;
    }
}

Compter les nœuds

class NodeCounter {
    public int countAllNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftCount = countAllNodes(root.leftChild);
        int rightCount = countAllNodes(root.rightChild);

        return leftCount + rightCount + 1;
    }
}

Vérifier l'équilibre

class BalanceVerifier {
    public boolean isBalanced(TreeNode root) {
        return checkBalance(root) != -1;
    }

    private int checkBalance(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftHeight = checkBalance(node.leftChild);
        if (leftHeight == -1) {
            return -1;
        }

        int rightHeight = checkBalance(node.rightChild);
        if (rightHeight == -1) {
            return -1;
        }

        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }

        return Math.max(leftHeight, rightHeight) + 1;
    }
}

Tous les chemins

class PathFinder {
    public List<string> findAllPaths(TreeNode root) {
        List<string> paths = new ArrayList<>();
        if (root == null) {
            return paths;
        }
        explorePaths(root, "", paths);
        return paths;
    }

    private void explorePaths(TreeNode node, String currentPath, List<string> pathList) {
        if (node == null) {
            return;
        }

        String updatedPath = currentPath.isEmpty() ?
            String.valueOf(node.data) :
            currentPath + "->" + node.data;

        if (node.leftChild == null && node.rightChild == null) {
            pathList.add(updatedPath);
            return;
        }

        explorePaths(node.leftChild, updatedPath, pathList);
        explorePaths(node.rightChild, updatedPath, pathList);
    }
}
</string></string></string>

Somme des feuilles gauches

class LeftLeafSum {
    public int calculateSum(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int sum = 0;
        if (root.leftChild != null &&
            root.leftChild.leftChild == null &&
            root.leftChild.rightChild == null) {
            sum += root.leftChild.data;
        }

        sum += calculateSum(root.leftChild);
        sum += calculateSum(root.rightChild);

        return sum;
    }
}

Feuille la plus basse à gauche

class DeepestLeftLeafFinder {
    private int maxDepth = -1;
    private int deepestValue = 0;

    public int findDeepestLeftLeafValue(TreeNode root) {
        if (root == null) {
            return 0;
        }
        deepestValue = root.data; // Valeur par défaut si l'arbre est une seule racine
        searchDeepestLeft(root, 0);
        return deepestValue;
    }

    private void searchDeepestLeft(TreeNode node, int currentDepth) {
        if (node == null) {
            return;
        }

        if (node.leftChild == null && node.rightChild == null) {
            if (currentDepth > maxDepth) {
                maxDepth = currentDepth;
                deepestValue = node.data;
            }
            return;
        }

        searchDeepestLeft(node.leftChild, currentDepth + 1);
        searchDeepestLeft(node.rightChild, currentDepth + 1);
    }
}

Somme des chemins

class PathSumChecker {
    public boolean hasPathWithSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        targetSum -= root.data;

        if (root.leftChild == null && root.rightChild == null) {
            return targetSum == 0;
        }

        boolean leftResult = hasPathWithSum(root.leftChild, targetSum);
        if (leftResult) {
            return true;
        }

        boolean rightResult = hasPathWithSum(root.rightChild, targetSum);
        return rightResult;
    }
}

Construction à partir de parcours

class TreeBuilder {
    public TreeNode buildFromInAndPost(int[] inorder, int[] postorder) {
        if (inorder.length == 0 || postorder.length == 0) {
            return null;
        }
        return constructSubtree(inorder, 0, inorder.length - 1,
                                postorder, 0, postorder.length - 1);
    }

    private TreeNode constructSubtree(int[] in, int inStart, int inEnd,
                                     int[] post, int postStart, int postEnd) {
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }

        int rootValue = post[postEnd];
        TreeNode root = new TreeNode(rootValue);

        int rootIndexInOrder = -1;
        for (int i = inStart; i <= inEnd; i++) {
            if (in[i] == rootValue) {
                rootIndexInOrder = i;
                break;
            }
        }

        int leftSubtreeSize = rootIndexInOrder - inStart;

        root.leftChild = constructSubtree(in, inStart, rootIndexInOrder - 1,
                                          post, postStart, postStart + leftSubtreeSize - 1);
        root.rightChild = constructSubtree(in, rootIndexInOrder + 1, inEnd,
                                           post, postStart + leftSubtreeSize, postEnd - 1);

        return root;
    }
}

Arbre binaire maximum

class MaxBinaryTreeBuilder {
    public TreeNode build(int[] values) {
        return buildSubtree(values, 0, values.length - 1);
    }

    private TreeNode buildSubtree(int[] arr, int left, int right) {
        if (left > right) {
            return null;
        }

        int maxValueIndex = findMaxIndex(arr, left, right);
        TreeNode root = new TreeNode(arr[maxValueIndex]);

        root.leftChild = buildSubtree(arr, left, maxValueIndex - 1);
        root.rightChild = buildSubtree(arr, maxValueIndex + 1, right);

        return root;
    }

    private int findMaxIndex(int[] arr, int start, int end) {
        int maxIndex = start;
        for (int i = start + 1; i <= end; i++) {
            if (arr[i] > arr[maxIndex]) {
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}

Fusionner deux arbres

class TreeMerger {
    public TreeNode merge(TreeNode tree1, TreeNode tree2) {
        if (tree1 == null) {
            return tree2;
        }
        if (tree2 == null) {
            return tree1;
        }

        TreeNode merged = new TreeNode(tree1.data + tree2.data);
        merged.leftChild = merge(tree1.leftChild, tree2.leftChild);
        merged.rightChild = merge(tree1.rightChild, tree2.rightChild);

        return merged;
    }
}

Recherche dans un ABR

class BSTSearch {
    public TreeNode search(TreeNode root, int target) {
        if (root == null || root.data == target) {
            return root;
        }

        if (target < root.data) {
            return search(root.leftChild, target);
        } else {
            return search(root.rightChild, target);
        }
    }
}

Validasion d'un ABR

class BSTValidator {
    private TreeNode previous = null;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        if (!isValidBST(root.leftChild)) {
            return false;
        }

        if (previous != null && previous.data >= root.data) {
            return false;
        }
        previous = root;

        return isValidBST(root.rightChild);
    }
}

Différence minimale dans un ABR

class MinDifferenceFinder {
    private int minDiff = Integer.MAX_VALUE;
    private TreeNode prev = null;

    public int findMinDifference(TreeNode root) {
        inorderTraversal(root);
        return minDiff;
    }

    private void inorderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }

        inorderTraversal(node.leftChild);

        if (prev != null) {
            int diff = Math.abs(node.data - prev.data);
            minDiff = Math.min(minDiff, diff);
        }
        prev = node;

        inorderTraversal(node.rightChild);
    }
}

Mode dans un ABR

class ModeFinder {
    private List<integer> modes = new ArrayList<>();
    private Integer currentValue = null;
    private int currentCount = 0;
    private int maxCount = 0;

    public int[] findModes(TreeNode root) {
        traverseInorder(root);

        int[] result = new int[modes.size()];
        for (int i = 0; i < modes.size(); i++) {
            result[i] = modes.get(i);
        }
        return result;
    }

    private void traverseInorder(TreeNode node) {
        if (node == null) {
            return;
        }

        traverseInorder(node.leftChild);

        if (currentValue == null || currentValue != node.data) {
            currentValue = node.data;
            currentCount = 1;
        } else {
            currentCount++;
        }

        if (currentCount > maxCount) {
            maxCount = currentCount;
            modes.clear();
            modes.add(currentValue);
        } else if (currentCount == maxCount) {
            modes.add(currentValue);
        }

        traverseInorder(node.rightChild);
    }
}
</integer>

Plus proche ancêtre commun (arbre général)

class GeneralTreeLCA {
    public TreeNode findLCA(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }

        TreeNode leftLCA = findLCA(root.leftChild, p, q);
        TreeNode rightLCA = findLCA(root.rightChild, p, q);

        if (leftLCA != null && rightLCA != null) {
            return root;
        }

        return (leftLCA != null) ? leftLCA : rightLCA;
    }
}

Plus proche ancêtre commun (ABR)

class BSTLCA {
    public TreeNode findLCA(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        if (p.data < root.data && q.data < root.data) {
            return findLCA(root.leftChild, p, q);
        }

        if (p.data > root.data && q.data > root.data) {
            return findLCA(root.rightChild, p, q);
        }

        // Les nœuds sont dans des sous-arbres différents ou l'un d'eux est la racine.
        return root;
    }
}

Insertion dans un ABR

class BSTInserter {
    public TreeNode insert(TreeNode root, int value) {
        if (root == null) {
            return new TreeNode(value);
        }

        if (value < root.data) {
            root.leftChild = insert(root.leftChild, value);
        } else if (value > root.data) {
            root.rightChild = insert(root.rightChild, value);
        }

        return root;
    }
}

Suppression dans un ABR

class BSTDeleter {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }

        if (key < root.data) {
            root.leftChild = deleteNode(root.leftChild, key);
        } else if (key > root.data) {
            root.rightChild = deleteNode(root.rightChild, key);
        } else {
            // Le nœud à supprimer a été trouvé.
            if (root.leftChild == null) {
                return root.rightChild;
            }
            if (root.rightChild == null) {
                return root.leftChild;
            }

            // Le nœud a deux enfants : trouver le successeur in-order (min dans le sous-arbre droit).
            TreeNode successor = findMin(root.rightChild);
            root.data = successor.data;
            root.rightChild = deleteNode(root.rightChild, successor.data);
        }
        return root;
    }

    private TreeNode findMin(TreeNode node) {
        while (node.leftChild != null) {
            node = node.leftChild;
        }
        return node;
    }
}

Élagage d'un ABR

class BSTTrimmer {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }

        if (root.data < low) {
            return trimBST(root.rightChild, low, high);
        }

        if (root.data > high) {
            return trimBST(root.leftChild, low, high);
        }

        root.leftChild = trimBST(root.leftChild, low, high);
        root.rightChild = trimBST(root.rightChild, low, high);

        return root;
    }
}