Penjelasan terperinci tentang pelaksanaan pokok binari Java dan kes aplikasi tertentu

Penjelasan terperinci tentang pelaksanaan pokok binari Java dan kes aplikasi khusus

Pokok binari ialah struktur data yang sering digunakan dalam sains komputer, yang boleh melakukan operasi carian dan pengisihan yang sangat cekap. Dalam artikel ini, kita akan membincangkan cara untuk melaksanakan pokok binari di Jawa dan beberapa kes aplikasi khususnya.

Definisi pokok binari

Pokok binari ialah struktur data yang sangat penting, terdiri daripada nod akar (nod atas pokok) dan beberapa subpokok kiri dan subpokok kanan. Setiap nod mempunyai paling banyak dua nod anak, nod anak di sebelah kiri dipanggil subtree kiri, dan nod anak di sebelah kanan dipanggil subtree kanan. Jika nod tidak mempunyai sebarang nod anak, ia dipanggil nod daun atau nod terminal.

Pelaksanaan pokok binari dalam Java

Kelas Node boleh digunakan dalam Java untuk mewakili nod pokok binari Kelas ini mengandungi nilai jenis int dan dua rujukan jenis Nod kiri dan kanan, yang mewakili nod anak sebelah kiri dan nod anak kanan. Berikut ialah kod sampel:

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

Laksanakan operasi asas pokok binari

1. Buat pokok binari

Anda boleh mencipta pokok binari secara rekursif, mula-mula cipta nod akar , dan kemudian cipta subpokok kiri dan subpokok kanan masing-masing. Berikut ialah kod sampel:

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. Cari nod

Kendalian carian pepohon binari adalah sangat cekap Ia biasanya ditentukan dengan membandingkan saiz nod nilai dan nilai sasaran untuk menentukan sama ada hendak mencari anak kiri Pokok itu masih subpokok kanan. Berikut ialah kod sampel:

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. Sisipkan nod

Apabila memasukkan nod baharu ke dalam pokok binari, anda perlu membandingkan nilai nod dan saiz daripada nilai yang dimasukkan, dan tentukan berdasarkan hasil perbandingan Sama ada hendak memasukkan nod baharu ke dalam subpokok kiri atau subpokok kanan. Berikut ialah kod sampel:

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. Padam nod

Memadam nod ialah operasi yang agak rumit dan perlu dibincangkan dalam beberapa situasi. Andaikan bahawa nod A akan dipadamkan, yang boleh dibahagikan kepada tiga situasi berikut:

• A ialah nod daun dan boleh dipadamkan terus.
• A hanya mempunyai satu nod anak, cuma gantikan nod anak dengan kedudukannya.
• A mempunyai dua nod anak Anda perlu mencari nod B terkecil dalam subpohon kanannya, gantikan A dengan nilai B, dan kemudian padamkan B.

Berikut ialah kod sampel:

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

Kes aplikasi khusus

Pokok binari boleh menyelesaikan beberapa masalah struktur data biasa, seperti mencari elemen kth dan mencari elemen k terkecil, cari kedalaman pokok binari, dsb.

Berikut ialah kes aplikasi khusus:

1. Cari elemen ke-k

Hasil traversal tertib pokok binari adalah dalam perintah, jadi anda boleh menggunakan traversal Inorder untuk mencari elemen kth. Berikut ialah kod sampel:

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. Cari elemen k terkecil

Untuk mencari elemen k terkecil dalam pokok binari, anda juga boleh menggunakan traversal tertib , mengambil elemen k teratas. Berikut ialah kod sampel:

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. Mencari kedalaman pokok binari

Anda boleh menggunakan rekursi untuk mencari kedalaman pokok binari. Berikut ialah kod sampel:

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

Ringkasan

Artikel ini memperkenalkan pelaksanaan pepohon binari dalam Java dan beberapa kes aplikasi tertentu. Pokok binari ialah struktur data yang sangat cekap yang sering digunakan apabila memproses sejumlah besar data. Dalam aplikasi praktikal, kita boleh memilih kaedah pelaksanaan yang berbeza mengikut ciri masalah tertentu untuk mendapatkan prestasi yang lebih baik.

Atas ialah kandungan terperinci Penjelasan terperinci tentang pelaksanaan pokok binari Java dan kes aplikasi tertentu. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!