Tree Structure (Struktur Data & Algoritma)

Struktur Tree banyak dikenal untuk menunjukkan susunan pengurus dalam suatu organisasi.

Istilah dalam Tree:
1. Root
2. Parent
3. Child
4. Node
5. Leaf
6. Sibling
7. Ancestor
8. Descendant

Level dalam struktur tree menunjukkan peringkat node dari mulai root ke bawah, dimana root menempati level 0 dst.

Struktur Tree terbagi 2 macam

1. Ordered Tree
Penempatan sibling berdasarkan aturan tertentu. Aturan yang berbeda akan menyebabkan struktur tree yang berbeda pula.

2. Unordered Tree atau Oriented Tree
Cara penembatan siblinya tidak ditentukan, yang penting jelas hubungan parent-childnya.

Struktur Data tree dalam pemrograman bahasa C, dapat dijabarkan sbb:

struct node {
   struct node *left;
   struct node *right;
   char label;
};

Algoritma penelusuran data (traverse) pada struktur tree ada 3 macam.
1. PreOrder
Cara penelusurannya:
a. Pergi ke root
b. Telusuri bagian kiri tree sampai selesai
c. Telusuri bagian kanan tree sampai selesai

void preorder(struct node *p){
   if ( p == NULL) return;
   printf("Node %c ", p->label);
   preorder(p->left);
   preorder(p->right);
}

2. InOrder
Cara penelusurannya:
a. Telusuri bagian kiri tree sampai selesai
b. Pergi ke root
c. Telusuri bagian kanan tree sampai selesai

void inorder(struct node *p){
    if ( p == NULL) return;
    inorder(p->left);
    printf("Node %c ", p->label);
    inorder(p->right);
}

3. PostOrder
Cara penelusurannya:
a. Telusuri bagian kiri tree sampai selesai
b. Telusuri bagian kanan tree sampai selesai
c. Pergi ke root

void postorder(struct node *p){
    if ( p == NULL) return;
    postorder(p->left);
    postorder(p->right);
    printf("Node %c ", p->label);
}

Dengan menggunakan penelusuran yang berbeda urutan data yang dihasilkan dari sebuah struktur tree akan berbeda pula.