Struktur Data Pohon/Tree

Widiastuti, SKom., MMSI

Real World

root

branches

leaves

Computer SCientiSt’S View

branches

leaves root

nodes

Tree (Pohon)

Kumpulan node yang saling terhubung

secara hirarki.

Root adalah node yang memiliki hirarki tertinggi.

Subtree (pohon anak) adalah beberapa node yang tersusun hirarki yang ada dibawah root.

POHON / TREE

Struktur data yang terdiri dari akar (root), dan subpohon-subpohon dalam susunan berhirarki.

ROOT/AKAR

Simpul

/ Node

/ Vertex

TINGKAT (LEVEL) KEDALAMAN (DEPTH) POHON

Tingkat dimulai dari 0, 1, 2 ……

Kedalaman dimulai dari 1, 2, 3, ……

TINGKAT 0

TINGKAT 1

TINGKAT 2

TINGKAT 3

DERAJAT SIMPUL

Derajat 2

Derajat 2

Derajat 0

Derajat 3

Derajat = jumlah anak yang dimiliki sebuah

simpul

NODE INTERNAL & EKSTERNAL

Node Internal

Node Internal

Node Eksternal

Node Internal = node yang memiliki anak

Node eksternal = node yang tidak memiliki anak (daun)

Istilah Tree (Pohon)

Latihan Ancestor (F) …

Descendant (B) …

Parent (I) …

Child (C) …

Sibling (G) …

Size …

Height …

Root …

Leaf …

Degree (C) …

POHON BINER

Struktur Data Pohon yang maksimal memiliki 2 anak.

JUMLAH MAKS NODE

Jumlah maksimum node pada setiap tingkat adalah 2 pangkat n

FISIK POHON BINER

FISIK POHON BINER

Alamat Left Info Right

1 D

2 E

3 A

4

5 F

6 B

7

8 G

9 C

10

Alamat Left Info Right

1 D

2 E

3 6 A 9

4

5 F

6 B

7

8 G

9 C

10

Alamat Left Info Right

1 0 D 0

2 0 E 0

3 6 A 9

4

5 0 F 0

6 1 B 2

7

8 0 G 0

9 5 C 8

10

KONVERSI POHON KE POHON BINER

Anak pertama menjadi anak kiri, anak ke-2 menjadi cucu kanan, ke-3 jadi cicit kanan ……

LATIHAN KONVERSI KE POHON BINER

Konversi pohon umum ini ke pohon biner.

X

Y R S

Q T W U Z

P M N

LATIHAN KONVERSI KE POHON UMUM

Konversi pohon biner ini ke pohon umum.

A

B

C

D

X

Y

X E I

J