Kamis, 31 Mei 2018
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-elmennya.
ISTILAH DALAM TREE
Gambar 1.1 Istilah dalam Tree
Ilustrasi alogaritma tree
Gambar 1.2 Ilustrasi Algoritma Tree
Keterangan :
Ancesor (F) = C, A
Descendant(C) = F,G
Parent (D) = B
Child (A) = B, C
Sibbling (F) = G
Size = 7
Height = 3
Root = A
Leaf = D,E,F,G
Degree = 2
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
Gambar 1.4 Binary Tree
FULL BINARY TREE
Semua node, kecuali leaf pasti memiliki 2 anak dan tiap
subpohon memiliki panjang path yang sama.
Gambar 1.5 Full Binary Tree
COMPLETE BINARY TREE
Tree yang mirip dengan full binary tree, tapi tiap
subtree boleh memiliki panjang path yang berbeda dan tiap node (kecuali leaf)
memiliki 2 anak.
Gambar 1.6 Complete Binary Tree
SKEWED BINARY TREE
Binary tree yang semua nodenya (kecuali leaf) hanya memiliki satu anak.
Gambar 1.7 Skewed Binary Tree
Berikut adalah contoh progam :
//header file
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
//pendeklarasian struct sebuah tree awal
struct Node{
int data;
Node *kiri;
Node *kanan;
};
//fungsi untuk menambahkan node baru
void tambah(Node **root, int databaru)
{
//jika root masih kosong
if((*root) == NULL)
{
//pembuatan node baru
Node *baru;
//pengalokasian memori dari node yang telah dibuat
baru = new Node;
//inisialisasi awal node yang baru dibuat
baru->data = databaru;
baru->kiri = NULL;
baru->kanan = NULL;
(*root) = baru;
(*root)->kiri = NULL;
(*root)->kanan = NULL;
printf("Data bertambah!");
}
//jika data yang akan dimasukkan lebih kecil daripada elemen root, maka akan diletakkan di node sebelah kiri.
else if(databaru<(*root)->data)
tambah(&(*root)->kiri, databaru);
//jika data yang akan dimasukkan lebih besar daripada elemen root, maka akan diletakkan di node sebelah kanan
else if(databaru>(*root)->data)
tambah(&(*root)->kanan, databaru);
//jika saat dicek data yang akan dimasukkan memiliki nilai yang sama dengan data pada root
else if(databaru == (*root)->data)
printf("Data sudah ada!");
}
//fungsi yang digunakan untuk mencetak tree secara preOrder
void preOrder(Node *root)
{
if(root != NULL){
printf("%d ", root->data);
preOrder(root->kiri);
preOrder(root->kanan);
}
}
//fungsi yang digunakan untuk mencetak tree secara inOrder
void inOrder(Node *root)
{
if(root != NULL){
inOrder(root->kiri);
printf("%d ", root->data);
inOrder(root->kanan);
}
}
//fungsi yang digunakan untuk mencetak tree secara postOrder
void postOrder(Node *root)
{
if(root != NULL){
postOrder(root->kiri);
postOrder(root->kanan);
printf("%d ", root->data);
}
}
//fungsi utama
int main()
{
//deklarasikan variabel
int pil, data;// c;
Node *pohon; //*t;
pohon = NULL; //inisialisasi node pohon
//perulangan do-while
do
{
system("cls"); //bersihkan layar
printf("\t#PROGRAM TREE C++#");
printf("\n\t==================");
printf("\nMENU");
printf("\n----\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)
{
//jika pil bernilai 1
case 1 :
printf("\nINPUT : ");
printf("\n-------");
printf("\nData baru : ");
scanf("%d", &data);
//panggil fungsi untuk menambah node yang berisi data pada tree
tambah(&pohon, data);
break;
//jika pil bernilai 2
case 2 :
printf("\nOUTPUT PRE ORDER : ");
printf("\n------------------\n");
if(pohon!=NULL)
//panggil fungsi untuk mencetak data secara preOrder
preOrder(pohon);
else
printf("Masih kosong!");
break;
//jika pil bernilai 3
case 3 :
printf("\nOUTPUT IN ORDER : ");
printf("\n------------------\n");
if(pohon!=NULL)
//panggil fungsi untuk mencetak data secara inOrder
inOrder(pohon);
else
printf("Masih kosong!");
break;
//jika pil bernilai 4
case 4 :
printf("\nOUTPUT POST ORDER : ");
printf("\n------------------\n");
if(pohon!=NULL)
//panggil fungsi untuk mencetak data secara postOrder
postOrder(pohon);
else
printf("Masih kosong!");
break;
}
_getch();
}while(pil != 5); //akan diulang jika input tidak samadengan 5
return EXIT_FAILURE;
}
Hasil Eksekusi Progam
Gambar 1.8 Tampilan Awal
Gambar 1.9 Tambah data
Gambar 2.0 Jika ditekan Menu 2
Gambar 2.1 Jika ditekan menu 3
Gambar 2.2 Jika ditekan menu 4
Gambar 2.3 Jika ditekan menu 5
Post By :
Tri Atmojo Sulaiman
Pend. Teknik Informatika
Referensi :
http://www.nblognlife.com/2014/12/tree-pada-c-tree-awal.html
