PPC Iklan Blogger Indonesia

Jumat, 11 Mei 2012

UTS


Pengertian tree

Tree merupakan salah satu bentuk implementasi banyak linked list yang biasanya digunakan untuk menggambarkan hubungan yang bersifat hirarkis antara elemen elemen yang ada.

Jenis-jenis Binary Tree :

a) Full Binary Tree

Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

b) Complete Binary Tree

Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

c) Skewed Binary Tree

yakni Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

Macam macam binary tree

    Preorder Traversal

    Inorder Traversal

    Postorder TraversalPengertian dan gambar linket list

Node ke-1                        node ke-2          node ke-3             node ke-4

Linked list

Setiap elemen linked list terdiri dari 2 bagian, data dan pointer address.

Pengalokasian ruang memori dilakukan tanpa pendeklarasian sebelumnya dan terbatas pada jumlah ruang memori yang tersisa (dapat dipakai).

Array

Setiap elemen array hanya berisi data saja.

Pengalokasian ruang memori terbatas pada jumlah ruang yang dideklarasikan sebelumnya.

Operasi-Operasi yang ada pada Linked List

    Insert

Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.

    IsEmpty

Fungsi ini menentukan apakah linked list kosong atau tidak.

    Find First

Fungsi ini mencari elemen pertama dari linked list

    Find Next

Fungsi ini mencari elemen sesudah elemen yang ditunjuk now

    Retrieve

Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.

    Update

Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu

    Delete Now

Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.

    Delete Head

Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.

    Clear

Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.

Single Linked List :

~ Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya dan juga memiliki field yang berisi data.

~ Akhir linked list ditandai dengan node terakhir akan menunjuk ke null yang akan digunakan sebagai kondisi berhenti saat pembacaan linked list.


Double Linked List :

~ Linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu: 1 field pointer yang menunjuk ke pointer berikutnya, 1 field pointer yang menunjuk ke pointer sebelumnya dan field yang berisi data dari node tersebut.

~ Pointer next dan prev-nya menunjuk ke null.


Single Circular Linked List :

~ Single Linked List yang pointer next-nya menunjuk ke dirinya sendiri, jika terdiri dari beberapa node maka pointer terakhirnya akan menunjuk ke pointer terdepannya.

Double Circular Linked List :

~ Double Linked List yang pointer next dan prev-nya menunjuk ke dirinya sendiri secara circular.