Pertemuan 5 -Introduction to Tree, Binary Tree And Expression Tree- -Benedick Asdyo-2101631090

 Tree
merupakan graf tanpa adanya cycle atau koleksi dari satu atau lebih node
Istilah dalam tree:

contoh tree

 Node dari tree =  A,B,C,D,E,F,G
Root dari tree = A(Node teratas) 

DEGREE dari Tree = 3

DEGREE dari C = 2

tinggi tree = 3

PARENT of C = A

CHILDREN dari  A = B, C, D

SIBILING dari F = G

ANCESTOR dari F = A, C

DESCENDANT dari C = F, G

 Binary Tree
-seperti namanya, binary tree adalah tree yang setiap node nya memiliki children maksimal 2
-Node tanpa children disebut leaf
-contoh 

-jumlah node pada level tertentu dapat dihitung dengan rumus 2^level
-jumlah maksimal seluruh node dengan ketinggian h dapat dihitung dengan 2^h-1
-tinggi maksimal dari binary tree dapat dicari dengan rumus log n basis 2

 -Tipe-tipe binary tree:
PERFECT binary tree adalah binary tree yang setia levelnya memliki depth yang sama.

COMPLETE binary tree adalah Hampir sama dengan perfect binary tree, tapi semua simpul (kecuali daun) memiliki 2 anak dan tiap cabang memiliki panjang ruas berbeda.

SKEWED binary tree adalah binary tree yang setiap nodenya hanya memiliki 1 anak

-Implementasi dengan linked list :

struct node {

  int data;

  struct node *left;

  struct node *right;

  struct node *parent;

};

•

struct node *root = NULL;

 Konsep expression tree

 

Prefix  : *+ab/-cde

Postfix    : ab+cd-e/*

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

 untuk prefix kita tulis dulu operatornya baru childrennya dari kiri
untuk postfix kita tulis dulu childrennya baru parentnya(seperti saat menggambarkan tree untuk fungsi rekursif)
untuk infix kita perlu bantuan kurung agar operatornya dijalankan dengan benar






Nama : Benedick Asdyo
NIM   : 2101631090