Download - Laporan Praktikum Resmi - Tree 1
-
5/19/2018 Laporan Praktikum Resmi - Tree 1
1/16
LAPORAN PRAKTIKUM RESMI
ALGORITMA STRUKTUR DATA II
TREE
Disusun oleh :
Velisia Puspita Devi
201301023
Dosen pengampu :
Yosef Murya Kusuma Ardhana.S.T., M.Kom
JURUSAN SISTEM INFORMASI
SEKOLAH TINGGI ILMU KOMPUTER YOS
SUDARSO
PURWOKERTO
2014
-
5/19/2018 Laporan Praktikum Resmi - Tree 1
2/16
2
BAB I
LANDASAN TEORI
1. Pengantar
Tree merupakan struktur data non linear. Struktur data dalam
bentuk pohon (tree) dapat diartikan sebuah struktur data yang secara
bentuk menyerupai sebuah pohon, yang terdiri dari serangkaian simpul
atau nodeyang saling berhubungan.
Simpul-simpul atau nodetersebut dihubungkan oleh sebuah vektor.
Setiap simpul dapat memiliki 0 atau lebih nodeanak (child). Sebuah node
yang memiliki nodeanak disebut nodeinduk (parent).
Sebuah node anak hanya memiliki satu node induk. Sesuai
konvensi ilmu komputer, treebertumbuh ke bawah, dengan demikian node
anak akan digambarkan berada di bawah nodeinduknya.
Node yang berada di pangkal tree disebut node akar (root),
sedangkan node yang berada di paling ujung pada piramida tree disebut
nodedaun (leaf).
A. Struktur Tree
Semua bulatan disebut simpul (node).
NodeG adalah nodeindukdari H, I, J.
NodeH, I, J adalah nodeanakdari G.
-
5/19/2018 Laporan Praktikum Resmi - Tree 1
3/16
3
Akar (root) adalah simpul yang tidak memiliki superordinat. Untuk
pohon yang dicontohkan di atas, maka rootadalah nodeA.
Daun (leaf) adalah simpul yang tidak memiliki subordinat. Untuk
pohon diatas dicontohkan diatas, maka leafadalah nodeD, E, F, H, I, J.
a. Superordinat dan Subordinat
NodeB merupakan superordinat nodeE dan nodeF.
NodeE dan F mempunyai superordinat yang sama, yaitu nodeB.
NodeB mempunyai subordinat, yaitu nodeE (node) dan F (node).NodeE dan nodeF merupakan subordinat simpul B.
b. Tingkat (Level) dan Kedalaman (Depth)
- Tingkat (level)
Root dinyatakan berada pada level 0 (namun ada juga
dibeberapa buku literatur lain menyebutnya level 1).
-
5/19/2018 Laporan Praktikum Resmi - Tree 1
4/16
4
- Kedalaman (depth)
Treeyang mempunyai posisi paling atas atau level teratas.
c. Derajat (Degree) Sebuah Node
Degree pada sebuah node menyatakan jumlah subordinat dari node
tersebut.
Untuk treeyang dicontohkan pada gambar diatas :
NodeA : degree= 3.
NodeB : degree= 2.
NodeC : degree= 0.
NodeD : degree= 3.
B. Pohon Biner (BinaryTree)
Pohon Biner adalah sebuah tree yang pada masing-masing
simpulnya hanya dapat memiliki maksimum 2 simpul anak, tidak boleh
lebih. Pada pohon biner umumnya kedua nodeanak (child) disebut dengan
posisinya, yaitu subordinat kiri (left child) dan subordinat kanan (right
child).
Ada banyak cara dalam mengilustrasikan struktur sebuah node
binary tree, namum yang paling umum adalah ilustrasi seperti pada
gambar di bawah ini.
Left Right
INFO
-
5/19/2018 Laporan Praktikum Resmi - Tree 1
5/16
5
a. Pohon Biner dengan Depth 3
Ilustrasi gambar di bawah ini merupakan contoh dari pohon biner
dengan depth = 3.
b. StriclyBinaryTree
StriclyBinary Tree adalah pohon biner yang semua node-nya
(kecuali simpul leaf) mempunyai lengkap node subordinat kiri dan node
subordinat kanan.
c. Complete Binary Tree
Complete Binary Tree dengan depth = d adalah pohon binerstricly
binary tree, dimana semua leaf hanya berada pada level d. Maka, pada
completely binary tree berlaku:
Pada level k jumlah node
n=2^k
Untuk tree dengan depth d, maka jumlah node
n=2^(d+1)-1
Untuk tree dengan depth d, maka jumlah node leaf
C
F
A
B
D E G
-
5/19/2018 Laporan Praktikum Resmi - Tree 1
6/16
6
n=2^d
Untuk tree dengan depth d, maka jumlah node bukan leafn=(2^d)-1
Bila jumlah seluruh node=n, maka depth tree adalah
d=log2(n+1)-1
Complete Binary Tree dengan depth = d, memiliki cirri-ciri:
Setiap node yang berada di bawah d-1, memiliki 2 subordinat.
Jika pada level d-1 subtree kanan ada node yang mempunyai
subordinat, maka setiap node pada level d-1 subtree kiri harus
memiliki subordinat kiri dan kanan.
d. Balance Binary Tr ee
Balance Binary Tree atau pohon biner seimbang atau biasa disebut
dengan pohon AVL adalah pohon biner dengan ketinggiansubtree kiri dan
subtree kanan untuk setiap node superordinat paling banyak selisih 1.
AVL Tree muncul untuk menyeimbangkanBinary Search Tree . Dengan
AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan
disederhanakan.
Selain AVL Tree, terdapat pula Height Balanced and Tree, yakni
Binary Search Tree yang memiliki perbedaan level antarasubtree kiri dan
subtree kanan maksimal adalah n. Sehingga AVL Tree adalah Height
Balanced 1 Tree.
Untuk mempermudah menyeimbangkan tree, maka digunakan
simbol-simbol bantu.
- (tanda minus) : digunakan apabilasubtree kiri lebih panjang dari
subtree kanan.
+ (tanda plus) : digunakan apabilasubtree kanan lebih panjang
darisubtree kiri.
0 (nol) : digunakan apabilasubtree kanan dansubtree kiri
memiliki height yang sama.
-
5/19/2018 Laporan Praktikum Resmi - Tree 1
7/16
7
BAB II
PENJELASAN PROGRAM
1. Latihan Praktikum
Pada bab ini akan membahas tentang listing program yang telah
digunakan untuk latihan pada pertemuan pertama. Latihan yang dilakukan
mencakup pada Listing Program Tree.
Listing Program Tree
/** Program-Tree(Baru).cpp
*
* Created on: Sep 12, 2014* Author: home
*/
#include
usingnamespacestd;
structnode{
intdata;node*kiri;
node*kanan;
};
voidtambah(node**root, intdatabaru){
if((*root)==NULL){
node*baru;baru=newnode;baru->data=databaru;
baru->kiri=NULL;baru->kanan=NULL;
(*root)=baru;(*root)->kiri=NULL;
(*root)->kanan=NULL;
cout
-
5/19/2018 Laporan Praktikum Resmi - Tree 1
8/16
8
elseif(databaru>(*root)->data)
tambah(&(*root)->kanan, databaru);
elseif(databaru==(*root)->data)
coutkiri);
coutkanan);
}}
voidpostorder(node*root)
{if(root !=NULL){
postorder(root->kiri);
postorder(root->kanan);
cout
-
5/19/2018 Laporan Praktikum Resmi - Tree 1
9/16
9
switch(pil){
case1 : coutdata;
tambah(&pohon, data);break;
case2 : if(pohon !=NULL)
{preorder(pohon);
}
else
{cout
-
5/19/2018 Laporan Praktikum Resmi - Tree 1
10/16
10
-
5/19/2018 Laporan Praktikum Resmi - Tree 1
11/16
11
Penjelasan Program Tree
1. #include merupakan pengarah preprocessor yang berfungsi untuk
menginstruksikan compiler untuk menyertakan berkas C++ sebelum di
compile.
-
5/19/2018 Laporan Praktikum Resmi - Tree 1
12/16
12
2.
adalah sebuah library yang berfungsi untuk memanggil library
C++. Library iostream berfungsi untuk input dan output (cin dan cout).
3. Using namespace std merupakan standart device.
4.
main merupakan badan fungsi atau fungsi utama.
5. Struct merupakan struktur atau class.
6. Return 0 merupakan nilai balik suatu fungsi.
7. Statement do-while digunakan untuk perulangan, agar lebih efisien.
8. Void tambah berfungsi untuk menambah node.
9. Void preorder berfungsi untuk menampilkan data yang telah ditambahkan
dalam suatu node akar (root) dan node daun (leaf).
10.Void inorder berfungsi untuk menampilkan data yang telah ditambahkan.
11.Void postorder berfungsi untuk menampilkan data. Data yang ditampilkan
pertama yaitu data yang paling terakhir ditambahkan (FIFO).
12.tambah(&pohon, data) merupakan pemanggilan prosedur tambah pada
main program atau program utama.
13.
preorder(pohon) merupakan pemanggilan prosedur preorder pada main
program atau program utama.
14.inorder(pohon) adalah pemanggilan prosedur inorder pada main program
atau program utama.
15.struct node
{
int data;
node *kiri;
node *kanan;
};
Merupakan listing program yang memberikan perintah atau berfungsi
untuk membuat node baru. Node yang dibuat berupa left dan right node.
Dimana tipe datanya adalah integer atau bilangan bulat, karena data yang
diinputkan berupa angka.
16.if((*root) == NULL)
{
-
5/19/2018 Laporan Praktikum Resmi - Tree 1
13/16
13
node *baru;
baru = new Node;
baru->data = databaru;
baru->kiri = NULL;
baru->kanan = NULL;
(*root) = baru;
(*root)->kiri = NULL;
(*root)->kanan = NULL;
cout (*root)->data)
else if(databaru == (*root)->data)
tambah(&(*root)->kiri,databaru)
tambah(&(*root)->kanan,databaru);
cout
-
5/19/2018 Laporan Praktikum Resmi - Tree 1
14/16
14
19.
Switch(pil) merupakan statement penggunaan swtichcase pada main
program.
20.node *pohon;
pohon = NULL;
adalah proses inisialisasi pada node dalam program tree.
-
5/19/2018 Laporan Praktikum Resmi - Tree 1
15/16
15
BAB III
KESIMPULAN
Dari program di atas, coding program dapat dijalankan di Borland C++,
tetapi tidak dapat dijalankan (terdapat eror) di Eclipse C++. Beberapa syntax
harus dihapus atau diganti. Contohnya getch(), clrscr(), #include ,
#include , *t, c, void main, return 0, using namespace std dan lain-lain.
Untuk library #include dalam Eclipse C++ bisa diganti dengan library
#include , karena menggunakan cin dan cout bukan printf dan scanf.
Untuk library #include , dalam Eclipse tidak perlu disertakan.
Dalam Eclipse, getch() dan clrscr() tidak bisa digunakan. Perintah atau
syntax tersebut hanya bisa digunakan dalam Borland yang fungsinya untuk
mengakhiri sebuah program dan untuk menghapus layar. Untuk *t dan c, tidak
perlu diinisialisasikan atau dideklarasikan dalam program, karena *t dan c tidak
digunakan di dalam maupun diluar main program. Selain itu, di dalam Eclipse,
harus menyertakan using namespace std. Fungsi dari syntax tersebut sebagai
standar device. Jika coding atau listing program sudah benar, tetapi tidak
menyertakan using namespace std, maka program tidak dapat dijalankan (eror).
Selain dari syntax atau listing program yang sudah dijelaskan di atas,
terdapat pula syntax atau listing program yang perlu diubah. Contohnya tipe dari
fungsi main. Untuk fungsi void main() pada main program, bisa diganti atau
diubah menjadi main() atau int main(). Fungsi tersebut akan berpengaruh pada
nilai balik. Sehingga nilai balik pada main program tergantung pada fungsi main
program. Contohnya pada hasil output program di atas. Nilai fungsi balik tertulis
return 0, yang artinya tidak terdapat nilai.
-
5/19/2018 Laporan Praktikum Resmi - Tree 1
16/16
16
BAB IV
DAFTAR PUSTAKA
Ardhana, YM Kusuma. 2013. Struktur Data dalam Ilustrasi Eclips Indigo C ++.
Yogyakarta: CAPS (Center of Academic Publishing Service).
Kristanto, Andri. 2003. Struktur Data Dengan C++. Yogyakarta: Graha Ilmu.
Kadir, Abdul. 2012. Buku Pintar C++ untuk Pemula. Jakarta: MediaKom