04 - Introduction to Tree, Binary Tree and Expression Tree - 2101713241 - Claudia Anita Magdalena

• Tree

Tree adalah sebuah kumpulan-kumpulan nodes. 

Node bagian paling atas dinamakan root. 

Nodes yang tidak mempunyai children dinamakan leaf. 

Nodes yang mempunyai parent yang sama dinamakan sibling. 

Garis yang menghubungkan parent dan child dinamakan edge. 

Degree of node merupakan total sub tree dari node. 

Height/Depth merupakan maksimum degree dari nodes pada tree.

Jika terdapat garis yang menghubungkan p ke q, maka p dinamakan ancestor dari q, dan q adalah descendant dari p.

Contoh:

Degree of tree = 3

Degree of C = 2

Height = 3

Parent of C = A

Children of A = B,C,D

Sibling of F = G

Ancestor of F = A,C

Descendant of C = F, G

• Binary Tree Concept

Binary Tree adalah sebuah pohon struktur data di mana setiap simpul memiliki paling banyak dua anak. Umumnya, anaknya dinamakan kiri dan kanan. Node yang tidak mempunyai anak dinamakan leaf. 

Contoh: 

Binary tree diatas mempunyai 9 nodes dan berakar pada 18. Leaves nodenya adalah 9, 12, 10 dan 23.

Macam - macam binary tree:

- Perfect Binary Tree

Perfect Binary Tree adalah binary tree yang setiap levelnya berada pada depth yang sama.

- Complete Binary Tree

Complete Binary Tree adalah binary tree yang setiap levelnya (kecuali yang terakhir), sudah terisi semua.

- Skewed Binary Tree

Skewed Binary Tree adalah binary tree yang masing-masing node mempunyai anak yang paling banyak satu.

- Balanced Binary Tree

• Representasi dari Binary Tree

- Implementasi menggunakan array

Index pada array merepresentasikan nomor node.

Index ke-0 adalah akar node.

Index pada left child = 2p+1, dimana p merupakan index parent

Index pada right child = 2p+2

Index parent = (p-1)/2

- Implementasi menggunakan linked list

struct node{

      int data;

      struct node *left;

      struct node *right;

      struct node *parent;

};

struct node *root = NULL;

• Ekspresi dari Tree 

Contoh: 

-Prefix : *+ab/-cde

-Postfix : ab+cd-e/*

-Infix : (a+b)*((c-d)/e)

• Prefix Tranversal

Pada prefix, kita harus print terlebih dahulu sebelum childnya di proses.

void prefix(struct tnode *curr){

        printf("%c", curr->chr);

        if(curr->left != 0) prefix(curr->left);

        if(curr->right!= 0) prefix(curr->right);

}

• Postfix Traversal

Pada postfix, kita harus print setelah childnya di proses.

void prefix(struct tnode *curr){

        if(curr->left != 0) prefix(curr->left);

        if(curr->right!= 0) prefix(curr->right);

        printf("%c", curr->chr);

}

• Infix Traversal

Pada infix, mungkin memiliki ambiguitas operator tanpa tanda kurung.

Contohnya:

* + a b c pada prefix akan dikodekan dalam infix sebagai a + b * c dengan kode sebelumnya, sementara infix yang benar adalah (a+b) * c.

a + b * c : b dikalikan dengan c kemudian ditambahkan dengan a.

(a+b) * c : a ditambahkan dengan b kemudian dikalikan dengan c.

Solusinya adalah kita dapat menambahkan brackets () ketika menuliskan operator.

void infix(tnode *curr){

        if(is_operator(curr->chr))putchar( '(' );

        if(curr->left != 0) infix(curr->left);

        printf("%c", curr->chr);

        if(curr->right!= 0) infix(curr->right);

        if(is_operator(curr->chr))putchar( '(' );        

}

Jadi, * + a b c pada prefix akan dikodekan sebagai ((a+b) * c) pada infix, dan ini benar.