4 - Introduction to Tree, Binary Tree, and Tree Expression - 2101711356 - Farhan Adji Nugroho

Introduction to Tree, Binary Tree, and Expression Tree

Sub Topics

Tree & Binary Tree:

-        Tree Concept

-        Binary Tree Concept

-        Type of Binary Tree

-        Property of Binary Tree

-        Representation of Binary Tree

-        Expression Tree Concept

-        Create Expression Tree from Prefix, Postfix and Infix

-        Prefix, Postfix and Infix Traversal

·       Konsep Tree

Tree adalah koleksi dari satu node atau lebih.

Keterangan :

Path – path mengacu pada urutan node di sepanjang garis pada tree.

Root – Node di bagian teratas tree disebut sebagai root. Hanya ada satu root per tree dan satu path dari root node ke node manapun.

Parent – setiap node kecuali root memiliki satu garis ujung ke atas node yang disebut parent.

Child – Node di bawah sebuah node tertentu yang dihubungkan dengan garis kebawah yang disebut child node.

Leaf – node yang tidak memiliki anak disebut sebagai leaf node.

Subtree – subtree merupakan turunan dari sebuah node.

Levels – level sebuah node mewakili generasi sebuah node. Jika root node pada tingkat 0, maka node anak berikutnya berada pada level 1, generasi berikutnya di tingkat 2, dan seterusnya.

Siblings­-node yang memiliki parent node sama disebut sebagai sibling.

Degree – adalah total subtree dari sebuah node.

Height/Depth-  adalah tingkat maksimum degree dari sebuah nodes dalam tree

jika ada garis yang menghubungkan p dengan q, kemudian p disebut sebagai ancestor dari q, dan q adalah descendant dari p.

·       Konsep Binary Tree

-Sebuah pengorganisasian secara hirarki dari beberapa buah node, dimana masing-masing node tidak memiliki child lebih dari dua.

-Implementasi binary tree bisa dilakukan menggunakan struktur data linked list. Masing-masing node terdiri dari tiga bagian yaitu sebuah data/info dan dua buah pointer yang dinamakan pointer kiri/kanan.

           

Tipe dari Binary Tree

-        Perfect Binary tree

Adalah binary tree yang setiap levelnya memiliki depth yang sama.

-        Complete Binary Tree

Adalah binary tree dimana setiap level, kecuali yang terakhir terisi penuh, dan semua node terisi dikiri sebanyak mungkin.

Skewed Binary Tree

Adalah binary tree dimana setiap node memiliki paling banyak satu child.

           

-        Balanced Binary Tree

Adalah binary tree dimana tidak ada leaf yang jauh dari root daripada leaf lainnya (skema penyeimbangan yang berbeda memungkinkan definisi yang berbeda).

           

Jumlah maksimal node

Jumlah maksimal node pada setiap level adalah 2ⁿ

Jumlah maksimum dari node pada binary tree adalah 2ⁿ⁺¹-1

Jumlah maksimum node dari binary tree of height 3. = 1+2+4+8 = 2⁰ + 2¹+2²+2³=2⁴-1 = 15.

           

Jumlah minimum height dari binary tree pada n node adalah 2log(n) dan jumlah maksimum height pada binary tree of n node adalah n-1

Skewed binary tree memiliki maximum height.

·       Representasi Binary Tree

-        Implementasi menggunakan array

Index on array represents node number

Index 0 is Root node

Index Left Child is 2p + 1, where p is parent index

Index Right Child is 2p + 2

Index Parent is (p-1)/2

-        Impelementasi menggunakan Linked List

struct node {

     int data;

     struct node *left;

     struct node *right;

     struct node *parent;

};

struct node *root = NULL;

·       Expression Tree Concept

Prefix               : *+ab/-cde

Postfix             : ab+cd-e/*

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

Kita akan menggunakan struktur ini untuk setiap node di tree :

struct tnode {

     char chr;

     struct tnode *left;

     struct tnode *right;
};

ini adalah binary tree.

·       Create Expression Tree from Prefix

Kita dapat membuat expression tree dari prefix dengan rekursif.

char s[MAXN];

int  p = 0;

void f(struct tnode *curr) {

     if ( is_operator(s[p]) ) {

           p++; curr->left  = newnode(s[p]);

           f(curr->left);

           p++; curr->right = newnode(s[p]);

           f(curr->right);

     }
}

Main function

struct tnode *root = newnode(s[0]);

f(root);

·       Prefix Traversal

melakukan prefix atau postfix di expression tree sangat simpel.

void prefix(struct tnode *curr) {

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

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

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

dalam prefix, kita harus di print/process sebelum child diproses.

·       Postfix Travesal

void postfix(struct tnode *curr) {

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

     if ( curr->right != 0 ) postfix(curr->right);
     printf( “%c“, curr->chr );

}

Dalam postfix, kita harus print/process setelah child diproses.

·       Infix Traversal

sebagai contoh * + a b c didalam prefix akan dikodekan dalam infixx sebagai a + b * c dengan kode sebelumnya, sedangkan infix adalah ( a + b ) * c.

a + b * c : b dikalikan dengan c dan kemudian ditambah a

( a + b ) * c : a di tambahkan dengan b dan kemudian dikali dengan c.

Prefix               : *+abc

Postfix             : ab+c*

Wrong infix     : a+b*c

Correct Infix    : (a+b)*c