TREE (POHON)
adalah salah satu bentuk sirkuit salah satu bentuk graph terhubung yang tidak mengandung sirkuit.
karena merupakan graph terhubung,maka pada pohon (tree) selalu terdapat path yang menghubungkan setiap simpul dalam pohon.
tree dapat juga didefinisikan sebagai kumpulan elemen yang salah satu elemenya di sebut akar(root) dan sisa elemen lainya (simpul)yang terpecah menjadi sebuah himpunan yang saling tidak berhubungan yang di sebut sub pohon (subtree) atau cabang.
Sifat sifat pohon
1. Jika Pohon mempunyai simpul sebanyak n,maka banyaknya ruas atau edge adalah n-1
2. Mempunyai simpul khusus yang di sebut root,jika simpul tersebut mempunyai derajat keluar >=0,dan derajat masuk = 0
3. Mempunyai simpul yang disebut daun/leaf,jika simpul tersebut berderajat keluar = 0,dan berderajat masuk = 1
4. Setiap simpul mempunyai Tingkatan/level yang dimulai dari root yang levelnya =1,sampai dengan level ke-n yang berada pada daun yang paling bawah.simpul yang mempunyai level sama di sebut bersaudara
5. Pohon mempunyai ketinggian atau kedalaman atau height ,yang merupakan level tertinggi.
6. Pohon mempunyai berat atau weight,yang banyaknya daun pada pohon.
Hutan (forest) adalah Kumpulan pohon yang tidak saling berhubungan
(klik untuk memperbesar gambar) Cara menggambarkan bentuk pohon :
* cara pertama
merupakan cara paling banyak digunakan dan paling mudah digunakan,caranya seperti gambar di atas.
* cara kedua
dengan membuat diagram venn seperti gambar di bawah ini
* Cara ketiga
dengan cara menggunakan notasi kurung untuk gambar pada diagram venn di atas.
hasilnya : (P(Q(R,S)),T(U(V,W)))
* Cara Keempat
dengan menggunakan notasi tingkat dan notasi garis
POHON BINAR (BINARY TREE)
Dalam struktur data, pohon memegang peranan yang cukup penting. Struktur ini biasanya digunakan terutama untuk menyajikan data yang mengandung hubungan hierarkykal antara elemen-elemen mereka.
Bentuk pohon khusus yang lebih mudah dikelola dalam komputer adalah pohon binary. Bentuk ini merupakan bentuk pohon yang umum. Sebuah pohon binar T didefinisikan terdiri dari sebuah himpunan hingga elemen yang disebut simpul
Karakteristik Pohon binar
1. Setiap simpul paling banyak hanya memiliki dua buah anak.
2. Derajat tertinggi dari setiap simpul adalah dua
3. Dibedakan antara cabang kiri dan cabang kanan
4. Dimmungkinkan tidak memiliki simpul
dibawah ini contoh pohon binar dengan cabang kiri dan kanan
Istilah pada pohon binar(binary tree)
* Pohon binar penuh (full binary tree)
semua simpul (kecuali daun) memiliki dua anak dan tiap cabang memiliki panjang ruas yang sama
* Pohon Binar lengkap(complate binary tree)
hampir sama dengan pohon biner penuh,bedanya tiap cabang memiliki ruas berbeda
* Pohon biner Similer
Dua pohon yang memiliki struktur sama tapi informasinya berbeda
* Pohon biner Ekivalent
Dua pohon yang memiliki struktur sama dan informasi yang sama
* Pohon biner Miring(skewed Tree)
Dua pohon yang semua simpulnya mempunyai satu anak /turunan kecuali daun.
Deklarasi Pohon Biner dengan program C++
Dalam setiap simpul selalu berisi dua buah pointer untuk menunjuk ke arah cabang kiri dan cabang kanan dan informasi yang akan di simpan dalam simpul tersebut.
* Tree dapat dibuat dengan menggunakan linked list secara rekursif
* Linked list yang digunakan adalah double linked list non circural
* data yang pertama kali masuk akan menjadi node root
* data yang lebih kecil dari node root akan masuk dan menempati node kiri dari node root,sedangkan jika lebih besar akan masuk dan menempati node sebelah kanan node root
Kamis, 17 Juni 2010
Struktur Pohon / Tree
Searching
Searching adalah pencarian data dengan cara menelusuri data-data tersebut.Pada suatu data seringkali dibutuhkan pembacaan kembali informasi (retrieval information) dengan cara searching.empat pencarian data dapat berupa array dalam memori, bisa juga pada file pada external storage
Sequential Search
Adalah suatu teknik pencarian data dalam array ( 1 dimensi ) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu.
Kemungkinan terbaik (best case) adalah jika data yang dicari terletak di indeks array terdepan (elemen array pertama) sehingga waktu yang dibutuhkan untuk pencarian data sangat sebentar (minimal).Kemungkinan terburuk (worst case) adalah jika data yang dicari terletak di indeks array terakhir (elemen array terakhir) sehingga waktu yang dibutuhkan untuk pencarian data sangat lama (maksimal).
deklarasi dalam program c++
Binary Search
Adalah teknik pencarian data dalam dengan cara membagi data menjadi dua bagian setiap kali terjadi proses pencarian.Data yang ada harus diurutkan terlebih dahulu berdasarkan suatu urutan tertentu yang dijadikan kunci pencarian.
Prinsip pencarian biner adalah:
• Data diambil dari posisi 1 sampai posisi akhir N
• Kemudian cari posisi data tengah dengan rumus: (posisi awal
+ posisi akhir) / 2
• Kemudian data yang dicari dibandingkan dengan data yang di
tengah, apakah sama atau lebih kecil, atau lebih besar?
• Jika lebih besar, maka proses pencarian dicari dengan posisi
awal adalah posisi tengah + 1
• Jika lebih kecil, maka proses pencarian dicari dengan posisi
akhir adalah posisi tengah –1
• Jika data sama, berarti ketemu.
Sorting
• Pengurutan data dalam struktur data sangat penting untuk data yang beripe data numerik ataupun karakter.
• Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun)
• Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu.
• Contoh:
• Data Acak : 5 6 8 1 3 25 10
• Ascending : 1 3 5 6 8 10 25
• Descending : 25 10 8 6 5 3 1
Array
Struktur data Array adalah organisasi kumpulan data homogen yang ukuran atau jumlah elemen
maksimumnya telah diketahui dari awal. Array umumnya disimpan di memori komputer
secara kontigu (berurutan). Deklarasi dari array adalah sebagai berikut:
int A[5]; artinya variabel A adalah kumpulan data sebanyak 5 bilangan bertipe
integer.
Operasi terhadap elemen di array dilakukan dengan pengaksesan langsung. Nilai
di masing-masing posisi elemen dapat diambil dan nilai dapat disimpan tanpa melewati
posisi-posisi lain.
Terdapat dua tipe operasi, yaitu:
1. Operasi terhadap satu elemen/posisi dari array
2. Operasi terhadap array sebagai keseluruhan
Dua operasi paling dasar terhadap satu elemen/posisi adalah
1. Penyimpanan nilai elemen ke posisi tertentu di array
2. Pengambilan nilai elemen dari posisi tertentu di array
1.3.1 Penyimpanan dan Pengambilan Nilai
Biasanya bahasa pemrograman menyediakan sintaks tertentu untuk penyimpanan
dan pengambilan nilai elemen pada posisi tertentu di array.
Contoh:
A[10] = 78, berarti penyimpanan nilai 78 ke posisi ke-10 dari array A
C = A[10], berarti pengambilan nilai elemen posisi ke-10 dari array A
1.3.2 Keunggulan dan Kelemahan Array
Keunggulan array adalah sebagai berikut:
1. Array sangat cocok untuk pengaksesan acak. Sembarang elemen di array dapat diacu
secara langsung tanpa melalui elemen-elemen lain.
2. Jika berada di suatu lokasi elemen, maka sangat mudah menelusuri ke elemen-
elemen tetangga, baik elemen pendahulu atau elemen penerus 3
3. Jika elemen-elemen array adalah nilai-nilai independen dan seluruhnya harus terjaga,
maka penggunaan penyimpanannya sangat efisien
Kelemahan array adalah sebagai berikut:
Array mempunyai fleksibilitas rendah, karena array mempunyai batasan sebagai berikut:
1. Array harus bertipe homogen. Kita tidak dapat mempunyai array dimana satu elemen
adalah karakter, elemen lain bilangan, dan elemen lain adalah tipe-tipe lain
2. Kebanyakan bahasa pemrograman mengimplementasikan array statik yang sulit
diubah ukurannya di waktu eksekusi. Bila penambahan dan pengurangan terjadi
terus-menerus, maka representasi statis
• Tidak efisien dalam penggunaan memori
• Menyiakan banyak waktu komputasi
• Pada suatu aplikasi, representasi statis tidak dimungkinkan
Stack / tumpukan
1 DAFTAR LINER
Sebuah daftar linier atau list linier [linear list], merupakan suatu Struktur Data Umum yang terbentuk dari barisan hingga [yang terurut] dari satuan data,ataupun dari Record Elemen yang terdapat di dalam daftar di sebut simpul atou node
File merupakan saiah satu contoh dari daftar linier yang elemen-elemennya berupa Record.Sebagai contoh,Nomor di dalam Buku telepon membentu sebuah daftar linier, Yang apabila daftarmterebut di masukan ke dalam memori secara berangkai akan di dapat sebuah tab
2 stack atau tumpukan
Stack atau tumpukan adalah bentuk khusus dari list linier.Pada stack, penghapus Serta pemasukan elemenya hanya dapat dilakukan pada satu posisi yakni posisi akhir dari list. Posisi ini di sebut Puncak atau Top dari Stack. Elemen stack s pada posisi ini di nyatakan dengan top (S).
Jelasnya bila Stack (S)=[S1,S2….ST] maka top (S) adalah ST. Banyaknya elemen stack S pada saat tertentu biasa kita sebut sebagai NOEL (S)Jadi untuk stack kita di atas, NOEL (S)=T.
Operator penghapus elemen pada Stack disebut POP, sedangkan Operator pemasukan element , disebut PUSH.
E
D
B
S NOEL(S) = 4, TOP(S) = E, dan seterusnya
A
Kita pada hakekatnya tidak membatasi beberapa banyak element dapat masuk ke dalam Stack. Untuk suatu Stack S = [S1,S2….SNOEL], kita katakana bahwa elemen S1 berada di atas elemen Sj, jika I lebih besar dari j. Suatu element tidak dapat kita POP ke luar, sebelum semua elemen di atasnya di keluarkan.
3 OPERASI PADA STACK
Terdapat empat operasi pada Stack, yakni CEATE (Stack), ISEMPETY(Stack), PUSH(elemen,stack), dan POP(Stack). CREATE(S) adalah Operator yang menyebabkan Stack S menjadi Stack hampa.Jadi NOEL (CREATE(S)) adalah 0, dan TOP (CREATE(S)) tak terdevinisi. Operetor ISEMPETY(S) bermaksud memeriksa Stack S hampa atau tidak. Operator PUSH (E,S) akan berkerja menambahkn elemen E pada Stack S,E ditempatkan sebagai TOP(S). Operator POP(S) merupakan operator yang bekerja mengeluarkan elemen TOP(S) dari dalam Stack. TOP(S) akan mengurangi nilai NOEL(S) dengan 1. Suatu kesalahan akan terjadi apabila kita mencoba melakukan POP(S) terhadap Stack S yang hampa.
4 DEKLARASI STACK DALAM VOBOL DAN PASKAL
Meskipun Stack amat luas digunakan, banyak bahasa pemprograman tidak mempunyai Type Data Stack secara built-in. Dalam hal ini, Pemrogram harus memanipulasi sendiri fasilitas yang dimiliki Bahasa Pemprogram tersebut, untuk dapat melakukan Operasi Stack terhadap Variabel Stack. Mungkin cara yang paling sederhana adalah membentuk Stack dalam bemtuk semacam Array. Satu hal yang nyata membedakan Stack dengan Array adalah banyaknya elemen Stack yang dapat bertambah atau berkurang setiap waktu, sementara banyaknya elemen sebuah Array selalu tetap. Deklerasi dari Variable S yang bertype data Stack. Diasumsikan bahwa elemen dari S masing – masing bertype data integer. Dan panjang Stack minimum 100 Elemen. Kita mendeklerasi bahwa sebuah Array yang dilengkapi dengan Variable TOP-PTR ini menyatakan subskrip dari elemen TOP(S) dari Stack . Kita menambahkan kombinasi dari Array dan indikator untuk TOP tersebut dengan nama STACK-STRUC. Dengan penyajian seperti ini, berlaku bahwa NOEL(S) = TOP-PTR, ISEMPETY(S) adalah true bila YTOP-PTR = 0, DAN false bila TOP-PTR lebih besar dari 0.
Dalam COBOL :
01 STACK-STRUCT
02 S PIC 9 (5)
OCCURS 100 TIMES.
Dalam Pascal :
Type stackstruct;
record Stack : Array [ 1..100] of integer;
topptr : integer
end
var S : stackstruct;
Kombinasi tidak mengerti aturan INFO yang kita inginkan. Untuk itu Pemprogram harus berhati-hati dan tidak member indeks kepada S sembarang tempat, selain dengan nilai TOP-PTR.
5 APLIKASI STACK
Stack sangat luas pemakaiannya dalam menyelesaikan dalam menyelesaikan problema. Kompiler, Sistem Operasi, dan berbagai Program Aplikasi banyak menggunakan Stack tersebut. Salah satu contoh adalah problema atau Matching Parantheses. Sebuah kapiler mempunyai tugas, salah satu di antaranya adalah menyelidiki apakan pemrogram telah dengan cepat mengikti aturan tatabahasa, atau sintaks, dari Bahasa pemprograman yang bersangkutan.
NOTASI POSTFIX
Aplikasi lain dari stack adalah pada kompilasi dari ekspresi dalam bahasa pemrograman tingkat tinggi. Kompilator harus mampu menyerahkan bentuk yang biasa, misalnya ((A+B)*C/D+E^F)/G ke suatu bentuk yang dapat lebih mudah dipergunakan dalam pembentukan kode objeknya. Cara yang biasa kita lakukan dalam menulis ekspresi aritmetik seperti di atas, dikenal sebagai notasi infix. Untuk operasi binar seperti menjumlah, membagi, mengurangi, mengalikan ataupun memangkatkan, operator tampil di antara dua operand, misalnya operator + tampil di antara operand A dan B pada operasi A + B. Stack dapat digunakan untuk mentransformasikan notasi infix ini menjadi notasi posfix. Pada notasi posfix, kedua operand tampil bersama di depan operator, misalnya AB+atau PQ* dan sebagainya. Kompilator akan lebih mudah menangani ekspresi dalam notasi posfix ini.
Berikut contoh melakukan pengalihan ekspresi infix ke postfix secara manual. Ekspresi infix = A + B / C * D akan dialihkan menjadi ekspresi postfix.
1. Pilih sub-ekspresi yang berisi “dua operand dan satu operator” yang memiliki level tertinggi
di ekspresi di atas. Didapat B / C dan C * D. Pilih yang paling kiri, maka kita peroleh: B / C.
2. Ubah sub-ekspresi tersebut menjadi sebuah operand, misalkan B / C menjadi E, maka
ekspresi semula menjadi: A + E * D.
3. Lakukan langkah ke (2) hingga ekspresi di atas menjadi “dua operand dan satu operator”
saja. Didapat: A + F
4. Alihkan menjadi bentuk postfix: operand-operand-operator, diperoleh A F +
5. Kembalikan setiap operand menjadi ekspresi semula. F tadinya adalah E * D, maka nilai
F = E * D. Satukan dengan ekspresi yang telah menjadi postfix. Hasilnya = A * E + D
6. Ulangi langkah ke (5) hingga terbentuk ekspresi postfix. Didapat A * B + C / D
Dengan demikian, ekspresi infix: A+B/C*D akan menjadi ABC/D*+ dalam notasi
postfix. Perhatikan dan pelajari tabel berikut ini:
Ekspresi Infix Ekspresi Postfix
A + B A + B
A + B * C A + B * C
(A + B) * C A + B * C
A * B + C A + B * C
Bila ada sub-ekspresi di dalam tanda kurung, maka sub-ekspresi tersebut harus dikerjakan terlebih dulu.
Berikut ini diberikan sebuah algoritma untuk mengubah notasi infix ke dalam notasi posfix. Sebuah stack digunakan untuk keperluan ini. Ekspresi diamati satu persatu dari kiri ke kanan. Pada algoritma ini terdapat 4 aturan dasar, sebagai berikut:
1. Jika simbol adalah ‘’(‘’ (kurung buka), maka ia kita PUSH ke dalam stack
2. Jika simbol adalah ‘’)’’ (kurung tutup), POP dari stack elemen-elemen stack, sampai pertama
kali kita POP simbol ‘’(‘’. Semua elemen stack yang di POP tersebu merupakan output,
kecuali ‘’(‘’ tadi.
3. Jika simbol adalah sebuah operand, tanpa melakukan perubahan elemen stack, operand
tersebut langsung merupakan output.
4. Jika simbol adalah sebuah operator, maka jika TOP stack adalah operator dengan\ level lebih
tinggi atau sama, maka elemen TOP kita POP, sekaligus keluar sebagai output, dilanjutkan
proses seperti ini sampai TOP merupakan ‘’(‘’ atau operator dengan level lebih rendah. Kalau
hal ini terjadi, operator (yang diamati) kita PUSH ke dalam stack. Biasanya ditambahkan
simbol ; (titik-koma) sebagai penutup ekspresi. Dalam keadaan ini, kita POP semua elemen
stack, sehingga stack menjadi hampa.
Dapat dicatat bahwa terdapat 3 level operator, yakni pemangkatan (level tertinggi), level menengahnya adalah perkalian (*) dan pembagian (/) dan level terendah adalah penjumlahan (+) dan pengurangan (-). Tabel berikut menunjukkan pelaksanaan algoritma di atas untuk mengubah ekspresi ((A+B)*C/D+E^F)/G; ke dalam notasi postfix. Jadi, ((A+B)*C/D+E^F)/G akan menjadi AB+C*D/EF^+G/ dalam notasi postfix.
Queue / Antrian
Queue (antrian) adalah struktur data dimana data yang pertama kali dimasukkan adalah data yang pertama kali bisa dihapus. Atau bisa juga disebut dengan struktur data yang menggunakan mekanisme FIFO (First In First Out).
queue
queue
Queue dalam kehidupan sehari-hari seperti antrian pada penjualan tiket kereta api, dimana orang yang pertama datang adalah orang yang pertama kali dilayani untuk membeli tiket. Jika ada orang baru yang datang akan membali tiket, maka posisinya berada pada urutan paling belakang dalam antrian tersebut. Orang yang berada pada posisi terakhir dalam antrian adalah yang terakhir kali dapat dilayani dan memperoleh tiket kereta api (kalau kurang beruntung, maka akan kehabisan tiket). Contoh lain adalah nasabah yang antri di teller bank, paket data yang menunggu untuk ditransmisikan lewat internet, antrian printer dimana terdapat antrian print job yang menunggu giliran untuk menggunakan printer, dsb.
Istilah-istilah yang digunakan dalam queue (antrian)
Memasukkan data (insert) disebut juga dengan put, add, atau enqueue. Menghapus data (remove) biasa disebut dengan istilah delete, get, atau dequeue. Bagian belakang queue, dimana data bisa dimasukkan disebut dengan back, tail (ekor), atau end (akhir). Sedangkan bagian depan (front) queue dimana data bisa dihapus juga biasa disebut dengan istilah kepala (head).Circular Queue
Di dunia nyata apabila seseorang sedang mengantri (misalnya antri tiket kereta api), apabila telah dilayani dan memperoleh tiket, maka ia akan keluar dari antrian dan orang-orang yang berada di belakangnya akan bergerak maju ke dapan. Kita bisa saja menggerakkan setiap item data ke depan apabila kita menghapus data yang terdepan, tetapi hal ini kurang efektif. Sebaliknya kita tetap menjaga setiap item data di posisinya, yang kita lakukan hanyalah merubah posisi front dan rear saja.
Yang menjadi permasalahan adalah apabila posisi rear berada pada bagian akhir dari array (atau pada nomor indeks yang terbesar). Meskipun ada bagian yang kosong di awal-awal array – karena mungkin data telah dihapus, data baru tidak bisa dimasukkan lagi karena rear-nya sudah tidak bisa bergerak lagi. Atau mungkinkah posisi rear nya bisa berpindah? Situasi seperti itu bisa dilihat seperti gambar berikut:
circular queueUntuk menghindari permasalahan seperti itu (tidak bisa memasukkan data baru) – meskipun queue-nya belum penuh, maka front dan rear-nya berputar (kembali) ke bagian awal array. Kejadian seperti ini dinamakan dengan circular queue (atau kadang-kadang disebut juga dengan istilah ring buffer). Kejadian seperti ini seperti terlihat pada gambar berikut:
circular queue
circular queue
Perhatikan bahwa setelah rear berputar (kembali) ke bagian awal array, posisinya sekarang di bawah front, kebalikan dari posisi aslinya (front berada di bawah rear). Coba hapus beberapa data sehingga pada suatu saat front juga akan berputar (balik) ke bagian awal array, sehingga front dan rear akan ke susunan aslinya (front di bawah rear).
Queue.java
class Queue
{
private int maxSize;
private long[] queArray;
private int front;
private int rear;
private int nItems;
//————————————————————–
public Queue(int s) // konstruktor
{
maxSize = s;
queArray = new long[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
//————————————————————–
public void insert(long j) // letakkan item (data) di posisi belakang dari queue
{
if(rear == maxSize-1) //
rear = -1;
queArray[++rear] = j; //naikkan rear dan masukkan item (data) pada posisi rear yang baru
nItems++; //tambah satu item lagi
}
//————————————————————–
public long remove() // hapus item (data) yang berada pada posisi front
{
long temp = queArray[front++]; //dapatkan nilainya dan naikkan front
if(front == maxSize) //
front = 0;
nItems–; // item (data) berkurang satu
return temp;
}
//————————————————————–
public long peekFront() //
{
return queArray[front];
}
//————————————————————–
public boolean isEmpty() //benar jika queue-nya kosong
{
return (nItems==0);
}
//————————————————————–
public boolean isFull() // benar jika queue-nya penuh
{
return (nItems==maxSize);
}
//————————————————————–
public int size() // jumlah ietm (data) dalam queue
{
return nItems;
}
//————————————————————–
} // end class Queue
QueueApp.java
class QueueApp
{
public static void main(String[] args)
{
Queue theQueue = new Queue(5); // queue menampung 5 item (data)
theQueue.insert(10); // masukkan 4 item (data)
theQueue.insert(20);
theQueue.insert(30);
theQueue.insert(40);
theQueue.remove(); // hapus 3 item (data)
theQueue.remove(); // (10, 20, 30)
theQueue.remove();
theQueue.insert(50); // masukkan 4 item (data) lagi
theQueue.insert(60); // (wraps around)
theQueue.insert(70);
theQueue.insert(80);
while( !theQueue.isEmpty() ) // hapus dan tampilkan
{ // all items
long n = theQueue.remove(); // (
System.out.print(n);
System.out.print(“ “);
}
System.out.println(“”);
} // end main()
} // end class QueueApp
method insert()
Method insert() mengasumsikan bahwa queue tidak penuh (full). Kita tidak melihatnya dalam main(), tetapi kita bisa memanggil insert() hanya setelah memanggil isFull() dan memperoleh nilai kembalian yang salah. Pengisian data dengan cara menaikkan rear dan mengisikan data baru tersebut pada rear yang baru sekarang. Tetapi, jika rear berada di puncak array, pada maxSize-1, maka harus kembali ke posisi terbawah array sebelum penyisipan dilakukan. Caranya dengan memberi nilai rear=-1, sehingga jika terjadi kenaikan pada pada rear, maka rear akan menjadi 0, dasar dari array. Dan akhirnya, nItem bertambah.
Method remove()
method remove mengasumsikan queue-nya tidak kosong. Untuk meyakinkan bahwa queue-nya tidak kosong, anda harus memanggil method isEmpty(). Penghapusan selalu dimulai dengan memperoleh nilai pada front dan kemudian mengurangi front. Jika front-nya terletak pada akhir array, maka harus kembali ke 0. Kemudian nItems dikurangi.
Method peek()
untuk mendapatkan nilai pada front.
Method isEmpty(), isFull(), and size()
untuk mengecek nItems, apakah kosong atau penuh.
Kunjungan pada Tree / pohon biner
Ada tida macam kunjungan pada pohon biner, yaitu kunjungan PreOrder, InOrder, dan PostOrder. Selain itu ada kunjungan LevelOrder, yaitu yang berdasarkan kedudukan tiap simpul dalam pohon. Keempat kunjungan itu dibagi menjadi orientasi, yaitu left to right oriented (LRO) atau kunjungan dilakukan di cabang kiri dulu baru ke cabang kanan dan right to left oriented (RLO) atau kunjungan dilakukan di cabang kanan dulu baru ke cabang kiri.
1. Kunjungan PreOrder
Kunjungan PreOrder LRO atau sering disebut dengan depth first order
menggunakan urutan sebagai berikut :
Cetak isi simpul yang dikunjungi.
Kunjungi cabang kiri.
Kunjungi cabang kanan.
Prosedur kunjungan PreOrder dapat dilakukan dengan cara rekursif atau non rekursif. Prosedur kunjungan secara PreOrder LRO dengan rekursif disajikan berikut ini :
Procedure PreOrder (Root:Pohon);
Begin
If Root <> nil then
Begin
Write (Root^.Info);
PreOrder (Root^.kiri);
PreOrder (Root^.kanan);
End;
End;
2. Kunjungan InOrder
Kunjungan InOrder LRO atau sering disebut dengan symmetric order,menggunakan urutan sebagai berikut :
Kunjungi cabang kiri.
Cetak isi simpul yang dikunjungi.
Kunjungi cabang kanan.
Seperti pada kunjungan PreOrder, prosedur kunjungan InOrder dapat dilakukan
dengan cara rekursif atau non rekursif.
Prosedur kunjungan secara InOrder LRO dengan rekursif disajikan berikut ini :
Procedure InOrder (Root:Pohon);
Begin
If Root <> nil then
Begin
InOrder (Root^.kiri);
Write (Root^.Info);
InOrder (Root^.kanan);
End;
End;
3. Kunjungan PostOrder
Kunjungan PostOrder LRO menggunakan urutan sebagai berikut :
Kunjungi cabang kiri.
Kunjungi cabang kanan.
Cetak isi simpul yang dikunjungi.
Seperti halnya PreOrde dan InOrder, prosedur kunjungan PostOrder juga dapat
dilakukan dengan cara rekursif atau non rekursif.
Prosedur kunjungan secara PostOrder LRO dengan rekursif disajikan berikut ini :
Procedure PostOrder (Root:Pohon);
Begin
If Root <> nil then
Begin
PostOrder (Root^.kiri);
PostOrder (Root^.kanan);
Write (Root^.Info);
End;
End;
4 Kunjungan LevelOrder
Kunjungan Level order mempunyai urutan sebagai berikut :
kunijungan dimulai dari simpul yang ada pada tingkat 1 (akar),
diteruskan pada simpul ditingkat 2 ,tingkat 3 dan seterusnya
