IKI 20100: Struktur Data & Algoritma 2007/2008 Semester Ganjil Tugas 2: Mencetak tree dalam file XML Pada tugas ini anda diminta untuk membuat program yang dapat mencetak isi sebuah tree ke file dengan penataan yang rapi dan terstruktur. Informasi mengenai bentuk dan isi sebuah tree akan dibaca dari sebuah file XML. XML (eXtensible Markup Language)1 adalah sebuah format standar untuk menyimpan informasi yang kini sangat banyak digunakan di industri, dan bisa dikatakan merupakan contoh baik pengaplikasian struktur data tree yang sudah kita pelajari di kuliah. Untuk membantu anda, di SCeLE tersedia sebuah program yang sudah mendefinisikan struktur data binary node dan binary tree, serta cara untuk membaca sebuah file XML. Tugas ini terdiri dari dua bagian. Pada bagian pertama, anda diminta untuk melengkapi program yang sudah diberikan agar ia dapat mencetak isi binary tree sesuai ketentuan di bawah. Pada bagian kedua, anda diminta untuk membuat class-class baru sehingga anda dapat membaca dan mencetak isi tree pada umumnya, yaitu tree yang boleh memiliki n anak, n ≥ 0.
1
Bagian 1: Mencetak isi binary tree
Setiap node dalam binary tree memiliki sebuah String yang harus dicetak. Peraturan yang harus ditaati adalah sebagai berikut: • Isi node root selalu dicetak pada baris pertama, dan dimulai pada awal baris. • Setiap node yang isinya dicetak harus diikuti oleh isi subtree kirinya, lalu diikuti oleh isi subtree kanannya. Isi node anak kiri dan anak kanan selalu dicetak dengan jarak indentasi 5 karakter ke kanan dibandingkan parent-nya. • Sebuah subtree kosong dinyatakan dengan mencetak string “[NULL]”. • Harus ada tepat satu baris yang dilongkap antara setiap baris yang berisi isi node. • Harus terbentuk garis yang menghubungkan sebuah node dengan kedua anak kiri dan kanannya dengan menggunakan untaian karakter garis tegaklurus (‘|’), strip (‘-’), dan simbol plus (‘+’). Agar lebih jelas, lihat contoh di bawah. Sebagai contoh, perhatikan gambar binary tree berikut:
Program yang anda buat harus bisa mencetak isi tree ini sesuai dengan ketentuan-ketentuan di atas, sehingga menghasilkan output sebagai berikut: 1 http://en.wikipedia.org/wiki/Xml
1
salak | +----rambutan | | | +----jeruk | | | | | +----[NULL] | | | | | +----manggis | | | | | +----[NULL] | | | | | +----[NULL] | | | +----apel | | | +----[NULL] | | | +----[NULL] | +----durian | +----mangga | | | +----nangka | | | | | +----[NULL] | | | | | +----[NULL] | | | +----[NULL] | +----pisang | +----[NULL] | +----[NULL]
Anda diberikan sekumpulan file .java di dalam package iki20100.tugas2 sebagai berikut: • BinaryTree.java: class ini mendefinisikan sebuah binary tree. • BinaryTreeNode.java: class ini mendefinisikan sebuah node pada binary tree. • XMLTreeBuilder.java: class ini menyediakan fasilitas untuk me-load sebuah BinaryTree dari sebuah file XML. Untuk bagian pertama ini, anda belum perlu memusingkan diri dengan class XMLTreeBuilder. Anda hanya perlu tahu bahwa ia menyediakan sebuah static method sebagai berikut: public static BinaryTree loadBinaryTree(String filename) Jika diberikan pathname sebuah file XML yang berisi definisi binary tree, ia akan mengembalikan instantiation BinaryTree yang sesuai, misalnya: BinaryTree treeKu = XMLTreeBuilder.loadBinaryTree("c:/dataku/sda/binarytree1.xml"); Pada class BinaryTree, terdapat method sebagai berikut: public void cetakSaya(String filename) Definisi method ini masih kosong, jadi anda harus melengkapinya agar ia dapat mencetak isi BinaryTree tersebut ke dalam file yang pathname-nya adalah parameter yang diberikan, misalnya: treeKu.cetakSaya("c:/dataku/sda/binarytree1.txt"); Jika dirasa perlu, anda juga boleh menambahkan method lain, baik di class BinaryTree maupun BinaryTreeNode. 2
2
Bagian 2: Membaca dan mencetak tree umum
Setelah berhasil menyelesaikan bagian pertama di atas, pada bagian kedua ini anda diminta untuk membuat generalisasi dari program di atas, sehingga dapat dihasilkan program yang mencetak isi sebuah tree yang tidak harus bersifat binary tree, atau boleh memiliki n anak, n ≥ 0. Peraturan yang harus ditaati sangat mirip dengan peraturan untuk binary tree di atas, namun ada sedikit perbedaan: • Isi node root selalu dicetak pada baris pertama, dan dimulai pada awal baris. • Setiap node yang isinya dicetak harus diikuti oleh isi semua subtree-nya, dimulai dengan anak pertama, anak kedua, anak ketiga, dan seterusnya. Isi node anak selalu dicetak dengan jarak indentasi 5 karakter ke kanan dibandingkan parent-nya. • Subtree kosong tidak dicetak sama sekali. • Harus ada tepat satu baris yang dilongkap antara setiap baris yang berisi isi node. • Harus terbentuk garis yang menghubungkan sebuah node dengan semua anak-anaknya dengan menggunakan untaian karakter garis tegaklurus (‘|’), strip (‘-’), dan simbol plus (‘+’). Agar lebih jelas, lihat contoh di bawah. Sebagai contoh, perhatikan gambar binary tree berikut:
Program yang anda buat harus bisa mencetak isi tree ini sesuai dengan ketentuan-ketentuan di atas, sehingga menghasilkan output sebagai berikut: salak | +----rambutan | | | +----jeruk | | | | | +----manggis | | | | | +----kedondong | | | | | +----gandaria | | | +----apel | +----durian | | | +----mangga | | | | | +----nangka | | | +----pisang | +----nanas
Untuk bagian kedua ini, anda harus melakukan hal-hal berikut: • Buatlah class Tree dan TreeNode yang mendefinisikan tree dan node pada tree di mana sebuah node bisa memiliki n anak, n ≥ 0. Anda dapat menghasilkan kedua class ini dengan sedikit memodifikasi class BinaryTree dan BinaryTreeNode yang sudah ada. 3
• Pada class Tree, buatlah method sebagai berikut: public void cetakSaya(String filename) Seperti halnya pada BinaryTree, method ini harus dapat mencetak isi Tree tersebut ke dalam file yang pathname-nya adalah parameter yang diberikan, misalnya: treeKu.cetakSaya("c:/dataku/sda/tree1.txt"); Jika dirasa perlu, anda juga boleh menambahkan method lain, baik di class Tree maupun TreeNode. • Tambahkan sebuah static method pada class XMLTreeBuilder dengan signature sebagai berikut: public static Tree loadTree(String filename) Jika diberikan pathname sebuah file XML yang berisi definisi tree, method ini harus mengembalikan instantiation Tree yang sesuai, misalnya: Tree treeKu = XMLTreeBuilder.loadTree("c:/dataku/sda/tree1.xml");
3
Format file XML
XML (eXtensible Markup Language) adalah sebuah format standar untuk menyimpan informasi dalam sebuah file. Pada dasarnya, sebuah file XML adalah text file biasa, di mana sepotong teks dapat diawali oleh opening tag dan diakhiri oleh closing tag, dan disebut sebagai elemen. Sebuah elemen dapat terletak di dalam elemen lain yang lebih besar, dan hal ini berarti bahwa sebuah file XML bisa dianggap merepresentasikan informasi yang memiliki struktur tree. Setiap file XML memiliki tepat satu buah root element (kadang disebut document element. Jika membutuhkan informasi lebih banyak mengenai XML, silahkan cari di Google (ada banyak sekali website dengan informasi lengkap mengenai XML).
3.1
Format file binary tree
Untuk file XML yang berisi binary tree pada bagian pertama tugas ini, digunakan ketentuan sebagai berikut: • Setiap elemen memiliki atribut dengan nama data, yang berisi sebuah string. • Setiap elemen dapat memiliki tepat satu elemen left dan tepat satu elemen right. • Elemen teratas diberi nama root. Contohnya, file binarytree1.xml berikut mendefinisikan binary tree yang digunakan sebagai contoh pada bagian pertama di atas:
4
3.2
Format file tree
Untuk file XML yang berisi tree pada bagian kedua tugas ini, digunakan ketentuan sebagai berikut: • Setiap elemen memiliki atribut dengan nama data, yang berisi sebuah string. • Setiap elemen dapat memiliki nol atau lebih elemen node. • Elemen teratas juga diberi nama node. Contohnya, file tree1.xml berikut mendefinisikan tree yang digunakan sebagai contoh pada bagian kedua di atas: <node data="salak"> <node data="rambutan"> <node data="jeruk"> <node data="manggis"/> <node data="kedondong"/> <node data="gandaria"/> <node data="apel"/> <node data="durian"> <node data="mangga"> <node data="nangka"/> <node data="pisang"/> <node data="nanas"/>
4
Command-line parameter
Program anda tidak perlu mengimplementasikan sebuah user interface yang interaktif, melainkan cukup menyediakan fasilitas di mana ia dapat menerima nama file input dan output melalui command-line parameter sebagai berikut: java BinaryTree <pathname file input> <pathname file output> java Tree <pathname file input> <pathname file output> Contohnya, jika program anda dijalankan dengan memanggil perintah java Tree tree1.xml tree1.txt maka program anda akan membaca file input seperti terdefinisi di atas dan menulis isinya secara rapi seperti terdefinisi pada bagian kedua. Perhatikan definisi method main pada class BinaryTree.
5
Catatan dan informasi tambahan • Untuk mengimplementasikan class TreeNode, coba pikirkan ADT apa yang paling cocok untuk merepresentasikan sejumlah anak dari node tersebut? • Class XMLTreeBuilder menggunakan fasilitas memroses file XML yang sudah disediakan oleh Java. Hanya dengan mempelajari source code-nya, anda mungkin sudah cukup mendapatkan pengertian untuk bisa mengerjakan bagian kedua tugas ini. Pada dasarnya, method private static Document parseFile(String filename) membaca sebuah file XML dan menghasilkan sebuah object org.w3c.dom.Document. Object ini berisi sebuah struktur data tree, di mana setiap node merepresentasikan sebuah komponen di dalam file XML. Node yang menyatakan elemen-elemen XML (misalnya,
) adalah instance object org.w3c.dom.Element. Pelajari method buildBinaryTree yang secara rekursif menghasilkan sebuah BinaryTree berdasarkan informasi dalam sebuah Element XML, dan method-method getChild dan getChildren yang mengembalikan Element dengan nama tag yang spesifik. 5
• Berilah komentar yang sejelas mungkin pada program anda. Jadikan komentar yang sudah ada sebagai pedoman. Lihatlah dokumentasi API Java yang tersedia di https://telaga.cs.ui.ac.id/WebKuliah/IKI20100/docs/api untuk contoh dokumentasi yang baik. • Anda TIDAK diperbolehkan menjiplak program lain, baik dari teman atau sumber lain, tanpa mengerti konsep isinya dan bagaimana cara kerjanya. Tentunya anda boleh mendiskusikan tugas ini dengan peserta kuliah lainnya, tetapi program yang anda submit harus merupakan hasil kerja anda sendiri. Peserta yang terbukti men-submit hasil pekerjaan orang lain akan mendapatkan hukuman keras.
6
Komponen penilaian • Kebenaran program (output benar untuk test case yang diuji): 40% • Kaidah-kaidah pemrograman (modularitas, rekursif, penggunaan generics): 20% • Komentar dan dokumentasi program (kejelasan dokumentasi): 40%
7
Pengumpulan tugas
Yang perlu dikumpulkan adalah file source code BinaryTree.java, BinaryTreeNode.java, Tree.java, TreeNode.java, dan XMLTreeBuilder.java, diletakkan dalam subdirectory yang sesuai dengan spesifikasi package-nya (iki20100.tugas2). Gabungkan semua file di atas ke dalam sebuah arsip ZIP yang diberi nama NPM anda, mis: 0606123456.zip. Batas akhir pengumpulan tugas adalah jam 16:00, hari Rabu, 14 November 2007. Pengumpulan dilakukan melalui SCeLE (untuk detail-nya, lihat homepage kuliah Struktur Data & Algoritma di SCeLE). Selamat bekerja!
6
