Tutorial InOrder - Alfi Zulfian Abdi - 1144024
PENGERTIAN
TREE
Kumpulan
node yang saling terhubung satu sama lain dalam suatu kesatuan yang
membentuk
layakya struktur sebuah pohon. Struktur pohon adalah suatu cara merepresentasikan
suatu struktur hirarki (one-to-many) secara grafis yang mirip sebuah pohon,
walaupun pohon tersebut hanya tampak sebagai kumpulan node-node
dari atas ke bawah. Suatu struktur data yang tidak linier yang menggambarkan
hubungan yang hirarkis (one-to-many) dan tidak linier antara elemen-elemennya.
Deklarasi
Pohon
Jika
kita memperhatikan setiap simpul dalam pohon biner, kita bisa menyusun
struktur data yang tepat dari simpul-simpul tersebut. Kita dapat melihat
bahwa dalam setiap simpul selalu berisi dua buah pointer untuk menunjuk
ke cabang kiri dan cabang kanan, dan informasi yang akan disimpan
dalamsimpul tersebut. Dengan memperhatikan hal ini, simpul dalam pohon biner
disajikan sebagai berikut:
typedef char TypeInfo;
typedef struct Simpul *Tree;
struct Simpul {
TypeInfo Info;
tree Kiri, /* cabang kiri */
Kanan; /* cabang kanan */
};
- JENIS-JENIS TREE
BINARY
TREE
Tree
dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua sub pohon dan
kedua subpohon harus terpisah.
Kelebihan
struktur Binary Tree :
- Mudah dalam penyusunan algoritma sorting
- Searching data relatif cepat
- Fleksibel dalam penambahan dan penghapusan data
- KUNJUNGAN PADA POHON BINER
Sebuah
pohon biner memiliki operasi traversal yaitu suatu kunjungan pada
suatu
simpul tepat satu kali. Dengan melakukan kunjungan lengkap kita akan
memperoleh
urutan informasi secara linier yang tersinpan di dalam pohon biner.
Terdapat
tiga jenis kunjungan pada pohon biner, yaitu :
- PREORDER
Kunjungan
jenis ini mempunyai urutan kunjungan sebagai berikut :
–
Cetak isi simpul yang dikunjungi.
–
Kunjungi cabang kiri.
–
Kunjungi cabang kanan.
Prosedur
untuk melakukan traversal secara PREORDER adalah sebagai berikut:
- INORDER
Kunjungan
jenis ini mempunyai urutan kunjungan sebagai berikut :
–
Kunjungi cabang kiri.
–
Cetak isi simpul yang dikunjungi.
–
Kunjungi cabang kanan.
Prosedur
untuk melakukan traversal secara INORDER adalah sebagai berikut:
- POSTORDER
Kunjungan
jenis ini mempunyai urutan kunjungan sebagai berikut :
–
Kunjungi cabang kiri.
–
Kunjungi cabang kanan.
–
Cetak isi simpul yang dikunjungi
BERIKUT
MERUPAKAN CONTOH PROGRAMNYA
#include<stdio.h>//header
file
#include<conio.h>
/*
Deklarasi struct */
typedef
struct Node{
int data; //data pada tree
Node *kiri; //penunjuk node anak kiri
Node *kanan; //penunjuk node anak kanan
};
/*
Fungsi untuk memasukkan data ke dalam tree */
void
tambah(Node **root, int databaru){
if((*root) == NULL){ //jika pohon/subpohon
masih kosong
Node *baru;//node “baru” dibentuk…
baru = new Node;//berdasarkan struct “Node”
baru->data = databaru; //data node baru diisi oleh variabel databaru
baru->kiri = NULL;//penunjuk kiri node baru masih kosong
baru->kanan = NULL;//penunjuk kanan node baru masih kosong
(*root) = baru; //node pohon (root) diletakkan pada node baru
(*root)->kiri = NULL;//penunjuk kiri node root masih kosong
(*root)->kanan = NULL; //penunjuk kanan node root masih kosong
printf(“Data bertambah!”);
}
else if(databaru < (*root)->data)//jika databaru kurang dari data node
root…
tambah(&(*root)->kiri, databaru);//tambahkan databaru pada subpohon kiri
else if(databaru > (*root)->data)//jika databaru lebih dari data node
root…
tambah(&(*root)->kanan, databaru); //tambahkan databaru pada subpohon
kanan
else if(databaru == (*root)->data)//jika databaru sama dengan data node root
printf(“Data sudah ada!”);//databaru tidak dapat ditambahkan pada tree
}
/*
Fungsi untuk menampilkan data secara pre-order
(data ditampilkan dari node induk, node anak kiri, lalu node anak kanan)
*/
void
preOrder(Node *root){
if(root != NULL){//jika pohon/subpohon tidak kosong
printf(“%d “, root->data);//menampilkan data node yang dikunjungi
preOrder(root->kiri);//mengunjungi node anak kiri
preOrder(root->kanan); //mengunjungi node anak kanan
}
}
/*
Fungsi untuk menampilkan data secara in-order
(data ditampilkan dari node anak kiri, node induk, lalu node anak kanan)
*/
void
inOrder(Node *root){
if(root != NULL){//jika pohon/subpohon tidak kosong…
inOrder(root->kiri);//mengunjungi node anak kiri
printf(“%d “, root->data);//menampilkan data node yang dikunjungi
inOrder(root->kanan);//mengunjungi node anak kanan
}
}
/*
Fungsi untuk menampilkan data secara post-order
(data ditampilkan dari node anak kiri, node anak kanan, lalu node induk)
*/
void
postOrder(Node *root){
if(root != NULL){//jika pohon/subpohon tidak kosong
postOrder(root->kiri); //mengunjungi node anak kiri
postOrder(root->kanan);//mengunjungi node anak kanan
printf(“%d “, root->data); //menampilkan data node yang dikunjungi
}
}
main(){
int pil, c;
Node *pohon, *t;
pohon = NULL;
do{
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);
else
printf(“Masih
kosong!”);
break;
case 4 :
if(pohon != NULL)
postOrder(pohon);
else
printf(“Masih kosong!”);
break;
}
getch();
printf(“\n”);
}
while(pil != 5);
}
Link Github :
Plagiarism :
good
BalasHapus