Tenia Wahyuningrum, S.Kom. MT Sisilia Thya Safitri, S.T.,M.T

tReE Tenia Wahyuningrum, S.Kom. MT Sisilia Thya Safitri, S.T.,M.T www.st3telkom.ac.id

Tree … Kumpulan node yang

saling

terhubung satu sama lain

dalam suatu kesatuan yang membentuk layakya struktur sebuah

pohon

.

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Tree …  merepresentasikan suatu struktur hirarki (one-to-many)  tampak sebagai kumpulan node dari

atas ke bawah.

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Tree …  salah satu bentuk implementasi

linked list

banyak yang digunakan untuk menggambarkan hubungan yang bersifat hirarkis

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Karena harapan lah, kita menanam pohon Meskipun kita tahu tak akan memetik buahnya berpuluh-puluh tahun kemudian

Contoh penggunaan struktur

tree

Family tree Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Contoh penggunaan struktur

tree

Tournamen schedule Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Contoh penggunaan struktur

tree

Organization Structure Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Tree anatomy Root

R

Level 0

Internal Node

T

S

Level 1

Leaf

X

Level 2

U

V

Child of X Level 3

Y

Z Parent of Z and Y

Subtree

W

Istilah dalam Tree

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

a Tree R T

S Y

Z

U

Tenia Wahyuningrum & Sisilia Thya

V

Ancestor (U) = T, R Descendant (T) = U, V, W Parent (Y) = S Child (R) = S, T Sibling (U) = V, W Size = 8 Height = 3 Root = R Leaf = Y, Z, U, V, W Degree (T) = 3

W

www.st3telkom.ac.id

Latihan X Y

R

S

Q

T P

Z

U

W

M N

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Representasi Tree  Diagram Venn

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Tree Representation  Notasi Tingkat

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Tree Representation  Notasi Kurung (A(B(D,E(I,J)),C(F,G,H)))

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Latihan • Buat diagram venn, notasi kurung dan notasi tingkat! X Y

R

S

Q

T P

Z

U

W

M N

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

• Identifikasikan !     

Ancestor (N) = Descendant (Y) = Parent (Z) = Child (Q) = Sibling (U) =

Tenia Wahyuningrum & Sisilia Thya

    

Size = Height = Root = Leaf = Degree (R) =

www.st3telkom.ac.id

Binnary Tree

Semakin tinggi pohon, semakin kuat angin meniupnya

– Suatu tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. – Tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Binary Tree

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Binary Tree A C

B D

E

Tenia Wahyuningrum & Sisilia Thya

F

G www.st3telkom.ac.id

Binary Tree A C

B D

E

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Binary Tree A B C Tenia Wahyuningrum & Sisilia Thya

D E F www.st3telkom.ac.id

Node pada Binary Tree  Jumlah maksimum node pada setiap tingkat adalah 2n, n= level/tingkat  Node pada binary tree maksimum berjumlah 2m-1, m= height

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Node pada Binary Tree A

Tingkat ke-0, jumlah max = 20

Tingkat ke-2, jumlah max = 22

C

B

Tingkat ke-1, jumlah max = 21

D

Tenia Wahyuningrum & Sisilia Thya

E

F

G

www.st3telkom.ac.id

Latihan • Gambarkan pohon biner dengan ketentuan sbb :         

Ancestor (M) = Z, X Descendant (Y) = K, L Parent (N) = Z Child (Z) = M, N Sibling (Y) = Z Size = 7 Height = 3 Root = X Leaf = K, L, M, N

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

xxx

Penelusuran Pohon Biner Jika kau teriaki dan maki pohon, lambat laun pohon akan mati Tenia Wahyuningrum www.st3telkom.ac.id

Definisi • Penelusuran seluruh node pada binary tree. • Metode :

–Preorder –Inorder –Postorder Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

PreOrder Traversal 1. Cetak data pada root 2. Secara rekursif mencetak seluruh data pada subpohon kiri 3. Secara rekursif mencetak seluruh data pada subpohon kanan

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Preorder Example (visit = print) a b

c a b c

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Preorder Example (visit = print) a

b f

e

d g

c

h

i

j

a bdghe i c f j Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Preorder Of Expression Tree /

+

* e + a

f

b

c

d

/ * + a b- c d+ e f Gives prefix form of expression! Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Script Preorder Of Expression Tree void preorder(pohon ph) { if (ph != NULL) { printf("%c ", ph->info); preorder(ph->kiri); preorder(ph->kanan); } }

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

InOrder Traversal 1.Secara rekursif mencetak seluruh data pada subpohon kiri 2.Cetak data pada root 3.Secara rekursif mencetak seluruh data pada subpohon kanan

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Inorder Example (visit = print) a

b

c ba c

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Inorder Example (visit = print) a b f

e

d

g

c

h

i

j

g d h b e i a f j c Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Script InOrder Of Expression Tree void inorder(pohon ph) { if (ph != NULL) { inorder(ph->kiri); printf("%c ", ph->info); inorder(ph->kanan); } }

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Postorder Traversal 1.Secara rekursif mencetak seluruh data pada subpohon kiri 2.Secara rekursif mencetak seluruh data pada subpohon kanan 3.Cetak data pada root

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Postorder Example (visit = print) a b

c bc a

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Postorder Example (visit = a print) b

f

e

d g

c

h

i

j

ghdi e bj f c a Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Postorder Of Expression Tree /

+

*

e + a

f

b

c

d

a b+ c d- * e f + /

Gives postfix form of expression! Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Script PostOrder Of Expression Tree

void postorder(pohon ph) { if (ph != NULL) { postorder(ph->kiri); postorder(ph->kanan); printf("%c ", ph->info); } }

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Latihan • Telusuri pohon biner berikut dengan menggunakan metode pre, in, post !

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id

Latihan 1 + *

3

-

5

2

/ 8

Tenia Wahyuningrum & Sisilia Thya

4

www.st3telkom.ac.id

Latihan 2

Tenia Wahyuningrum & Sisilia Thya

www.st3telkom.ac.id