Detaillierte Erläuterung der Java-Binärbaum-Implementierung und spezifischer Anwendungsfälle

Detaillierte Erläuterung der Java-Binärbaum-Implementierung und spezifischer Anwendungsfälle

Binärbaum ist eine in der Informatik häufig verwendete Datenstruktur, die sehr effiziente Such- und Sortiervorgänge durchführen kann. In diesem Artikel besprechen wir die Implementierung eines Binärbaums in Java und einige seiner spezifischen Anwendungsfälle.

Definition des Binärbaums

Der Binärbaum ist eine sehr wichtige Datenstruktur, die aus dem Wurzelknoten (dem obersten Knoten des Baums) und mehreren linken und rechten Teilbäumen besteht. Jeder Knoten hat höchstens zwei untergeordnete Knoten. Der untergeordnete Knoten links wird als linker Teilbaum bezeichnet, und der untergeordnete Knoten rechts wird als rechter Teilbaum bezeichnet. Wenn ein Knoten keine untergeordneten Knoten hat, wird er als Blattknoten oder Endknoten bezeichnet.

Binärbaum-Implementierung in Java

Die Node-Klasse kann in Java zur Darstellung von Binärbaumknoten verwendet werden. Diese Klasse enthält einen int-Typwert und zwei Node-Typreferenzen links und rechts, die den linken und den rechten untergeordneten Knoten darstellen jeweils. Das Folgende ist ein Beispielcode:

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

Implementieren der Grundoperationen eines Binärbaums

1. Erstellen eines Binärbaums

Sie können einen Binärbaum rekursiv erstellen, indem Sie zuerst den Wurzelknoten und dann den linken und rechten Teilbaum erstellen Teilbaum bzw. Das Folgende ist ein Beispielcode:

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

2. Knoten finden

Der Suchvorgang des Binärbaums ist sehr effizient. Im Allgemeinen wird durch Vergleichen der Größe des Knotenwerts entschieden, ob der linke Teilbaum oder der rechte Teilbaum durchsucht werden soll und der Zielwert. Das Folgende ist ein Beispielcode:

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

3. Knoten einfügen

Wenn Sie einen neuen Knoten in einen Binärbaum einfügen, müssen Sie den Wert des Knotens und die Größe des eingefügten Werts vergleichen und entscheiden, ob der neue Knoten eingefügt werden soll Knoten in den linken Teilbaum oder den rechten Teilbaum basierend auf dem Vergleichsergebnis. Das Folgende ist ein Beispielcode:

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

4. Knoten löschen

Das Löschen eines Knotens ist ein relativ komplexer Vorgang und muss in mehreren Situationen besprochen werden. Angenommen, Knoten A soll gelöscht werden, was in die folgenden drei Situationen unterteilt werden kann:

• A ist ein Blattknoten und kann direkt gelöscht werden.
• A hat nur einen untergeordneten Knoten. Ersetzen Sie einfach den untergeordneten Knoten durch seine Position.
• A hat zwei untergeordnete Knoten. Wir müssen den kleinsten Knoten B in seinem rechten Teilbaum finden, A durch den Wert von B ersetzen und dann B löschen.

Das Folgende ist ein Beispielcode:

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

Spezifische Anwendungsfälle

Binärbäume können einige häufige Datenstrukturprobleme lösen, z. B. das Finden des k-ten Elements, das Finden der kleinsten k-Elemente, das Ermitteln der Tiefe des Binärbaums usw .

Das Folgende sind spezifische Anwendungsfälle:

1. Suchen des k-ten Elements

Das Ergebnis der Durchquerung eines Binärbaums in der Reihenfolge ist geordnet, sodass die Durchquerung in der Reihenfolge verwendet werden kann, um das k-te Element zu finden . Das Folgende ist ein Beispielcode:

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

2. Finden Sie die kleinsten k Elemente

Um die kleinsten k Elemente in einem Binärbaum zu finden, können Sie auch die Durchquerung in der Reihenfolge verwenden. Nehmen Sie einfach die ersten k Elemente. Das Folgende ist ein Beispielcode:

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

3. Ermitteln der Tiefe eines Binärbaums

Sie können die Rekursion verwenden, um die Tiefe eines Binärbaums zu ermitteln. Das Folgende ist ein Beispielcode:

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

Zusammenfassung

Dieser Artikel stellt die Implementierung von Binärbäumen in Java und einige spezifische Anwendungsfälle vor. Der Binärbaum ist eine sehr effiziente Datenstruktur, die häufig bei der Verarbeitung großer Datenmengen verwendet wird. In praktischen Anwendungen können wir je nach den Merkmalen spezifischer Probleme unterschiedliche Implementierungsmethoden auswählen, um eine bessere Leistung zu erzielen.

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Java-Binärbaum-Implementierung und spezifischer Anwendungsfälle. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!