Menerapkan Pohon Biner di Java

1. Perkenalan

Pada artikel ini, kami akan membahas implementasi pohon biner di Java.

Demi artikel ini, kami akan menggunakan pohon biner yang diurutkan yang akan berisi nilai int .

2. Pohon Biner

Pohon biner adalah struktur data rekursif di mana setiap node dapat memiliki paling banyak 2 anak.

Jenis pohon biner yang umum adalah pohon pencarian biner, di mana setiap node memiliki nilai yang lebih besar dari atau sama dengan nilai node di sub-pohon kiri, dan kurang dari atau sama dengan nilai node di sub-kanan kanan. pohon.

Berikut adalah representasi visual cepat dari jenis pohon biner ini:

Untuk implementasinya, kita akan menggunakan kelas Node tambahan yang akan menyimpan nilai int dan menyimpan referensi ke setiap anak:

class Node { int value; Node left; Node right; Node(int value) { this.value = value; right = null; left = null; } }

Kemudian, mari tambahkan simpul awal dari pohon kita, biasanya disebut root:

public class BinaryTree { Node root; // ... }

3. Operasi Umum

Sekarang, mari kita lihat operasi paling umum yang dapat kita lakukan pada pohon biner.

3.1. Memasukkan Elemen

Operasi pertama yang akan kita bahas adalah penyisipan node baru.

Pertama, kita harus menemukan tempat di mana kita ingin menambahkan node baru agar pohon tetap tersortir . Kami akan mengikuti aturan ini mulai dari node root:

  • jika nilai simpul baru lebih rendah dari simpul saat ini, kita pergi ke anak kiri
  • jika nilai simpul baru lebih besar dari simpul saat ini, kita pergi ke anak yang tepat
  • ketika simpul saat ini nol, kita telah mencapai simpul daun dan kita bisa memasukkan simpul baru di posisi itu

Pertama, kami akan membuat metode rekursif untuk melakukan penyisipan:

private Node addRecursive(Node current, int value) { if (current == null) { return new Node(value); } if (value  current.value) { current.right = addRecursive(current.right, value); } else { // value already exists return current; } return current; }

Selanjutnya, kita akan membuat metode publik yang memulai rekursi dari simpul akar :

public void add(int value) { root = addRecursive(root, value); }

Sekarang mari kita lihat bagaimana kita dapat menggunakan metode ini untuk membuat pohon dari contoh kita:

private BinaryTree createBinaryTree() { BinaryTree bt = new BinaryTree(); bt.add(6); bt.add(4); bt.add(8); bt.add(3); bt.add(5); bt.add(7); bt.add(9); return bt; }

3.2. Menemukan sebuah Elemen

Sekarang mari tambahkan metode untuk memeriksa apakah pohon tersebut berisi nilai tertentu.

Seperti sebelumnya, pertama-tama kita akan membuat metode rekursif yang melintasi pohon:

private boolean containsNodeRecursive(Node current, int value) { if (current == null) { return false; } if (value == current.value) { return true; } return value < current.value ? containsNodeRecursive(current.left, value) : containsNodeRecursive(current.right, value); }

Di sini, kami mencari nilai dengan membandingkannya dengan nilai di node saat ini, lalu melanjutkan di anak kiri atau kanan tergantung itu.

Selanjutnya, mari buat metode publik yang dimulai dari root :

public boolean containsNode(int value) { return containsNodeRecursive(root, value); }

Sekarang, mari buat tes sederhana untuk memverifikasi bahwa pohon itu benar-benar berisi elemen yang disisipkan:

@Test public void givenABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements() { BinaryTree bt = createBinaryTree(); assertTrue(bt.containsNode(6)); assertTrue(bt.containsNode(4)); assertFalse(bt.containsNode(1)); }

Semua node yang ditambahkan harus berada di dalam pohon.

3.3. Menghapus sebuah Elemen

Operasi umum lainnya adalah penghapusan node dari pohon.

Pertama, kita harus menemukan node yang akan dihapus dengan cara yang sama seperti yang kita lakukan sebelumnya:

private Node deleteRecursive(Node current, int value) { if (current == null) { return null; } if (value == current.value) { // Node to delete found // ... code to delete the node will go here } if (value < current.value) { current.left = deleteRecursive(current.left, value); return current; } current.right = deleteRecursive(current.right, value); return current; }

Setelah kami menemukan node untuk dihapus, ada 3 kasus utama yang berbeda:

  • node tidak memiliki anak - ini adalah kasus yang paling sederhana; kita hanya perlu mengganti node ini dengan null di node induknya
  • sebuah node memiliki tepat satu anak - di node induk, kami mengganti node ini dengan satu-satunya anak.
  • node memiliki dua anak - ini adalah kasus paling kompleks karena memerlukan reorganisasi pohon

Mari kita lihat bagaimana kita dapat mengimplementasikan kasus pertama ketika simpul adalah simpul daun:

if (current.left == null && current.right == null) { return null; }

Sekarang mari kita lanjutkan dengan kasus ketika node memiliki satu anak:

if (current.right == null) { return current.left; } if (current.left == null) { return current.right; }

Di sini, kami mengembalikan anak non-null sehingga bisa ditugaskan ke node induk.

Akhirnya, kita harus menangani kasus dimana node memiliki dua anak.

Pertama, kita perlu mencari node yang akan menggantikan node yang dihapus. Kami akan menggunakan simpul terkecil dari simpul yang akan dihapus sub-pohon kanan:

private int findSmallestValue(Node root) { return root.left == null ? root.value : findSmallestValue(root.left); }

Kemudian, kami menetapkan nilai terkecil ke node untuk dihapus dan setelah itu, kami akan menghapusnya dari sub pohon kanan:

int smallestValue = findSmallestValue(current.right); current.value = smallestValue; current.right = deleteRecursive(current.right, smallestValue); return current;

Terakhir, mari buat metode publik yang memulai penghapusan dari root :

public void delete(int value) { root = deleteRecursive(root, value); }

Sekarang, mari kita periksa apakah penghapusan berfungsi seperti yang diharapkan:

@Test public void givenABinaryTree_WhenDeletingElements_ThenTreeDoesNotContainThoseElements() { BinaryTree bt = createBinaryTree(); assertTrue(bt.containsNode(9)); bt.delete(9); assertFalse(bt.containsNode(9)); }

4. Melintasi Pohon

Di bagian ini, kita akan melihat berbagai cara melintasi pohon, yang mencakup secara detail pencarian depth-first dan breadth-first.

Kami akan menggunakan pohon yang sama dengan yang kami gunakan sebelumnya dan kami akan menunjukkan urutan traversal untuk setiap kasus.

4.1. Penelusuran Kedalaman-Pertama

Penelusuran mendalam pertama adalah jenis penelusuran yang dilakukan sedalam mungkin pada setiap anak sebelum menjelajahi saudara kandung berikutnya.

Ada beberapa cara untuk melakukan penelusuran mendalam-pertama: dalam-order, pre-order dan post-order.

In-order traversal terdiri dari kunjungan pertama ke sub-pohon kiri, kemudian simpul akar, dan terakhir sub-pohon kanan:

public void traverseInOrder(Node node) { if (node != null) { traverseInOrder(node.left); System.out.print(" " + node.value); traverseInOrder(node.right); } }

Jika kita memanggil metode ini, keluaran konsol akan menampilkan traversal berurutan:

3 4 5 6 7 8 9

Traversal praorder mengunjungi simpul akar, kemudian subpohon kiri, dan terakhir subpohon kanan:

public void traversePreOrder(Node node) { if (node != null) { System.out.print(" " + node.value); traversePreOrder(node.left); traversePreOrder(node.right); } }

Dan mari kita periksa traversal pre-order di output konsol:

6 4 3 5 8 7 9

Traversal pasca-pesanan mengunjungi subtree kiri, subtree kanan, dan node root di akhir:

public void traversePostOrder(Node node) { if (node != null) { traversePostOrder(node.left); traversePostOrder(node.right); System.out.print(" " + node.value); } }

Berikut adalah node dalam post-order:

3 5 4 7 9 8 6

4.2. Pencarian Luas-Pertama

Ini adalah jenis traversal umum lainnya yang mengunjungi semua node pada suatu tingkat sebelum melanjutkan ke tingkat berikutnya .

Traversal semacam ini juga disebut urutan-tingkat dan mengunjungi semua tingkat pohon mulai dari akar, dan dari kiri ke kanan.

Untuk implementasinya, kami akan menggunakan Queue untuk menampung node dari setiap level secara berurutan. Kami akan mengekstrak setiap node dari daftar, mencetak nilainya, lalu menambahkan anaknya ke antrian:

public void traverseLevelOrder() { if (root == null) { return; } Queue nodes = new LinkedList(); nodes.add(root); while (!nodes.isEmpty()) { Node node = nodes.remove(); System.out.print(" " + node.value); if (node.left != null) { nodes.add(node.left); } if (node.right != null) { nodes.add(node.right); } } }

Dalam hal ini, urutan node adalah:

6 4 8 3 5 7 9

5. Kesimpulan

Dalam artikel ini, kita telah melihat cara mengimplementasikan pohon biner yang diurutkan di Java dan operasi yang paling umum.

Kode sumber lengkap untuk contoh tersedia di GitHub.