TREE
Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hierarkis (hubungan one to many) antara elemen-elemen.
Tree bisa didefinisikan sebagai kumpulan simpul/node dengan elemen khusus yang disebut Root.
Contoh :
Direktori/folder pada windows atau linux.
A. Terminologi Pada Tree
Contoh Tree :
B. Operasi Dasar
- Create: membentuk sebuah tree baru yang kosong.
- Clear: menghapus semua elemen tree.
- Empty: mengetahui apakah tree kosong atau tidak.
- Insert: menambah node ke dalam Tree secara rekursif. Jika data yang akan dimasukkan lebih besar daripada elemen root, maka akan diletakkan di node sebelah kanan, sebaliknya jika lebih kecil maka akan diletakkan di node sebelah kiri. Untuk data pertama akan menjadi elemen root.
- Find: mencari node di dalam Tree secara rekursif sampai node tersebut ditemukan dengan menggunakan variable bantuan ketemu. Syaratnya adalah tree tidak boleh kosong.
- Traverse: yaitu operasi kunjungan terhadap node-node dalam pohon dimana masing-masing node akan dikunjungi sekali.
- Count: menghitung jumlah node dalam Tree.
- Height : mengetahui kedalaman sebuah Tree
- Find Min dan Find Max : mencari nilai terkecil dan terbesar pada Tree
- Child : mengetahui anak dari sebuah node (jika punya)
C. BST (Binary Search Tree)
Suatu tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah.
Tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.
Contoh BST :
D. Tree Traversal
Ada tiga cara traversal
preorder
inorder
postorder
Untuk tree yang kosong, traversal tidak perlu dilakukan
1. Preorder (SLR)
- Simpul / Node nya
- Subtree sebelah kiri (Left)
- Subtree sebelah kana (Right)
Contoh :
Implementasi dalam bahasa C
struct node {
struct node *left;
struct node *right;
char label;
}
void preorder(struct node *p)
{
if (p==NULL) return; jika empty-tree, tidak perlu lakukan
printf(“visit %c ”, p->label); tampilkan label node yang dikunjungi
preorder(p->left); traverse the left subtree
preorder(p->right); traverse the right subtree
}
2. Inorder (LSR)
- Subtree sebelah kiri (Left)
- Simpul / Node nya
- Subtree sebelah kana (Right)
contoh :
Implementasi dalam bahasa C
struct node {
struct node *left;
struct node *right;
char label;
}
void inorder(struct node *p)
{
if (p==NULL) return; jika empty-tree, tidak perlu lakukan
inorder(p->left); traverse the left subtree
printf(“visit %c ”, p->label); tampilkan label node yang dikunjungi
inorder(p->right); traverse the right subtree
}
3. Postorder (LRS)
- Subtree sebelah kiri (Left)
- Subtree sebelah kana (Right)
- Simpul /Node nya
contoh :
Implementasi dalam bahasa C
struct node {
struct node *left;
struct node *right;
char label;
}
void postorder(struct node *p)
{
if (p==NULL) return; jika empty-tree, tidak perlu lakukan
postorder(p->left); traverse the left subtree
postorder(p->right); traverse the right subtree
printf(“visit %c ”, p->label); tampilkan label node yang dikunjungi
}
Contoh Preorder, Postorder, Inorder
0 komentar:
Posting Komentar