Cara Mencetak Diagram Pohon Biner

1. Perkenalan

Pencetakan adalah teknik visualisasi yang sangat umum untuk struktur data. Ini bisa menjadi rumit dalam hal pohon, karena sifat hierarkinya.

Dalam tutorial ini, kita akan mempelajari beberapa teknik pencetakan untuk Binary Trees di Java.

2. Diagram Pohon

Terlepas dari batasan menggambar dengan hanya karakter di konsol, ada banyak bentuk diagram yang berbeda untuk mewakili struktur pohon. Memilih salah satunya sangat bergantung pada ukuran dan keseimbangan pohon.

Mari kita lihat beberapa kemungkinan jenis diagram yang dapat kita cetak:

Tapi, kami akan menjelaskan yang praktis yang juga lebih mudah untuk diterapkan. Dengan memperhatikan arah pertumbuhan pohon, kita dapat menyebutnya sebagai pohon horizontal :

Karena pohon horizontal mengalir selalu ke arah yang sama dengan aliran teks , kami memiliki beberapa keuntungan untuk memilih diagram horizontal di atas yang lain:

  1. Kita juga bisa membayangkan pohon yang besar dan tidak seimbang
  2. Panjang nilai node tidak mempengaruhi struktur tampilan
  3. Jauh lebih mudah untuk diterapkan

Oleh karena itu, kita akan menggunakan diagram horizontal dan menerapkan kelas printer pohon biner sederhana di bagian selanjutnya.

3. Model Pohon Biner

Pertama-tama, kita harus memodelkan pohon biner dasar yang dapat kita lakukan hanya dengan beberapa baris kode.

Mari kita definisikan kelas BinaryTreeModel sederhana :

public class BinaryTreeModel { private Object value; private BinaryTreeModel left; private BinaryTreeModel right; public BinaryTreeModel(Object value) { this.value = value; } // standard getters and setters } 

4. Contoh Data Uji

Sebelum kita mulai menerapkan printer pohon biner kita, kita perlu membuat beberapa contoh data untuk menguji visualisasi kita secara bertahap:

BinaryTreeModel root = new BinaryTreeModel("root"); BinaryTreeModel node1 = new BinaryTreeModel("node1"); BinaryTreeModel node2 = new BinaryTreeModel("node2"); root.setLeft(node1); root.setRight(node2); BinaryTreeModel node3 = new BinaryTreeModel("node3"); BinaryTreeModel node4 = new BinaryTreeModel("node4"); node1.setLeft(node3); node1.setRight(node4); node2.setLeft(new BinaryTreeModel("node5")); node2.setRight(new BinaryTreeModel("node6")); BinaryTreeModel node7 = new BinaryTreeModel("node7"); node3.setLeft(node7); node7.setLeft(new BinaryTreeModel("node8")); node7.setRight(new BinaryTreeModel("node9"));

5. Printer Pohon Biner

Tentu saja, kami memerlukan kelas terpisah untuk menjaga BinaryTreeModel kami tetap bersih demi Prinsip Tanggung Jawab Tunggal.

Sekarang, kita dapat menggunakan Pola Pengunjung sehingga pohon menangani hierarki dan printer hanya menangani pencetakan. Tetapi untuk tutorial ini, kami akan menyatukannya agar tetap sederhana.

Jadi, kami mendefinisikan kelas bernama BinaryTreePrinter dan mulai mengimplementasikannya.

5.1. Pre-Order Traversal

Mempertimbangkan diagram horizontal kita, untuk mencetaknya dengan benar, kita dapat membuat awal sederhana dengan menggunakan traversal pre-order .

Akibatnya, untuk melakukan penjelajahan pra-pemesanan, kita perlu mengimplementasikan metode rekursif yang pertama mengunjungi simpul akar, kemudian subpohon kiri, dan terakhir subpohon kanan.

Mari tentukan metode untuk melintasi pohon kita:

public void traversePreOrder(StringBuilder sb, BinaryTreeModel node) { if (node != null) { sb.append(node.getValue()); sb.append("\n"); traversePreOrder(sb, node.getLeft()); traversePreOrder(sb, node.getRight()); } } 

Selanjutnya, mari tentukan metode cetak kita:

public void print(PrintStream os) { StringBuilder sb = new StringBuilder(); traversePreOrder(sb, this.tree); os.print(sb.toString()); } 

Jadi, kami cukup mencetak pohon uji kami:

new BinaryTreePrinter(root).print(System.out); 

Outputnya adalah daftar node pohon dalam urutan yang dilalui:

root node1 node3 node7 node8 node9 node4 node2 node5 node6 

5.2. Menambahkan Tepi Pohon

Untuk mengatur diagram kami dengan benar, kami menggunakan tiga jenis karakter “├──”, “└──”, dan “│” untuk memvisualisasikan node. Dua yang pertama adalah untuk penunjuk dan yang terakhir untuk mengisi tepi dan menghubungkan penunjuk.

Mari perbarui metode traversePreOrder kita , tambahkan dua parameter sebagai padding dan pointer , dan gunakan karakter masing-masing:

public void traversePreOrder(StringBuilder sb, String padding, String pointer, BinaryTreeModel node) { if (node != null) { sb.append(padding); sb.append(pointer); sb.append(node.getValue()); sb.append("\n"); StringBuilder paddingBuilder = new StringBuilder(padding); paddingBuilder.append("│ "); String paddingForBoth = paddingBuilder.toString(); String pointerForRight = "└──"; String pointerForLeft = (node.getRight() != null) ? "├──" : "└──"; traversePreOrder(sb, paddingForBoth, pointerForLeft, node.getLeft()); traversePreOrder(sb, paddingForBoth, pointerForRight, node.getRight()); } } 

Selain itu, kami juga memperbarui metode cetak :

public void print(PrintStream os) { StringBuilder sb = new StringBuilder(); traversePreOrder(sb, "", "", this.tree); os.print(sb.toString()); } 

Jadi, mari kita uji BinaryTreePrinter kami lagi:

Jadi, dengan semua bantalan dan penunjuk, diagram kita telah terbentuk dengan baik.

Namun, kami masih memiliki beberapa baris tambahan untuk dihilangkan:

Saat kita melihat diagram, masih ada karakter di tiga tempat yang salah:

  1. Kolom baris ekstra di bawah simpul akar
  2. Garis ekstra di bawah subtree kanan
  3. Garis ekstra di bawah subtree kiri yang tidak memiliki saudara kanan

5.3. Implementasi yang Berbeda untuk Root dan Child Nodes

Untuk memperbaiki garis ekstra, kita dapat membagi metode traverse kita. Kami akan menerapkan satu perilaku ke simpul akar dan satu lagi untuk simpul anak.

Mari menyesuaikan traversePreOrder hanya untuk node root:

public String traversePreOrder(BinaryTreeModel root) { if (root == null) { return ""; } StringBuilder sb = new StringBuilder(); sb.append(root.getValue()); String pointerRight = "└──"; String pointerLeft = (root.getRight() != null) ? "├──" : "└──"; traverseNodes(sb, "", pointerLeft, root.getLeft(), root.getRight() != null); traverseNodes(sb, "", pointerRight, root.getRight(), false); return sb.toString(); } 

Selanjutnya, kita akan membuat metode lain untuk simpul anak sebagai traverseNodes. Selain itu , kami akan menambahkan parameter baru hasRightSibling untuk mengimplementasikan baris sebelumnya dengan benar:

public void traverseNodes(StringBuilder sb, String padding, String pointer, BinaryTreeModel node, boolean hasRightSibling) { if (node != null) { sb.append("\n"); sb.append(padding); sb.append(pointer); sb.append(node.getValue()); StringBuilder paddingBuilder = new StringBuilder(padding); if (hasRightSibling) { paddingBuilder.append("│ "); } else { paddingBuilder.append(" "); } String paddingForBoth = paddingBuilder.toString(); String pointerRight = "└──"; String pointerLeft = (node.getRight() != null) ? "├──" : "└──"; traverseNodes(sb, paddingForBoth, pointerLeft, node.getLeft(), node.getRight() != null); traverseNodes(sb, paddingForBoth, pointerRight, node.getRight(), false); } } 

Selain itu, kami membutuhkan sedikit perubahan dalam metode cetak kami :

public void print(PrintStream os) { os.print(traversePreOrder(tree)); } 

Akhirnya, diagram kami telah terbentuk menjadi bentuk yang bagus dengan hasil yang bersih:

6. Kesimpulan

Pada artikel ini, kami mempelajari cara sederhana dan praktis untuk mencetak Pohon Biner di Java .

Semua contoh artikel ini dan kasus pengujian tambahan tersedia di GitHub.