Pertemuan Ke-4 (20/03/18) - Introduction to Tree, Binary Tree, and Expression Tree

Nama  : Wirasatya Aryyaguna

NIM    : 2101670532

Introduction to Tree, Binary Tree and Expression Tree

Tree Concept

• Degree of Tree            : Banyaknya level (dari root sampai paling bawah)
• Parent                          : Node yang memiliki child
• Child                           : Node yang memiliki parent
• Sibling                         : Node yang satu parent dengan node lain
• Ancestor                     : Dari paling bawah(atau yang ditunjuk) sampai root
• Descendant                 : Keturunan

Tipe dari Binary Tree:

• Perfect Binary Tree, adalah pohon biner dimana setiap level berada pada kedalaman yang sama.
• Complete Binary Tree, adalah pohon biner yang lengkap.
• Skewed Binary Tree, adalah pohon biner dimana masing-masing node memiliki paling banyak satu anak.
• Balanced Binary Tree

Implementation using linked list

struct node {

            int data;

            struct node *left;

            struct node *right;

            struct node *parent;

};

struct node *root = NULL;

Jumlah maksimal nodes dari suatu Binary Tree adalah 2^k.

Jumlah maksimal nodes dari suatu tinggi h adalah 2^h+1-1.

Prefix              : *+abc

Postfix            : ab+c*