Explication détaillée de l'implémentation de l'arbre binaire Java et des cas d'application spécifiques

Explication détaillée de l'implémentation de l'arbre binaire Java et des cas d'application spécifiques

L'arbre binaire est une structure de données souvent utilisée en informatique, qui peut effectuer des opérations de recherche et de tri très efficaces. Dans cet article, nous verrons comment implémenter un arbre binaire en Java et certains de ses cas d'application spécifiques.

Définition de l'arbre binaire

L'arbre binaire est une structure de données très importante, composée du nœud racine (le nœud supérieur de l'arbre) et de plusieurs sous-arbres gauche et sous-arbres droits. Chaque nœud a au plus deux nœuds enfants, le nœud enfant de gauche est appelé sous-arbre gauche et le nœud enfant de droite est appelé sous-arbre droit. Si un nœud n’a aucun nœud enfant, il est appelé nœud feuille ou nœud terminal.

Implémentation d'un arbre binaire en Java

La classe Node peut être utilisée en Java pour représenter les nœuds d'un arbre binaire. Cette classe contient une valeur de type int et deux références de type Node à gauche et à droite. , représentant respectivement le nœud enfant gauche et le nœud enfant droit. Voici un exemple de code :

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

Opérations de base pour implémenter un arbre binaire

1. Création d'un arbre binaire

#🎜🎜 #peut être fait de manière récursive Pour créer un arbre binaire, créez d'abord le nœud racine, puis créez respectivement le sous-arbre gauche et le sous-arbre droit. Voici un exemple de code :

public class TreeBuilder {
    public TreeNode buildTree(int[] array) {
        if (array == null || array.length == 0) {
            return null;
        }
        return build(array, 0, array.length - 1);
    }

    private TreeNode build(int[] array, int start, int end) {
        if (start > end) {
            return null;
        }
        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(array[mid]);
        root.left = build(array, start, mid - 1);
        root.right = build(array, mid + 1, end);
        return root;
    }
}

Find node

L'opération de recherche de l'arbre binaire est très efficace, généralement en comparant la taille de la valeur du nœud et de la valeur cible Pour décider s'il faut rechercher le sous-arbre gauche ou le sous-arbre droit. Voici un exemple de code :

public class TreeSearch {
    public TreeNode search(TreeNode root, int target) {
        if (root == null || root.val == target) {
            return root;
        }
        if (root.val > target) {
            return search(root.left, target);
        } else {
            return search(root.right, target);
        }
    }
}

Insérer un nœud

Lors de l'insertion d'un nouveau nœud dans un arbre binaire, vous devez comparer la valeur du nœud et la taille de la valeur insérée, et décidez s'il faut insérer le nouveau nœud dans le sous-arbre de gauche ou dans le sous-arbre de droite en fonction du résultat de la comparaison. Voici un exemple de code :

public class TreeInsert {
    public TreeNode insert(TreeNode root, int target) {
        if (root == null) {
            return new TreeNode(target);
        }
        if (root.val > target) {
            root.left = insert(root.left, target);
        } else if (root.val < target) {
            root.right = insert(root.right, target);
        }
        return root;
    }
}

Delete node

La suppression d'un nœud est une opération relativement complexe et doit être discutée dans plusieurs situations . Supposons que le nœud A doit être supprimé, qui peut être divisé dans les trois situations suivantes :

A est un nœud feuille et peut être supprimé directement.
A n'a qu'un seul nœud enfant, il suffit de remplacer le nœud enfant par sa position.
A a deux nœuds enfants. Nous devons trouver le plus petit nœud B dans son sous-arbre droit, remplacer A par la valeur de B, puis supprimer B.

Ce qui suit est un exemple de code :

public class TreeDelete {
    public TreeNode delete(TreeNode root, int target) {
        if (root == null) {
            return null;
        }
        if (root.val > target) {
            root.left = delete(root.left, target);
        } else if (root.val < target) {
            root.right = delete(root.right, target);
        } else {
            if (root.left == null && root.right == null) {
                return null;
            } else if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            } else {
                TreeNode min = findMin(root.right);
                root.val = min.val;
                root.right = delete(root.right, min.val);
            }
        }
        return root;
    }

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

Cas d'application spécifique

Les arbres binaires peuvent résoudre certains problèmes courants de structure de données, tels que comme recherche Le kième élément, trouver les k éléments les plus petits, trouver la profondeur de l'arbre binaire, etc.

Voici des cas d'application spécifiques :

Trouver le kième élément

Le résultat du parcours dans l'ordre d'un arbre binaire est ordonné, vous pouvez donc utiliser le parcours dans l'ordre pour trouver le kième élément. Voici un exemple de code :

public class TreeFindKth {
    private int cnt = 0;

    public int kthSmallest(TreeNode root, int k) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        int left = kthSmallest(root.left, k);
        if (left != Integer.MAX_VALUE) {
            return left;
        }
        cnt++;
        if (cnt == k) {
            return root.val;
        }
        return kthSmallest(root.right, k);
    }
}

Trouver les plus petits k éléments

La recherche des plus petits k éléments dans un arbre binaire peut également être utilisée Pour un parcours séquentiel, prenez simplement les k premiers éléments. Voici un exemple de code :

public class TreeFindMinK {
    public List<Integer> kSmallest(TreeNode root, int k) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            result.add(current.val);
            if (result.size() == k) {
                return result;
            }
            current = current.right;
        }
        return result;
    }
}

Trouver la profondeur d'un arbre binaire

Vous pouvez utiliser la récursivité pour trouver la profondeur d'un binaire arbre. Voici un exemple de code :

public class TreeDepth {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

Summary

Cet article présente l'implémentation d'arbres binaires en Java et quelques cas d'application spécifiques. L'arbre binaire est une structure de données très efficace qui est souvent utilisée lors du traitement de grandes quantités de données. Dans les applications pratiques, nous pouvons choisir différentes méthodes de mise en œuvre en fonction des caractéristiques de problèmes spécifiques pour obtenir de meilleures performances.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!