PRAKTIKUM ALGORITMA DAN STRUKTUR DATA MODUL KE-4 BINARY TREE & BINARY SEARCH TREE (BST)

PRAKTIKUM ALGORITMA DAN STRUKTUR DATA MODUL KE-4 BINARY TREE & BINARY SEARCH TREE (BST)

LABORATORIUM PEMROGRAMAN PROGRAM STUDI TEKNIK INFORMATIKA FAKULTAS TEKNIK UNIVERSITAS MUHAMMADIYAH MALANG 2015

Dokumen Laboratorium Teknik Informatika UMM @ 2015 – Modul Praktikum Algoritma

dan Struktur Data

I.

TUJUAN Mahasiswa mampu : 1. Memahami struktur pohon tree sebagai model penyimpanan data. 2. Memahami cara menyimpan dan mengakses elemen dari sebuah struktur pohon biner. 3. Memahami struktur pohon biner dalam versi linked list. 4. Memahami operasi-operasi standar yang terkait dengan pohon biner.

II. ALAT YANG DIGUNAKAN Peralatan yang digunakan : 1.Perangkat PC yang terinstall Java 2.Editor Java

III. DASAR TEORI 

Tree adalah kumpulan element yang saling terhubung secara hirarki (one to many). Tree terdiri dari root (akar), path (cabang), dan leaf (daun). Element pada tree yaitu berupa node. Sebuah node hanya boleh memiliki satu induk/parent. Kecuali root, tidak memiliki induk/parent. Setiap node dapat memiliki nol atau banyak cabang anak (one to many). Node yang tidak memiliki cabang anak disebut daun.



Root (Node Root) adalah node yang memiliki hirarki tertinggi, yang pertama kali dibentuk sehingga tidak memiliki parent (node induk). Penelusuran path tiap node dimulai dari root. Subtree adalah node-node lain dibawah root yang saling terhubung satu sama lain secara hirarki.



Path merupakan percabangan dari satu node ke node lainnya. Setiap node dapat memiliki lebih dari satu cabang node atau tidak sama sekali memiliki cabang.



Leaf adalah node pada tree yang terletak pada pangkal dan tidak memiliki cabang ke


dan Struktur Data

element node lainnya. Dalam artian leaf terdapat pada hirarki terbawah pada sebuah tree. 

Istilah pada Tree antara lain:

IV. PROSEDUR PELAKSANAAN Prosedur pelaksanaan praktikum adalah sebagai berikut : 1. Mahasiswa mencoba latihan yang ada pada modul praktikum 2. Mahasiswa menganalisa hasil dari program pada latihan yang telah dijalankan 3. Mahasiswa mengerjakan tugas yang diberikan 4. Mahasiswa mendemonstrasikan program yang telah dikerjakan pada dosen/assisten 5. Mahasiswa membuat laporan dari tugas yang telah dikerjakan 6. Upload laporan melalui e-labit.umm.ac.id


dan Struktur Data

V. LATIHAN PRAKTIKUM 1. Interface BinaryTree import java.lang.reflect.*; public interface BinaryTree { public boolean isEmpty(); public Object root(); public void makeTree(Object root, Object left, Object right); public BinaryTree removeLeftSubtree(); public BinaryTree removeRightSubtree(); public void preOrder(Method visit); public void inOrder(Method visit); public void postOrder(Method visit); public void levelOrder(Method visit); }

2. Class BinaryTreeNode public class BinaryTreeNode { // package visible data members Object element; BinaryTreeNode leftChild; // left subtree BinaryTreeNode rightChild; // right subtree // constructors public BinaryTreeNode() {} public BinaryTreeNode(Object theElement) {element = theElement;} public BinaryTreeNode(Object theleftChild,BinaryTreeNode therightChild) { element = theElement; leftChild = theleftChild; rightChild = therightChild; }

theElement,BinaryTreeNode

// accessor methods public BinaryTreeNode getLeftChild() {return leftChild;} public BinaryTreeNode getRightChild() {return rightChild;} public Object getElement() {return element;} // mutator methods public void setLeftChild(BinaryTreeNode theLeftChild) {leftChild = theLeftChild;} public void setRightChild(BinaryTreeNode theRightChild) {rightChild = theRightChild;} public void setElement(Object theElement) {element = theElement;} // output method public String toString() {return element.toString();} }


dan Struktur Data

3. Class LinkedBinaryTree import java.lang.reflect.*; public class LinkedBinaryTree implements BinaryTree { // instance data member BinaryTreeNode root; // root node // class data members static Method visit; // visit method to use during a traversal static Object [] visitArgs = new Object [1]; // parameters of visit method static int count; // counter static Class [] paramType = {BinaryTreeNode.class}; // type of parameter for visit static Method theAdd1; // method to increment count by 1 static Method theOutput; // method to output node element // method to initialize class data members static { try { Class lbt = LinkedBinaryTree.class; theAdd1 = lbt.getMethod("add1", paramType); theOutput = lbt.getMethod("output", paramType); } catch (Exception e) {} // exception not possible } // only default constructor available // class methods /** visit method that outputs element */ public static void output(BinaryTreeNode t) {System.out.print(t.element + " ");} /** visit method to count nodes */ public static void add1(BinaryTreeNode t) {count++;} // instance methods /** @return true iff tree is empty */ public boolean isEmpty() {return root == null;} /** @return root element if tree is not empty * @return null if tree is empty */ public Object root() {return (root == null) ? null : root.element;} /** set this to the tree with the given root and subtrees * CAUTION: does not clone left and right */ public void makeTree(Object root, Object left, Object right) { this.root = new BinaryTreeNode(root, ((LinkedBinaryTree) left).root, ((LinkedBinaryTree) right).root); } /** remove the left subtree Dokumen Laboratorium Teknik Informatika UMM @ 2015 – Modul Praktikum Algoritma

dan Struktur Data

* @throws IllegalArgumentException when tree is empty * @return removed subtree */ public BinaryTree removeLeftSubtree() { if (root == null) throw new IllegalArgumentException("tree is empty"); // detach left subtree and save in leftSubtree LinkedBinaryTree leftSubtree = new LinkedBinaryTree(); leftSubtree.root = root.leftChild; root.leftChild = null; return (BinaryTree) leftSubtree; } /** remove the right subtree * @throws IllegalArgumentException when tree is empty * @return removed subtree */ public BinaryTree removeRightSubtree() { if (root == null) throw new IllegalArgumentException("tree is empty"); // detach right subtree and save in rightSubtree LinkedBinaryTree rightSubtree = new LinkedBinaryTree(); rightSubtree.root = root.rightChild; root.rightChild = null; return (BinaryTree) rightSubtree; } /** preorder traversal */ public void preOrder(Method visit) { this.visit = visit; thePreOrder(root); } /** actual preorder traversal method */ static void thePreOrder(BinaryTreeNode t) { if (t != null) { visitArgs[0] = t; try {visit.invoke(null, visitArgs);} catch (Exception e) {System.out.println(e);} thePreOrder(t.leftChild); thePreOrder(t.rightChild); } }

// visit tree root // do left subtree // do right subtree

/** inorder traversal */ public void inOrder(Method visit) { this.visit = visit; theInOrder(root); } /** actual inorder traversal method */ static void theInOrder(BinaryTreeNode t) { if (t != null) Dokumen Laboratorium Teknik Informatika UMM @ 2015 – Modul Praktikum Algoritma

dan Struktur Data

{ theInOrder(t.leftChild); visitArgs[0] = t; try {visit.invoke(null, visitArgs);} catch (Exception e) {System.out.println(e);} theInOrder(t.rightChild);

// do left subtree // visit tree root // do right subtree

} } /** postorder traversal */ public void postOrder(Method visit) { this.visit = visit; thePostOrder(root); } /** actual postorder traversal method */ static void thePostOrder(BinaryTreeNode t) { if (t != null) { thePostOrder(t.leftChild); thePostOrder(t.rightChild); visitArgs[0] = t; try {visit.invoke(null, visitArgs);} catch (Exception e) {System.out.println(e);} } } /** level order traversal */ public void levelOrder(Method visit) { ArrayQueue q = new ArrayQueue(); BinaryTreeNode t = root; while (t != null) { visitArgs[0] = t; try {visit.invoke(null, visitArgs);} catch (Exception e) {System.out.println(e);}

// do left subtree // do right subtree // visit tree root

// visit tree root

// put t's children on queue if (t.leftChild != null) q.put(t.leftChild); if (t.rightChild != null) q.put(t.rightChild); // get next node to visit t = (BinaryTreeNode) q.remove(); } } /** output elements in preorder */ public void preOrderOutput() {preOrder(theOutput);} /** output elements in inorder */ public void inOrderOutput() {inOrder(theOutput);} Dokumen Laboratorium Teknik Informatika UMM @ 2015 – Modul Praktikum Algoritma

dan Struktur Data

/** output elements in postorder */ public void postOrderOutput() {postOrder(theOutput);} /** output elements in level order */ public void levelOrderOutput() {levelOrder(theOutput);} /** count number of nodes in tree */ public int size() { count = 0; preOrder(theAdd1); return count; } /** test program */ public static void main(String [] args) { LinkedBinaryTree a = new LinkedBinaryTree(), x = new LinkedBinaryTree(), y = new LinkedBinaryTree(), z = new LinkedBinaryTree(); y.makeTree(new Integer(1), a, a); z.makeTree(new Integer(2), a, a); x.makeTree(new Integer(3), y, z); y.makeTree(new Integer(4), x, a); System.out.println("Preorder sequence is "); y.preOrderOutput(); System.out.println(); System.out.println("Inorder sequence is "); y.inOrderOutput(); System.out.println(); System.out.println("Postorder sequence is "); y.postOrderOutput(); System.out.println(); System.out.println("Level order sequence is "); y.levelOrderOutput(); System.out.println(); System.out.println("Number of nodes = " + y.size()); } }

Output LinkedBinaryTree :


dan Struktur Data

4. Class ArrayBinaryTree public class ArrayBinaryTree { // data members static Object [] a; // array that contains the tree static int last; // position of last element in array a /** visit method that prints the element in a[i] */ public static void visit(int i) {System.out.print(a[i] + " ");} /** inorder traversal */ public static void inOrder(Object [] theArray, int theLast) { // set static data members a = theArray; last = theLast; // start the recursive traversal method at the root theInOrder(1); } /** actual method to do the inorder static void theInOrder(int i) {// traverse subtree rooted at a[i] if (i <= last && a[i] != null) {// root exists theInOrder(2 * i); // visit(i); // theInOrder(2 * i + 1); // } }

traversal */

do left subtree visit tree root do right subtree

/** test program */ public static void main(String [] args) { Integer [] a = new Integer [15]; a[1] = new Integer(1); a[2] = new Integer(2); a[5] = new Integer(5); a[10] = new Integer(10); a[11] = new Integer(11); System.out.println("The elements in inorder are"); inOrder(a, 11); System.out.println(); } }

Output ArrayBinaryTree.java


dan Struktur Data

5. Class BinarySearchTree /** binary search tree */ //package dataStructures; public class BinarySearchTree extends LinkedBinaryTree { // top-level nested class static class Data { // data members Object element; // element in node Comparable key; // its key // constructor Data(Comparable theKey, Object theElement) { key = theKey; element = theElement; } public String toString() {return element.toString();} } /** @return element with specified key * @return null if no matching element */ public Object get(Object theKey) { // pointer p starts at the root and moves through // the tree looking for an element with key theKey BinaryTreeNode p = root; Comparable searchKey = (Comparable) theKey; while (p != null) // examine p.element.key if (searchKey.compareTo(((Data) p.element).key) < 0) p = p.leftChild; else if (searchKey.compareTo(((Data) p.element).key) > 0) p = p.rightChild; else // found matching element return ((Data) p.element).element; // no matching element return null; } /** insert an element with the specified key * overwrite old element if there is already an * element with the given key * @return old element (if any) with key theKey */ public Object put(Object theKey, Object theElement) { BinaryTreeNode p = root; // search pointer BinaryTreeNode pp = null; // parent of p Comparable elementKey = (Comparable) theKey; // find place to insert theElement while (p != null) {// examine p.element.key pp = p; // move p to a child Dokumen Laboratorium Teknik Informatika UMM @ 2015 – Modul Praktikum Algoritma

dan Struktur Data

if (elementKey.compareTo(((Data) p.element).key) < 0) p = p.leftChild; else if (elementKey.compareTo(((Data) p.element).key) > 0) p = p.rightChild; else {// overwrite element with same key Object elementToReturn = ((Data) p.element).element; ((Data) p.element).element = theElement; return elementToReturn; } } // get a node for theElement and attach to pp BinaryTreeNode r = new BinaryTreeNode (new Data(elementKey, theElement)); if (root != null) // the tree is not empty if (elementKey.compareTo(((Data) pp.element).key) < 0) pp.leftChild = r; else pp.rightChild = r; else // insertion into empty tree root = r; return null; } /** @return matching element and remove it * @return null if no matching element */ public Object remove(Object theKey) { Comparable searchKey = (Comparable) theKey; // set p to point to node with key searchKey BinaryTreeNode p = root, // search pointer pp = null; // parent of p while (p != null && !((Data) p.element).key.equals(searchKey)) {// move to a child of p pp = p; if (searchKey.compareTo(((Data) p.element).key) < 0) p = p.leftChild; else p = p.rightChild; } if (p == null) // no element with key searchKey return null; // save element to be removed Object theElement = ((Data) p.element).element; // restructure tree // handle case when p has two children if (p.leftChild != null && p.rightChild != null) {// two children // convert to zero or one child case // find element with largest key in left subtree of p BinaryTreeNode s = p.leftChild, ps = p; // parent of s while (s.rightChild != null) {// move to larger element ps = s; s = s.rightChild; } Dokumen Laboratorium Teknik Informatika UMM @ 2015 – Modul Praktikum Algoritma

dan Struktur Data

// move largest element from s to p p.element = s.element; p = s; pp = ps; } // p has at most one child, save this child in c BinaryTreeNode c; if (p.leftChild == null) c = p.rightChild; else c = p.leftChild; // remove node p if (p == root) root = c; else {// is p left or right child of pp? if (p == pp.leftChild) pp.leftChild = c; else pp.rightChild = c; } return theElement; } /** output elements in ascending order of key */ public void ascend() {inOrderOutput();} // test binary search tree class public static void main(String [] args) { BinarySearchTree y = new BinarySearchTree(); // insert a few elements y.put(new Integer(1), new Character('a')); y.put(new Integer(6), new Character('c')); y.put(new Integer(4), new Character('b')); y.put(new Integer(8), new Character('d')); System.out.println("Elements in ascending order are"); y.ascend(); System.out.println(); // remove an element System.out.println("Removed element " + y.remove(new Integer(4)) + " with key 4"); System.out.println("Elements in ascending order are"); y.ascend(); System.out.println(); // remove another element System.out.println("Removed element " + y.remove(new Integer(8)) + " with key 8"); System.out.println("Elements in ascending order are"); y.ascend(); System.out.println(); // remove yet another element System.out.println("Removed element " + y.remove(new Integer(6)) Dokumen Laboratorium Teknik Informatika UMM @ 2015 – Modul Praktikum Algoritma

dan Struktur Data

+ " with key 6"); System.out.println("Elements in ascending order are"); y.ascend(); System.out.println(); // try to remove a nonexistent element System.out.println("Removed element " + y.remove(new Integer(6)) + " with key 6"); System.out.println("Elements in ascending order are"); y.ascend(); System.out.println(); } }

output class BinarySearchTree :

VI. TUGAS PRAKTIKUM 1. Tambahkan penelusuran postorder dan preorder pada program binarytree menggunakan array diatas 2. Modifikasi program binary tree yang ada pada latihan sehingga dapat digunakan untuk menyimpan nama-nama dari silsilah keluarga dan dapat mengenali pola seperti berikut : 1) Anak ke-X dari orang tua Y 2) Orang tua dari anak ke-X 3) Semua anak dari orang tua Y 4) Cucu dari orang tua Y 5) Semua anggota keluarga


dan Struktur Data

Berikut adalah gambaran bentuk tree dan gambaran hasil running program :

Sitisoni

Nina

Agus

Meri

peni

Toni

Joko

Sinta

Budi

rina

wenda

niko

lori

dina

Masukkan pilihan >> 1 Nama orang tua ? Nina Anak nomor ? 2 Anak ke-2 dari Nina adalah Meri Masukkan pilihan >> 2 Nama anak ? Wenda Orang tua dari Wenda adalah Toni Masukkan pilihan >> 3 Nama orang tua? Sinta Semua anak dari Sinta adalah Rina, Niko, Lori Masukkan pilihan >> 4 Nama orang tua? Sinta Cucu dari Sinta adalah Dina Masukkan pilihan >> 5 Semua anggota keluarga : Nina, Budi, Sinta, Joko, Agus, Meri, Toni, Rina, Niko, Lori, Peni, Wenda, Dina.


dan Struktur Data

Keterangan : 1. Tugas praktikum dikerjakan sendiri, jika ketahuan mengcopas, mencontoh, mereplika, menjiplak dll akan dikenakan sanksi nilai x ½. 2. Tidak ada demo susulan, sesuai dengan jadwal yang telah ditentukan, kecuali ada alasan yang logis dan dapat di maklumi. 3. Kriteria penilaian praktikum: a. 25% Absensi. b. 50% demo tugas. c. 25% laporan praktikum. d. Tambahan nilai (sesuai kebijakan aslab masing-masing), misal keaktifan dll. 4. Kriteria penilaian laporan: a. Menggunakan template yang sudah disediakan. b. Melampirkan hasil praktikum (latihan dan tugas modul) dan screenshot hasil programdan penjelasannya. c. Dikerjakan sendiri, jika ketahuan mengcopas, mencontoh, mereplika, menjiplak dll akan dikenakan sanksi pengosongan nilai laporan. Penting! Tetap semangat, jangan menyerah dan pasti bisa jika mau berusaha, jangan lupa juga untuk terus berdoa agar dapat mencapai hasil yang maksimal, jangan pernah takut untuk bertanya jika masih ada kebingungan yang melanda, diselingi terus berolah raga, makan yang banyak dan sehat sesuai 4 sehat 5 sempurna serta minum multivitamin agar tetap bugar :D,


dan Struktur Data

PRAKTIKUM ALGORITMA DAN STRUKTUR DATA MODUL KE-4 BINARY TREE & BINARY SEARCH TREE (BST)

Recommend Documents