Rangkuman Materi Struktur Data Pert.4

Tree

Tree adalah sebuah rangkaian dari beberapa node. bentuk tree adalah bercabang ke bawah dan akar berada di node paling atas. Tree mempunyai level(kedalaman) dan juga degree. Ada juga node yang disebut sebagai leaf, node tersebut tidak memiliki cabang kebawah.

Binary tree adalah jenis tree yang ditiap node hanya boleh memiliki cabang maksimal 2.

ada beberapa jenis Binary tree, yaitu :

1. Perfect Binary tree
2. Complete Binary Tree
3. Skewed Binary Tree

Bagian-bagian dalam Binary Tree :

maximum node yang bisa ada adalah 2^h+1 – 1.
h adalah ketinggian dari binary tree.

Tinggi minimum dari binary tree dengan n node adalah ²log(n).

Tinggi maximum dari binary tree dengan n node adalah n – 1.

Expression tree

• untuk prefix membaca dari atas ke bawah.

jadi prefixnya adalah : *+ab/-cde

• untuk postfix membaca dari bawah ke atas.

jadi postfixnya adalah : ab+cd-e/*

• untuk infix membaca dari kiri ke kanan.

jadi infixnya adalah : (a+b)*((c-d)/e)