laporan struktur data tree

BAB I

PENDAHULUAN

1.1 Latar Belakang Masalah

Struktur pohon (tree) biasanya digunakan untuk menggambarkan hubungan yang bersifat hirarkis secara elemen- elemen yang ada. Contoh penggunaan struktur pohon :

Silsilah keluarga Hasil pertandingan yang berbentuk turnamen Striktur organisasi dari sebuah perusahaan

Dalam ilmu komputer, tree adalah sebuah struktur data yang secara bentuk menyerupai sebuah pohon, yang terdiri dari serangkaian node (simpul) yang saling berhubungan. Node-node tersebut dihubungkan oleh sebuah vektor. Setiap node dapat memiliki 0 atau lebih node anak (child). Sebuah node yang memiliki node anak disebut node induk (parent). Sebuah node anak hanya memiliki satu node induk. Sesuai konvensi ilmu komputer, tree bertumbuh ke bawah, tidak seperti pohon di dunia nyata yang tumbuh ke atas. Dengan demikian node anak akan digambarkan berada di bawah node induknya.

Mahasiswa sebagai modal dasar pembangunan diharapkan memiliki kemampuan dan pemahaman dalam menciptakan program yang saat ini dituntut untuk mampu menguasai bahasa pemrograman, misalnya bahasa C++. Tree merupakan salah satu struktur data yang paling penting, karena banyak aplikasi menggunakan informasi dan data yang secara alami memiliki struktur hirarkis berguna dalam membantu memecahkan banyak masalah algoritmis dalam kehidupan sehari- hari.

1.2 Rumusan Masalah

Rumusan masalah yang akan dibahas dalam laporan ini adalah bagaimana menciptakan suatu algoritma tree yang selanjutnya dapat diimplementasikan dalam bahasa pemograman C++.

1.3 Maksud dan Tujuan

Adapun maksud dan tujuan dari pembuatan laporan ini adalah sebagai berikut :

a. Sebagai bahan terapan dari teori- teori yang telah dipraktekkan dan dipelajari dalam mata kuliah struktur data khususnya pembahasan tentang tree.

b. Untuk lebih memahami bagaimana komputer mampu mengerjakan perintah yang dimasukkan dan memahami logika jalannya program.

c. Sebagai syarat untuk mendapatkan nilai akhir semester dari mata kuliah praktek struktur data.

1

BAB II

DASAR TEORI

2.1 Pengantar Bahasa C++

Tahun 1978, Brian W. Kerninghan & Dennis M. Ritchie dari AT & T Laboratories mengembangkan bahasa B menjadi bahasa C. Bahasa B yang diciptakan oleh Ken Thompson sebenarnya merupakan pengembangan dari bahasa BCPL ( Basic Combined Programming Language ) yang diciptakan oleh Martin Richard.

Sejak tahun 1980, bahasa C banyak digunakan pemrogram di Eropa yang sebelumnya menggunakan bahasa B dan BCPL. Dalam perkembangannya, bahasa C menjadi bahasa paling populer diantara bahasa lainnya, seperti PASCAL, BASIC, FORTRAN.

Tahun 1989, dunia pemrograman C mengalami peristiwa penting dengan dikeluarkannya standar bahasa C oleh American National Standards Institute (ANSI). Bahasa C yang diciptakan Kerninghan & Ritchie kemudian dikenal dengan nama ANSI C.

Mulai awal tahun 1980, Bjarne Stroustrup dari AT & T Bell Laboratories mulai mengembangkan bahasa C. Pada tahun 1985, lahirlah secara resmi bahasa baru hasil pengembangan C yang dikenal dengan nama C++. Sebenarnya bahasa C++ mengalami dua tahap evolusi. C++ yang pertama, dirilis oleh AT&T Laboratories, dinamakan cfront. C++ versi kuno ini hanya berupa kompiler yang menterjemahkan C++ menjadi bahasa C.

Pada evolusi selanjutnya, Borland International Inc. mengembangkan kompiler C++ menjadi sebuah kompiler yang mampu mengubah C++ langsung menjadi bahasa mesin (assembly). Sejak evolusi ini, mulai tahun 1990 C++ menjadi bahasa berorientasi obyek yang digunakan oleh sebagian besar pemrogram professional.

2.2 Struktur Bahasa C++

Contoh :

2

// my first program in C++

#include <iostream.h>

int main ()

{

cout << "Hello World!";

return 0;

}

Hasil :

Hello World!

Sisi kiri merupakan source code, yang dapat diberi nama hiworld.cpp dan sisi kanan adalah hasilnya setelah di-kompile dan di-eksekusi.

Program diatas merupakan salah satu program paling sederhana dalam C++, tetapi dalam program tersebut mengandung komponen dasar yang selalu ada pada setiap pemrograman C++. Jika dilihat satu persatu :

// my first program in C++

Baris ini adalah komentar. semua baris yang diawali dengan dua garis miring (//) akan dianggap sebagai komentar dan tidak akan berpengaruh terhadap program. Dapat digunakan oleh programmer untuk menyertakan penjelasan singkat atau observasi yang terkait dengan program tersebut.

#include <iostream.h>

Kalimat yang diawali dengan tanda (#) adalah are preprocessor directive. Bukan merupakan

baris kode yang dieksekusi, tetapi indikasi untuk kompiler. Dalam kasus ini kalimat #include <iostream.h> memberitahukan preprocessor kompiler untuk menyertakan header file standard iostream. File spesifik ini juga termasuk library deklarasi standard I/O pada C++ dan file ini disertakan karena fungsi-fungsinya akan digunakan nanti dalam program.

3

int main ()

Baris ini mencocokan pada awal dari deklarasi fungsi main. fungsi main merupakan titik awal dimana seluruh program C++ akan mulai dieksekusi. Diletakan diawal, ditengah atau diakhir program, isi dari fungsi main akan selalu dieksekusi pertama kali. Pada dasarnya, seluruh program C++ memiliki fungsi main. main diikuti oleh sepasang tanda kurung () karena merupakan fungsi. pada C++, semua fungsi diikuti oleh sepasang tanda kurung () dimana, dapat berisi argumen didalamnya. Isi dari fungsi main selanjutnya akan mengikuti,berupa deklarasi formal dan dituliskan diantara kurung kurawal ({}), seperti dalam contoh.

cout << "Hello World";

Intruksi ini merupakan hal yang paling penting dalam program contoh. cout merupakan standard output stream dalam C++ (biasanya monitor). cout dideklarasikan dalam header file iostream.h, sehingga agar dapat digunakan maka file ini harus disertakan.

return 0;

Intruksi return menyebabkan fungsi main() berakhir dan mengembalikan kode yang mengikuti instruksi tersebut, dalam kasus ini 0. Ini merupakan cara yang paling sering digunakan untuk mengakhiri program.

2.3 Variabel, Tipe Data, Konstanta

Untuk dapat menulis program yang dapat membantu menjalankan tugas-tugas kita, kita harus mengenal konsep dari variabel.

kita dapat mendefinisikan variable sebagai bagian dari memory untuk menyimpan nilai yang telah ditentukan. Setiap variable memerlukan identifier yang dapat membedakannya dari variable yang lain, sebagai contoh dari kode diatas identifier variabelnya adalah a, b dan result, tetapi kita dapat membuat nama untuk variabel selama masih merupakan identifier yang benar.

4

2.3.1 IdentifiersIdentifier adalah untaian satu atau lebih huruf, angka, atau garis bawah ( _ ). Panjang dari

identifier, tidak terbatas, walaupun untuk beberapa kompiler hanya 32 karakter pertama saja yang dibaca sebagai identifier (sisanya diabaikan). Identifier harus selalu diawali dengan huruf atau garis bawah ( _ ).

Ketentuan lainnya yang harus diperhatikan dalam menentukan identifier adalah tidak boleh menggunakan key word dari bahasa C++. Diawah ini adalah key word dalam C++

Asm auto Bool break case

Catch char Class const const_cast

Continue default Delete do double

dynamic_cast else Enum explicit extern

False float For friend goto

If inline Int long mutable

namespace new Operator private protected

Public register reinterpret_cast return short

Signed sizeof Static static_cast struct

Switch template This throw true

Try typedef Typeid typename union

Unsigned using Virtual void volatile

wchar_t

Bahasa C++ adalah bahasa yang "case sensitive", ini berarti identifier yang dituliskan dengan huruf kapital akan dianggap berbeda dengan identifier yang sama tetapi dituliskan dengan huruf kecil, sabagai contoh : variabel RESULT tidak sama dengan variable result ataupun variabel Result.

2.3.2 Tipe Data

Tipe data yang ada pada C++, berikut nilai kisaran yang dapat direpresentasikan :

5

Name Bytes* Range*

char 1signed: -128 to 127

unsigned: 0 to 255

short 2signed: -32768 to 32767unsigned: 0 to 65535

long 4signed:-2147483648 to 2147483647unsigned: 0 to 4294967295

int * See short, long

float 4 3.4e + / - 38 (7 digits)

double 8 1.7e + / - 308 (15 digits)

long double 10 1.2e + / - 4932 (19 digits)

bool 1 true or false

wchar_t 2 wide characters

2.3.3 Deklarasi variabelUntuk menggunakan variabel pada C++, kita harus mendeklarasikan tipe data yang akan

digunakan. Sintaks penulisan deklarasi variabel adalah dengan menuliskan tipe data yang akan digunakan diikuti dengan identifier yang benar, contoh : int a

Jika akan menggunakan tipe data yang sama untuk beberapa identifier maka dapat dituliskan dengan menggunakan tanda koma, contoh :

int a, b, c;

Tipe data integer (char, short, long dan int) dapat berupa signed atau unsigned tergantung dari kisaran nilai yang akan direpresentasikan. Dilakukan dengan menyertakan keyword signed atau unsigned sebelum tipe data.

6

2.3.4 Inisialisasi VariabelKetika mendeklarasikan variabel local, kita dapat memberikan nilai tertentu. Sintaks penulisan

sbb :

type identifier = initial_value ;

Misalkan kita akan mendeklarasikan variabel int dengan nama a yang bernilai 0, maka dapat dituliskan :

int a = 0;

Atau dengan cara lainnya, yaitu menyertakan nilai yang akan diberikan dalam tanda ():

type identifier (initial_value) ;

Contoh :

int a (0);

2.3.5 Konstanta :Konstanta adalah ekspresi dengan nilai yang tetap. Terbagi dalam Nilai Integer, Nilai

Floating-Point, Karakter and String.

Nilai Integer

Merupakan nilai konstanta numerik yang meng-identifikasikan nilai integer decimal. Karena merupakan nilai numeric, maka tidak memerlukan tanda kutip (") maupun karakter khusus lainnya

C++ memungkinkan kita untuk mempergunakan nilai oktal (base 8) dan heksadesimal (base 16). Jika menggunakan octal maka harus diawali dengan karakter 0 (karakter nol), dan untuk heksadesimal diawali dengan karakter 0x (nol, x).

Nilai Floating Point

Merepresentasikan nilai desimal dan/atau eksponen, termasuk titik desimal dan karakter e (Yang merepresentasikan “dikali 10 pangkat n” , dimana n merupakan nilai integer) atau keduanya. Contoh

:

Karakter dan StringMerupakan konstanta non-numerik, Contoh :

'z'

7

Untuk karakter tunggal dituliskan diantara kutip tunggal (') dan untuk untaian beberapa karakter, dituliskan diantara kutip ganda (").

Konstanta karakter dan string memiliki beberapa hal khusus, seperti escape codes.

\n Newline

\r carriage return

\t Tabulation

\v vertical tabulation

\b Backspace

\f page feed

\a alert (beep)

\' single quotes (')

\" double quotes (")

\? question (?)

\\ inverted slash (\)

Konstanta Define (#define)

Kita dapat mendefinisikan sendiri nama untuk konstanta yang akan kita pergunakan, dengan menggunakan preprocessor directive #define. Dengan format :

#define identifier value

Deklarasi Konstanta (const)

Dengan prefix const kita dapat mendeklarasikan konstanta dengan tipe yang spesifik seperti yang kita inginkan. contoh :

const int width = 100;

8

2.4 Operator

Operator-operator yang disediakan C++ berupa keyword atau karakter khusus. Operator-operator ini cukup penting untuk diketahui karena merupakan salah satu dasar bahasa C++.

Assignation (=). Operator assignation digunakan untuk memberikan nilai ke suatu variable.

a = 5

Memberikan nilai integer 5 ke variabel a. Sisi kiri dari operator disebut lvalue (left value) dan sisi kanan disebut rvalue (right value). lvalue harus selalu berupa variable dan sisi kanan dapat berupa konstanta, variabel, hasil dari suatu operasi atau kombinasi dari semuanya.

Arithmetic operators ( +, -, *, /, % )+ addition

- subtraction

* multiplication

/ division

% module

Compound assignation operators (+=, -=, *=, /=, %=, >>=, <<=, &=, ^=, |=)

contoh :

value += increase; equivalen dengan value = value + increase;a -= 5; equivalen dengan a = a - 5;a /= b; equivalen dengan a = a / b;price *= units + 1; equivalen dengan price = price * (units + 1);

Increase (++) and decrease (--)Operator Increase dan Decrease dapat digunakan sebagai prefix atau suffix. Dengan kata lain dapat

dituliskan sebelum identifier variabel (++a) atau sesudahnya (a++). operator increase yang digunakan sebagai prefix (++a), Perbedaannya terlihat pada tabel dibawah ini :

9

Relational operators ( ==, !=, >, <, >=, <= )Untuk mengevaluasi antara 2 ekspresi, dapat digunakan operator Relasional. Hasil dari

operator ini adalah nilai bool yaitu hanya berupa true atau false, atau dapat juga dalam nilai int, 0 untuk mereprensentasikan "false" dan 1 untuk merepresentasikan "true". Operator-operator relasional pada C++ :

== Equal

!= Different

> Greater than

< Less than

>= Greater or equal than

<= Less or equal than

Logic operators ( !, &&, || ).Operator ! equivalen dengan operasi boolean NOT, hanya mempunyai 1 operand, berguna untuk

membalikkan nilai dari operand yang bersangkutan. Contoh :

operator Logika && dan || digunakan untuk mengevaluasi 2 ekspresi dan menghasilkan 1 nilai akhir. mempunyai arti yang sama dengan operator logika Boolean AND dan OR.

Conditional operator ( ? ).Operator kondisional mengevaluasi ekspresi dan memberikan hasil tergantung dari hasil evaluasi

(true atau false). Sintaks :

condition ? result1 : result2

Bitwise Operators ( &, |, ^, ~, <<, >> ).Operator Bitwise memodifikasi variabel menurut bit yang merepresentasikan nilai yang disimpan,

atau dengan kata lain dalam representasi binary.

op asm Description

10

& AND Logical AND

| OR Logical OR

^ XOR Logical exclusive OR

~ NOT Complement to one (bit inversion)

<< SHL Shift Left

>> SHR Shift Right

Explicit type casting operatorsType casting operators memungkinkan untuk mengkonversikan tipe data yang sudah diberikan ke

tipe data yang lain. Ada beberapa cara yang dapat dilakukan dalam C++, yang paling popular yaitu tipe baru dituliskan dalam tanda kurung () contoh:

int i;float f = 3.14;i = (int) f;

sizeof()Operator ini menerma 1 parameter, dapat berupa type variabel atau variabel itu sendiri dan

mengembalikan ukurannya type atau object tersebut dalam bytes :

a = sizeof (char);

Contoh diatas akan memberikan nilai 1ke a karena char adalah tipe data dengan panjang 1 byte. Nilai yang diberikan oleh sizeof bersifat konstsn constant.

2.5 Operasi Input Output

Memasukkan data dan menampilkannya merupakan hal yang sering dilakukan dalam pemrograman. Salah satu jenis pernyataan yang hampir selalu digunakan pada tiap program adalah pernyataan pemanggilan fungsi untuk keperluan input/output. Untuk operasi input/ output dibutuhkan praprosessor berupa #include <stdio.h>

11

Ada beberapa fungsi dasar dalam fasilitas I/O, yaitu putchar dan getchar. Fungsi putchar digunakan khusus untuk menampilkan sebuah karakter ke layar, sedangkan getchar digunakan untuk membaca sebuah karakter. Selain fasilitas dasar I/O, bahasa juga mempunyai fasilitas I/O yang terformat, yaitu dengan fungsi scanf dan printf. Terformat artinya lebar dan bentuk tampilannya dapat diatur.

2.5.1 fungsi printfFungsi printf() merupakan fungsi yang digunakan untuk menampilkan berbagai jenis data

yang dapat diformat karena fungsi ini dapat menggunakan kode-kode format, yaitu karakter-karakter konversi. Bentuk umum fungsi ini adalah : Printf (“string control “, argumen1, argumen2,…);

String control dapat berupa keterangan beserta penentu format (seperti %d, %f, dan lain-lain). Argument adalah data yang akan ditampilkan dapat berupa variable konstanta, maupun ungkapan.

2.5.2 fungsi scanfFungsi scanf() merupakan fungsi yang digunakan untuk memasukkan berbagai jenis data.

Fungsi ini mirip dengan printf. Fungsi scanf ini ada yang sudah ditentukan dari dalam program, namun ada juga yang membaca masukan dari keyboard, artinya ditentukan oleh pemakai melalui masukan dari keyboard.

2.6 Struktur KontrolSebuah program biasanya tidak terbatas hanya pada intruksi yang terurut saja, tetapi juga

memungkinkan terjadinya percabangan, perulangan dan pengambilan keputusan. Untuk mengatasi kebutuhan itu C++ menyediakan struktur kontrol yang dapat menangani hal-hal tersebut.

2.6.1 Struktur kondisionsal ifPerintah if digunakan untuk mewujudkan percabangan bersyarat.

Instruksi if tunggalIf (ekspresi) pernyataan;

Pengujian ekspresi selslu diapit dengan tanda kurung. Ekspresi dengan menggunakan operator perbandingan akan dites nilai kebenarannya apakah benar atau salah. Pernyataan bisa berupa perintah mencetak output, proses, atauu gabungan.

Instruksi if dengan elseIf (ekspresi) pernyataan1;Else pernyataan2;Operator lain yang sering digunakan adalah ternary (?) yang mempunyai bentuk :

(ekspresi) ? pernyataan1 : pernyataan2 ;

Perintah diatas mempunyai nilai yang sama dengan perintah berikut :If (ekspresi) pernyataan1 else pernyataan2;

12

Instruksi if dengan pilihan if lainnya

If (ekspresi1) pernyataan1;Else if (ekspresi2) pernyataan2;Else pernyataan3;

Instruksi if di dalam instruksi if

If (ekspresi1) pernyataan1; If (ekspresi2) pernyataan2;

2.6.2. instruksi switchInstruksi switch dirancang untuk menangani pegendalian program yang melibatkan

banyak alternative. Biasanya banyak digunakan untuk menggantikan instruksi if-else yang bertingkat. Bentuk umum instruksi switch adalah :

Switch (ekspresi){ Case item1 : pernyataan1;

Break; Case item2 : pernyataan2; Berak; Default : pernyataan;

Break;}

2.7 Struktur Perulangan (Loops)Loops merupakan perulangan statement dengan jumlah tertentu jika kondisi terpenuhi.

2.7.1 The while loop.

Sintaks :

while (expression) statement

Fungsi dari statement diatas adalah mengulang statement jika expression bernilai true.

2.7.2 The do-while loop.

Sintaks

13

do statement while (condition);

Secara fungsional, hampir sama dengan while loop, hanya saja condition dalam do-while dievaluasi setelah eksekusi statement , dengan kata lain, sedikitnya satu kali eksekusi statement walaupun kondisi tidak terpenuhi.

2.7.3 The for loop.

Sintaks

for (initialization; condition; increase) statement;

Fungsinya akan mengulang statement jika condition bernilai benar. Sama seperti while loop., hanya saja for memungkinkan untuk memberikan instruksi initialization dan intruksi increase, sehingga dapat menampilkan loop dengan counter.

Algoritma perulangan for :

1. initialization, digunakan untuk memberikan nilai awal untuk variable counter. Dieksekusi hanya sekali.

2. condition, Dievaluasi, jika bernilai true maka loop berlanjut, sebaliknya loop berhenti dan statement diabaikan

3. statement, dieksekusi, bisa berupa instruksi tunggal maupun blok instruksi (dalam tanda { } ).4. kemudian algoritma kembali ke step 2.

2.8 Kontrol Percabangan (Bifurcation) dan Lompatan (jumps)

2.8.1 Instruksi break

Dengan menggunakan instruksi break, program akan keluar dari loop walaupun kondisi untuk berakhirnya loop belum terpenuhi. Dapat digunakan untuk mengakhiri infinite loop, atau untuk menyebabkan loop selesai sebelum saatnya.

2.8.2 Instruksi continue

14

Instruksi continue menyebabkan program akan melewati instruksi selanjutnya hingga akhir blok dalam loop. Atau dengan kata lain langsung melompat ke iterasi selanjutnya.

2.8.3 Instruksi goto

Menyebabkan lompatan dalam program. Tujuan dari lompatan diidentifikasikan dengan label, yang berisikan argumen-argumen. penulisan label diikuti dengan tanda colon (:).

2.8.4 Struktur Seleksi : switch.

Instruksi switch digunakan untuk membandingkan beberapa nilai konstan yang mungkin untuk sebuah ekspresi, hampir sama dengan if dan else if.

switch meng-evaluasi expression dan memeriksa apakah equivalen dengan constant1, jika ya, maka akan meng-eksekusi block of instructions 1 sampai terbaca keyword break, kemudian program akan lompat ke akhir dari stuktur selektif switch.Jika expression tidak sama dengan constant1, maka akan diperiksa apakah expression equivalen dengan constant2. jika ya, maka akan dieksekusi block of instructions 2 sampai terbaca break. Begitu seterusnya, jika tidak ada satupun konstanta yang sesuai maka akan mengeksekusi default:

2.9 Function

Function adalah satu blok instruksi yang dieksekusi ketika dipanggil dari bagian lain dalam suatu program. Format dari function:

type name ( argument1, argument2, ...) statement

Dimana : type, adalah tipe dari data yang akan dikembalikan/dihasilkan oleh function. name, adalah nama yang memungkinkan kita memanggil function. arguments (dispesifikasikan sesuai kebutuhan). Setiap argumen terdiri dari tipe data diikuti

identifier, seperti deklarasi variable (contoh, int x) dan berfungsi dalam function seperti variable lainnya. Juga dapat melakukan passing parameters ke function itu ketika dipanggil. Parameter yang berbeda dipisahkan dengan koma.

statement, merupakan bagian badan suatu function. Dapat berupa instruksi tunggal maupun satu blok instruksi yang dituliskan diantara kurung kurawal {}.

Function tanpa tipe (Kegunaan void)

15

Deklarasi fungsi akan selalu diawali dengan tipe dari fungsi, yang menyatakan tipe data apa yang akan dihasilkan dari fungsi tersebut. Jika tidak ada nilai yang akan dikembalikan, maka dapat digunakan tipe void.

BAB III

TREE

16

3.1 Definisi Tree

Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hierarkis (hubungan one to many) antara elemen-elemen.

Tree merupakan salah satu struktur data yang paling penting, karena banyak aplikasi menggunakan informasi dan data yang secara alami memiliki struktur hirarkis berguna dalam membantu memecahkan banyak masalah algoritmis.

Contoh sederhana tree:

Tree biasa definisikan sebagai kumpulan simpul/node dengan elemen khusus yang disebut Root. Node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lain (disebut subtree). Apabila diamati pada setiap subtree, akan terlihat bahwa subtree pun mempunyai root dan subtree- subtree, dengan kata lain juga merupakan sebuah tree.

Untuk lebih jelasnya, berikut akan diuraikan istilah-istilah umum dalam tree :

Predecessor : Node yang berada diatas node tertentu Successor : Node yang berada dibawah node tertentu Ancestor : Seluruh node yang terletak sebelum node tertentu dan

terletak pada jalur yang sama. Descendent : Seluruh node yang terletak sebelum node tertentu dan

terletak pada jalur yang sama Parent : Predecessor satu level diatas suatu node. Child : Successor satu level dibawah suatu node. Sibling : Node-node yang memiliki parent yang sama dengan suatu

node Subtree : Bagian dari tree yang berupa suatu node beserta

descendantnya, dan memiliki semua karakteristik dari tree tersebut.

Size : Banyaknya node dalam suati tree. Height : Banyaknya tingkatan / level dalam suatu tree. Root : Satu-satunya node khusus dalam tree yang tidak

17

http://wapedia.mobi/id/Berkas:AVLtreef.svg

mempunyai predecessor Leaf : Node –node dalam tree yang tidak memiliki successor. Degree : Banyaknya child yang dimiliki suatu node.

3.2 Representasi Dari Tree

Ada beberapa cara untuk menggambarkan sebuah tree yaitu :

Pedigree chart

Lineal chart

Diagram venn atau nested sets

Nested parentheses(N0 (N1 (N2) (N3) (N4)) (N5) (N6 (N7) (N8)))

18

Bar chart

Level-number notation

3.3Jenis- Jenis Tree

Binary TreeBinary tree adalah tree dengan syarat bahwa tiap node hanya boleh mimiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.Binary Tree adalah struktur data yang hampir mirip juga dengan Linked List untuk menyimpan koleksi dari data. Linked list dapat dianalogikan sebagai rantai linear, sedangkan binary tree bisa digambarkan sebagai rantai tidak linear. Binary tree dikelompokkan menjadi unordered binary tree (tree yang terurut) dan ordered binary tree (tree yang terurut). Ordered binary tree yaitu sebuah tree yang di dalamnya terdapat aturan untuk menyusun node-node dalam level yang sama, atau sebuah tree dimana setiap subtree pada semua node di dalamnya membentuk himpunan yang berurutan (ordered set). Urutan node-node dapat bersifat ascending (urut naik) dan dapat pula bersifat descending (urut turun).

Contoh dari non-ordered tree :

19

Contoh dari ordered tree :

Binary Tree dapat digambarkan berdasarkan kondisinya, sebagai berikut:

Gambaran dari Binary Tree yang terdiri dari 3 (tiga) node :

Masing-masing simpul dalam binary tree terdiri dari tiga bagian yaitu sebuah data dan dua buah pointer yang dinamakan pointer kiri dan kanan.

Simpul juga mempunyai sibling, descendants, dan ancestors. Sibling dari sebuah simpul adalah anak lain dari induk simpul tersebut. Descendants dari sebuah simpul adalah semua simpul-simpul merupakan cabang (berada dibawah) simpul tersebut. Ancestors dari sebuah simpul adalah semua simpul yang berada diatas antara simpul tersebut dengan root. Penampilan dari sebuah tree akan ditampilkan dengan berat dari tree tersebut, angka yang menunjukkan jumlah level yang ada didalamnya.Tingkat suatu simpul ditentukan dengan pertama kali menentukan akar sebagai bertingkat 1. Jika suatu simpul dinyatakan sebagai tingkat N, maka simpul-simpul yang merupakan anaknya akan berada pada tingkatan N+1. Tinggi atau kedalaman dari suatu pohon adalah tingkat maksimum dari simpul dalam pohon dikurangi dengan 1. Selain tingkat, juga

20

dikenal istilah derajad (degree) dari suatu simpul. Derajad suatu simpul dinyatakan sebagai banyaknya anak atau turunan dari simpul tersebut.

Jenis- jenis binary tree :- Full Binary Tree

Jenis binary tree ini tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

- Complete Binary TreeJenis ini mirip dengan full binary tree, namun tiap subtree boleh memilki panjang path yang berbeda dan setiap node kecuali leaf hanya boleh memiliki dua child.

- Skewed Binary TreeSkewed binary tree adalah binary tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

3.4 Operasi- Operasi Pada Binary Tree

Create : Membentuk binary tree baru yang masih kosong. Clear : Mengosongkan binary tree yang sudah ada. Empty : Function untuk memeriksa apakah binary tree masih

kosong. Insert : Memasukkan sebuah node ke dalam tree. Ada tiga pilihan

insert : sebagai root, left child, atau right child. Find : Mencari root, parent, left, atau right child dari suatu node

(tree tidak boleh kosong). Update : Mengubah isi dari node yang ditunjuk oleh pointer current

(tree tidak boleh kosong). Retrieve : Mengetahui isi dari node yang ditunjuk oleh pointer current

(tree tidak boleh kosong) Deletesub : Menghapus sebuah subtree

21

Characteristic : Mengetahui karakteristik dari suatu tree, yakni size, height,serta average length. Tree tidak boleh kosong.

Tranverse : Mengunjungi seluruh node- node pada tree, masing-masing Sekali. Hasilnya adalah urutan informasi secara linear yang Tersimpan dalam tree. Ada tiga cara tranverse, yaitupreorder, inorder, dan postorder

3.5 Binary Search Tree

Binary tree ini memiliki sifat dimana semua left child harus lebih kecil daripada right child dan parentnya. Semua right child juga harus lebih besar dari pada left child serta parentnya. Binary search tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching / pencarian node tertentu dalam binary tree.

Dalam ilmu komputer, sebuah pohon biner terurut (binary search tree atau BST) adalah sebuah pohon biner struktur data yang memiliki sifat-sifat sebagai berikut:

Setiap simpul memiliki sebuah nilai. Sebuah susunan total ditentukan dalam nilai ini.

Sub pohon kiri dari sebuah simpul hanya memuat nilai lebih kecil dari nilai simpul.

Sub pohon kanan dari sebuah simpul hanya memuat nilai lebih besar atau sama dengan nilai dari simpul.

Berikut contoh pohon biner terurut dengan lebar 9 dan kedalaman 3, dengan akar 8 dan daun: 1, 4, 7 dan 13.

PEMBENTUKAN BINARY SEARCH TREE (BST)

Bila diketahui sederetan data 5, 3, 7, 1, 4, 6, 8, 9 maka proses inserting (memasukkan) data tersebut dalam algoritma BST per langkah adalah sebagai berikut :

Langkah 1: Pemasukan data 5 sebagai root

22

http://wapedia.mobi/id/Berkas:Binary_search_tree.svg

Langkah 2: Pemasukan data 3 disebelah kiri simpul 5 karena 3 < 5.

Langkah 3: Pemasukan data 7 disebelah kanan simpul 5 karena 7 > 5.

Langkah 4: Pemasukan data 1. Karena data 1 lebih kecil dari data di root yaitu 5 maka penelusuran dilanjutkan kesebelah kiri root. Kemudian karena disebelah kiri sudah ada daun dengan nilai 3 dan data 1 lebih kecil dari data 3 maka data 1 disisipkan disebelah kiri simpul 3.

Langkah 5: Pemasukan data 4.

Langkah 6: Pemasukan data 6. Karena data 6 lebih besar dari data di root yaitu 5 maka penelusuran dilanjutkan kesebelah kanan root. Kemudian karena disebelah kanan sudah ada simpul dengan nilai 7 dan data 6 lebih kecil dari data 7 maka data 6 disisipkan disebelah kiri simpul 7.

23

Langkah 7: Pemasukan data 8. Karena data 8 lebih besar dari data di root yaitu 5 maka penelusuran dilanjutkan kesebelah kanan root. Kemudian karena disebelah kanan sudah ada simpul dengan nilai 7 dan karena data 8 lebih besar dari data7 maka data 8 disisipkan disebelah kanan simpul 7.

Langkah 8: Pemasukan data 9. Karena data 9 lebih besar dari data di root yaitu 5 maka penelusuran dilanjutkan kesebelah kanan root. Kemudian karena disebelah kanan bukan merupakan daun yaitu simpul dengan nilai 7 dan karena data 9 lebih besar dari data 7, penelusuran terus dilanjutkan kesebelah kanan. Selanjutnya ditemukan ditemukan daun dengan nilai 8, karena data 9 lebih besar dari 8 maka data 9 disisipkan disebelah kanan simpul 8.

Operasi-Operasi Standar pada binary search tree (BST) :

Mengosongkan BST Mencek apakah BST kosong Mencari Tree Minimum

24

Mencari Tree Maksimum Memasukkan data baru ke dalam BST Mencari elemen tertentu dalam BST Menghapus data tertentu dari dalam BST Menampilkan semua elemen dalam BST

Pada dasarnya operasi dalam binary search tree sama dengan binary tree biasa, kecuali pada operasi insert, update, dan delete.

Insert

Pada binary search tree insert dilakukan setelah lokasi yang tepat ditemukan (lokasi tidak ditentukan oleh user sendiri).

Update

Update ini seperti yang ada pada binary tree biasa, namun disini update akan berpengaruh pada posisi node tersebut selanjutnya. Bila update mengakibatkan tree tersebut bukan binary search tree lagi, harus dilakukan perubahan pada tree dengan melakukan rotasi supaya tetap menjadi binary search tree.

Delete

Seperti halnya update, delete dalam binary search tree juga turut mempengaruhi struktur dari tree tersebut. Ketentuan Delete :

- Jika yang didelete adalah leaf maka tidak perlu dilakukan modifikasi terhadap lokasi

- Jika yang didelete adalah node yang hanya memiliki satu anak, maka anak tersebut langsung

menggantikan posisi dari parent-nya.

- Jika yang didelete adalah node dengan 2 anak (2 subtree), maka node yang diambil mengganti

node yang dihapus adalah:

a. Berasal dari left subtree yang diambil adalah node yang paling

kanan (nilai terbesar)

b. Berasal dari right subtree yang diambil adalah node yang

paling kiri (nilai terkecil)

25

AVL Tree

AVL Tree adalah binary search tree yang memilki perbedaaan tinggi/ level maksimal satu antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan binary search tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan. Selain AVL Tree, terdapat pula height balanced n tree, yakni binary search tree yang memiliki perbedaan level antara subtree kiri dan subtree kanan maksimal adalah n sehingga dengan kata lain AVL Tree adalah height balanced 1 tree.

Untuk memudahkan dalam menyeimbangkan tree, digunakan symbol-simbol bantu :

- (tanda minus) : digunakan apabila subtree kiri lebih panjang dari subtree Kanan.

+(tanda plus) : digunakan apabila subtree kanan lebih panjang dari subtree Kiri.

0 (nol) : digunakan apabila subtree kiri dan subtree kanan mempunyai height yang sama.

3.6 DEKLARASI TREE

PENYAJIAN DENGAN ARRAY

Pohon biner dapat disajikan secara berurutan dengan menggunakan array atau file. Untuk itu diperlukan adanya satu aturan tertentu dengat mengingat definisi pohon biner.pohon yang merupakan kedalaman N mempunyai simpul maksimum 2(N-1), dengan N adalah kedalaman simpul. Sebagai contoh pohon dengan kedalaman 4, mempunyai simpul secara keseluruhan (dari tingkat 1 sampai dengan 4) adalah 15 buah.

Dengan demikian, penyajian pohon biner secara berurutan dalam sebuah array adalah sebagai berikut. Akar pohon (simpul tingkat pertama) selalu menempati elemen pertama array, simpul-simpul tingkat 2 diletakkan sebagai elemen ke-2 dan 3. Simpul-simpul pada tingkat 3 diletakkan sebagai elemen ke-4,5,6,7. Simpul-simpul tingkat 4 diletakkan sebagai elemen ke-8 sampai ke-15. Berikut ini contoh penyajian tree dengan array :

26

Cara penyimpanan seperti ini hanya baik jika pohon binernya berupa pohon biner lengkap. Jika pohonnya tidak lengkap, pemakaian memory tidak efisien. Berikut ini contoh penyajian pohon biner menggunakan array yang tidak efisien :

PENYAJIAN DENGAN LINKED LIST

Simpul dalam pohon biner dapat disajikan dengan list sebagai berikut :

27

BAB IV

HASIL DAN PEMBAHASAN

4.1 Deklarasi Tree

Karena tree tersusun oleh node-node, maka yang perlu kita deklarasikan adalah komponen node itu sendiri. Dalam contoh dibawah, akan kita namai Node.

Sebelumnya perlu kita lihat bahwa untuk mewujudkan implementasi node ke dalam bahasa pemrograman, diperlukan sebuah struktur yang memiliki susunan berikut ini:

Variabel data digunakan untuk menyimpan nilai angka node tersebut, sedangkan kiri dan kanan, bertipe pointer, masing-masing mewakili vektor yang akan menunjuk ke node anak kiri dan kanan.

4.2 Inisialisasi Tree

Untuk pertama kali, saat kita akan membuat sebuah pohon biner, asumsi awal adalah pohon itu belum bertumbuh, belum memiliki node sama sekali, sehingga masih kosong. Oleh karena itu perlu kita tambahkan kode berikut pada baris awal fungsi Main:

28

typedef struct Node{

int data;

Node *kiri;

Node *kanan;

};

Kita mendeklarasikan sebuah pointer yang akan menunjuk ke akar pohon yang kita buat, dengan nama *pohon. Pointer ini ditujukan untuk menunjuk struktur bertipe Node, yang telah dibuat pada bagian 1. Karena pohon tersebut sama sekali belum memiliki node, maka pointer *pohon ditunjukkan ke NULL.

4.3 Menambahkan Node Pada Tree

Karena pohon yang kita buat merupakan sebuah pohon biner, maka untuk menambahkan sebuah node, secara otomatis penambahan tersebut mengikuti aturan penambahan node pada pohon biner:

1. Jika pohon kosong, maka node baru ditempatkan sebagai akar pohon.2. Jika pohon tidak kosong, maka dimulai dari node akar, dilakukan proses pengecekan berikut:

a. Jika nilai node baru lebih kecil dari nilai node yang sedang dicek, maka lihat ke kiri node tersebut. Jika kiri node tersebut kosong (belum memiliki kiri), maka node baru menjadi kiri node yang sedang dicek. Seandainya kiri node sudah terisi, lakukan kembali pengecekan a dan b terhadap node kiri tersebut. Pengecekan ini dilakukan seterusnya hingga node baru dapat ditempatkan.

b. Jika nilai node baru lebih besar dari nilai node yang sedang dicek, maka lihat ke kanan node tersebut. Jika kanan node tersebut kosong (belum memiliki kanan), maka node baru menjadi kanan node yang sedang dicek. Seandainya kanan node sudah terisi, lakukan kembali pengecekan a dan b terhadap node kanan tersebut. Pengecekan ini dilakukan seterusnya hingga node baru dapat ditempatkan.

Proses penambahan ini diimplementasikan secara rekursif pada fungsi berikut:

29

Node *pohon;

pohon = NULL;

Variabel **root menunjukkan node mana yang sedang dicek saat ini, untuk itu saat pemanggilan fungsi ini, variabel **root kita beri nilai pointer yang menunjuk ke node akar, yaitu pohon.

Untuk selengkapnya dapat dilihat pada bagian 5, kode program lengkap.

4.4 Membaca dan Menampilkan Node Pada Tree

Untuk membaca dan menampilkan seluruh node yang terdapat pada pohon biner, terdapat 3 macam cara, atau yang biasa disebut kunjungan (visit). Semua kunjungan diawali dengan mengunjungi akar pohon. Karena proses kunjungan ini memerlukan perulangan proses yang sama namun untuk depth (kedalaman) yang berbeda, maka ketiganya diimplementasikan dengan fungsi rekursif.

a. Kunjungan Pre-Order.Kunjungan pre-order dilakukan mulai dari akar pohon, dengan urutan:

1. Cetak isi (data) node yang sedang dikunjungi

2. Kunjungi kiri node tersebut,

- Jika kiri bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut.

- Jika kiri kosong (NULL), lanjut ke langkah ketiga.

30

void tambah(Node **root,int databaru){

if((*root) == NULL){

Node *baru;

baru = new Node;

baru->data = databaru;

baru->kiri = NULL;

baru->kanan = NULL;

(*root) = baru;

(*root)->kiri = NULL;

(*root)->kanan = NULL;

}

else if(databaru < (*root)->data)

tambah(&(*root)->kiri,databaru);

else if(databaru > (*root)->data)

tambah(&(*root)->kanan,databaru);

else if(databaru == (*root)->data)

printf("Data sudah ada!");

}

tambah(&pohon,data);

3. Kunjungi kanan node tersebut,

- Jika kanan bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kanan tersebut.

- Jika kanan kosong (NULL), proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya.

b. Kunjungan In-Order.1. Kunjungi kiri node tersebut,


- Jika kiri kosong (NULL), lanjut ke langkah kedua.

2. Cetak isi (data) node yang sedang dikunjungi



- Jika kanan kosong (NULL), proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya.

31

void preOrder(Node *root){

if(root != NULL){

printf("%d ",root->data);

preOrder(root->kiri);

preOrder(root->kanan);

}

}

void inOrder(Node *root){

if(root != NULL){

inOrder(root->kiri);


inOrder(root->kanan);

}

}

c. Kunjungan Post-Order.1. Kunjungi kiri node tersebut,


- Jika kiri kosong (NULL), lanjut ke langkah kedua.



- Jika kanan kosong (NULL), lanjut ke langkah ketiga.

3. Cetak isi (data) node yang sedang dikunjungi. Proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya.

Variabel **root pada setiap fungsi diatas menunjukkan node mana yang sedang dikunjungi saat ini, untuk itu saat pemanggilan, variabel **root kita beri nilai pointer yang menunjuk ke node akar, yaitu pohon.

32

void postOrder(Node *root){

if(root != NULL){

postOrder(root->kiri);

postOrder(root->kanan);


}

}

preOrder(pohon);

inOrder(pohon);

postOrder(pohon);

BAB V

PENUTUP

5.1 Kesimpulan

Dari pembahasan laporan di atas maka dapat disimpulkan bahwa :

1. Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hierarkis (hubungan one to many) antara elemen-elemen. Tree merupakan salah satu struktur data yang paling penting, karena banyak aplikasi menggunakan informasi dan data yang secara alami memiliki struktur hirarkis berguna dalam membantu memecahkan banyak masalah algoritmis.

2. Untuk membangun logika berpikir dan mengimplementasikan setiap permasalahan mengenai algoritma tree dapat diselesaikan secara logis dalam bentuk bahasa pemrograman C++.

5.2 Saran- Saran Dari hasil penulisan laporan dan pembelajaran mata kuliah Struktur Data. Selama masa perkuliahan disarankan :

1. Diharapkan dimasa yang akan datang pemberian penjelasan materi dapat diberikan secara jelas sehingga memudahkan dalam melakukan pratikum.

2. Dengan dilakukannya pratikum Struktur data, diharapkan mahasiswa/i dapat menambah pengetahuannya tentang pratikum struktur data dengan menggunakan bahasa pemograman C++. Selain itu mahasiswa seharusnya juga dapat mengimplementasikan kemahirannya menggunakan bahasa pemrograman C++ untuk memecahkan masalah algoritmis dalam kehidupan sehari-hari.

33

DAFTAR PUSTAKA

http://id.wikipedia.org/wiki/Struktur_data

http://dharmaatmaja.Wordpress.com/tag/tree/

34

http://dharmaatmaja.Wordpress.com/tag/tree/

http://id.wikipedia.org/wiki/Struktur_data

LAMPIRAN PROGRAM

Berikut ini kode program keseluruhan, termasuk menu tampilan, di mana di dalamnya terdapat Deklarasi Tree, Inisialisasi Tree, Penambahan Node, dan Pembacaaan serta Menampilkan Node dengan 3 macam kunjungan. Kode ditulis dengan C++

#include <stdio.h>

#include <conio.h>

typedef struct Node{

int data;

Node *kiri;

Node *kanan;

};

void tambah(Node **root,int databaru){

if((*root) == NULL){

Node *baru;

baru = new Node;

baru->data = databaru;

baru->kiri = NULL;

baru->kanan = NULL;

(*root) = baru;

(*root)->kiri = NULL;

(*root)->kanan = NULL;

printf("Data bertambah!");

}

else if(databaru < (*root)->data)

tambah(&(*root)->kiri,databaru);

else if(databaru > (*root)->data)

35

tambah(&(*root)->kanan,databaru);

else if(databaru == (*root)->data)

printf("Data sudah ada!");

}

void preOrder(Node *root){

if(root != NULL){


preOrder(root->kiri);

preOrder(root->kanan);

}

}

void inOrder(Node *root){

if(root != NULL){

inOrder(root->kiri);


inOrder(root->kanan);

}

}

void postOrder(Node *root){

if(root != NULL){

postOrder(root->kiri);

postOrder(root->kanan);


}

}

void main(){

int pil,c;

Node *pohon,*t;

36

pohon = NULL;

do{

clrscr();

int data;

printf("MENU\n");

printf("1. Tambah\n");

printf("2. Lihat pre-order\n");

printf("3. Lihat in-order\n");

printf("4. Lihat post-order\n");

printf("5. Exit\n");

printf("Pilihan : "); scanf("%d",&pil);

switch(pil){

case 1: printf("Data baru : ");scanf("%d",

&data);

tambah(&pohon,data);

break;

case 2: if(pohon!=NULL) preOrder(pohon);

else printf("Masih kosong!");

break;

case 3: if(pohon!=NULL) inOrder(pohon);


break;

case 4: if(pohon!=NULL) postOrder(pohon);


break; }

getch();

}while(pil!=5);

}

37

laporan struktur data tree

Documents