Struktur Pohon Biner dan Kunjungan Pohon Biner

Kunjungan Pohon Biner

Tree bisa didefinisikan sebagai suatu kumpulan

n elemen salah satu elemennya disebut dengan akar (root), dan sisa elemen lainnya (yang disebut simpul) terpecah menjadi sejumlah himpunan yang paling tidak berhubungan satu sama lain, yang disebut dengan subpohon (

subtree), atau disebut juga cabang. Jika kita melihat pada subpohon, maka subpohon inipun juga mempu

nyai akar dan sub-subpohonnya masing-masing.

Dalam kehidupan sehari-hari, tree dapat dilihat dari pohon silsilah keluarga. Tingkat yang tertinggi disebut juga sebagai root.

Untuk lebih jelasnya lihat gambar 6.1 merupakan

contoh dari sebuah tree.

Gambar 6.1 Contoh Tree dengan 15 simpul

Jika kita memperhatikan gambar ditas, sebenarnya yang disebut dengan simpul (node atau vertex) adalah elemen pohon yang berisi informasi / data dan petunjuk percabangan. Pada pohon diatas memiliki 15 simpul yang berisi informasi berupa huruf A, B, C, D sampai O lengkap dengan percabangannya. Akar / Root dari pohon diatas berisi huruf A.

Tingkat (level) suatu simpul ditentukan dengan pertama kali menentukan akar sebagai bertingkat 1. jika suatu simpul dinyatakan sebagai tingkat N, maka simpul-simpul yang merupakan anaknya dikatakan berada dalam tingkat N+1. pada pohon diatas merupakan tree dengan 5 level.

Latihan Soal Pra UTS Perancangan Basis Data

Pertemuan 1 Perancangan Basis Data

1)      Suatu sistem pengelolaan atau penyusunan data-data dengan menggunakan komputer yang digunakan untuk proses pengambilan keputusan disebut ....

a)      Database

b)      Sistem

c)      File System

d)     Sistem database

e)      File

2)      Fakta dari suatu obyek disebut ....

a)      Informasi

b)      Data

c)      Database

d)     DBMS

e)      Metadata

3)      Yang meruoakan pemakai (User) dari database adalah, kecuali ....

a)      Programmer

b)      End User

c)      DBA

d)     Database adminidtrator

e)      Network Guy

Program Linked List

#include <iostream>
// merupakan library untuk menyertakan header file standard iostream.

#include <malloc.h>
// merupakan library untuk menyertakan header file standard iostream.

using std::cout;
//perintah agar cout agar dapat berfungsi

typedef int typeinfo;
typedef struct typenode *typeptr;
typedef struct typenode {typeinfo info;
typeptr next;};
//mendeklarasian bahwa typeinfo bertipe integer serta menjadikan struct typenode dengan fungsi *typeptr dan menjelaskan isinya.

typeptr awal,akhir;
void buatlistbaru();
void sisipdepan (typeinfo IB);
void sisipbelakang (typeinfo IB);
void sisiptengah (typeinfo IB);
void hapuslist(typeinfo IB);
void cetaklist ();
int main()

Linked List

LINKED LIST

Pengertian Linked list :

• sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian.
• Linked list adalah suatu struktur data yg merupakan suatu rangkaian atau daftar record berjenis sama. Kemudian dihubungkan melalui bantuan pointer. Pengalokasian daftar dapat dilakukan secara dinamis sehingga isi dari daftar dapat dimanipulasi.
• struktur berupa rangkaian elemen saling berkait dimana setiap elemen dihubungkan elemen lain melalui pointer. Pointer adalah alamat elemen. Penggunaan pointer untuk mengacu elemen berakibat elemen-elemen bersebelahan secara logik walau tidak bersebelahan secara fisik di memori.

Single Linked List

Tempat yang disediakan pada satu area memori tertentu untuk menyimpan data dikenal dengan sebutan node atau simpul. Setiap node memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, dengan demikian hanya diperlukan sebuah variabel pointer. Susunan berupa untaian semacam ini disebut Single Linked List (NULLmemilik nilai khusus yang artinya tidak menunjuk ke mana-mana. Biasanya Linked List pada titik akhirnya akan menunjuk ke NULL).

Pembuatan Single Linked List dapat menggunakan 2 metode:

• LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)
• FIFO (First In First Out), aplikasinya : Queue (Antrean)

Double Linked List

Salah satu kelemahan single linked list adalah pointer (penunjuk) hanya dapat bergerak satu arah saja, maju/mundur, atau kanan/kiri sehingga pencarian data pada single linked list hanya dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, dapat menggunakan metode double linked list. Linked list ini dikenal dengan nama Linked list berpointer Ganda atau Double Linked List.

Circular Double Linked List

Merupakan double linked list yang simpul terakhirnya menunjuk ke simpul terakhirnya menunjuk ke simpul awalnya menunjuk ke simpul akhir sehingga membentuk suatu lingkaran.

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.

A. STACK DENGAN SINGLE LINKED LIST

Selain implementasi stack dengan array seperti telah dijelaskan sebelumnya, stack daat diimplementasikan dengan single linked list. Keunggulannya dibandingkan array adalah penggunaan alokasi memori yang dinamis sehingga menghindari pemborosan memori.

Misalnya pada stack dengan array disediakan tempat untuk stack berisi 150 elemen, sementara ketika dipakai oleh user stack hanya diisi 50 elemen, maka telah terjadi pemborosan memori untuk sisa 100 elemen, yang tak terpakai. Dengan penggunaan linked list maka tempat yang disediakan akan sesuai dengan banyaknya elemen yang mengisi stack.

Dalam stack dengan linked list tidak ada istilah full, sebab biasanya program tidak menentukan jumlah elemen stack yang mungkin ada (kecuali jika sudah dibatasi oleh pembuatnya). Namun demikian sebenarnya stack ini pun memiliki batas kapasitas, yakni dibatasi oleh jumlah memori yang tersedia.

Operasi-operasi untuk Stack dengan Linked List

• IsEmpty

Fungsi memeriksa apakah stack yang adamasih kosong.

• Push

Fungsi memasukkan elemen baru ke dalam stack. Push di sini mirip dengan insert dalam single linked list biasa.

• Pop

Fungsi ini mengeluarkan elemen teratas dari stack.

• Clear

Fungsi ini akan menghapus stack yang ada.

B. QUEUE DENGAN DOUBLE LINKED LIST

Selain menggunakan array, queue juga dapat dibuat dengan linked list. Metode linked list yang digunakan adalah double linked list.

Operasi-operasi Queue dengan Double Linked List

• IsEmpty

Fungsi IsEmpty berguna untuk mengecek apakah queue masih kosong atau sudah berisi data. Hal ini dilakukan dengan mengecek apakah head masih menunjukkan pada Null atau tidak. Jika benar berarti queue masih kosong.

• IsFull

Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bisa menampung data dengan cara mengecek apakah Jumlah Queue sudah sama dengan MAX_QUEUE atau belum. Jika benar maka queue sudah penuh.

• EnQueue

Fungsi EnQueue berguna untuk memasukkan sebuah elemen ke dalam queue (head dan tail mula-mula meunjukkan ke NULL).

• DeQueue

Procedure DeQueue berguna untuk mengambil sebuah elemen dari queue. Hal ini dilakukan dengan cara menghapus satu simpul yang terletak paling depan (head).

Dengan menggunakan linked list maka programmer dapat menimpan datanya kapanpun dibutuhkan. Linked list mirip dangan array, kecuali pada linked list data yang ingin disimpan dapat dialokasikan secara dinamis pada saat pengoperasian program (run-time).

Pada array, apabila programmer ingin menyimpan data, programmer diharuskan untuk mendefinisikan besar array terlebih dahulu, seringkali programmer mengalokasikan array yang sangat besar(misal 100). Hal ini tidak efektif karena seringkali yang dipakai tidak sebesar itu. Dan apabila programmer ingin menyimpan data lebih dari seratus data, maka hal itu tidak dapat dimungkinkan karena sifat array yang besarnya statik. Linked list adalah salah satu struktur data yang mampu menutupi kelemahan tersebut.