Binary Tree

Teknik Informatika - Universitas Muhammadiyah Malang (UMM)Tahun Akademik 2010-2011

Oleh : Nur Hayatin, S.ST

Sub Topik

• Penjelasan Tree• Istilah pada tree• Binary Tree• Jenis Binary Tree• ADT Binary tree

Tree (Pohon)

Real World

root

branches

leaves

Computer Scientist’s View

branches

leavesroot

nodes

Definisi

• Kumpulan node yang saling terhubung secara hirarki.

• Hirarki = bertingkat.• Tiap node dapat berisi data dan link

(penghubung) ke node lainnya• Tiap node memiliki satu induk, kecuali

node root (akar) yang tidak memiliki induk.• Tiap node dapat memiliki anak dalam

jumlah berapapun.

Linked list dan Tree

• Linked list linear/serial data– Contoh : nama-nama mahasiswa dalam

satu kelas.

• Tree non linear/hierachically data– Contoh : tingkatan pegawai dalam

perusahaan.

Contoh Tree

• Mis. : Struktur organisasi sebuah

perusahaan

Contoh Tree

– Mis. : Daftar isi sebuah buku

Contoh Tree

– Mis. : File system

Tree (Pohon)

• Root adalah node yang memiliki hirarki tertinggi.

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

Root and Subtrees

Object

Number Throwable OutputStream

Integer Double Exception FileOutputStream

RuntimeException

root

Tree (Pohon)

• Level adalah posisi hirarki dari sebuah node. Untuk root bisa diberikan level 0 atau 1.

• Leaf (Daun) adalah node yang tidak memiliki anak atau node yang berada pada hirarki paling bawah.

• Height (tinggi)/depth adalah jumlah level dari sebuah tree.

Leaves

Object

Number Throwable OutputStream

Integer Double Exception FileOutputStream

RuntimeException

Node DegreeObject

Number Throwable OutputStream

Integer Double Exception FileOutputStream

RuntimeException

3

2 1 1

0 0 1 0

0

Level

Level 3

Object

Number Throwable OutputStream

Integer Double Exception FileOutputStream

RuntimeException

Level 4

Level 2

Level 1

Level 3

Level 4

Level 2

Level 1

17

Contoh Tree (Pohon)

Level 0

Level 1

Level 2

Level 3

Daun/Leaf

R

S T

X VU W

Y Z

Root/Akar

Istilah Tree (Pohon)

Latihan

Ancestor (F)?Descendant (B)?Parent (I)?Child (C)?Sibling (G)?Size?Height?Root?Leaf?Degree (C)?

Tree (Pohon)

• Dimana,Ancestor (F) = C,ADescendant (B) = D,EParent (I) = HChild (A) = B,CSibling (F) = G,HSize = 9Height = 3/4Root = ALeaf = D,E,F,G,IDegree (C) = 3

Binary Tree

Gambar Binary Trees

Binary Tree

• Tiap node pada binary tree hanya boleh memiliki paling banyak dua child.

• Sehingga hanya ada dua subtree pada binary tree yang disebut sebagai left dan right subtrees.

Tree dan Binary Tree

• Pada binary tree nilai degree tidak lebih dari 2, sedangkan pada tree tidak terbatas.

• Sub tree pada binary harus terurut (ordered), sedangkan pada tree tidak (un-ordered).

Jenis Binary Tree

• Berdasarkan subtree binary tree dibedakan menjadi 4 jenis:– Full Binary Tree– Complete Binary Tree– Incomplete Binary Tree (Unbalanced

Tree)– Skewed Binary Tree

Jenis Tree(Full Binary Tree)

• Semua node (kecuali leaf) memiliki nol atau 2 anak dan tiap subtree memiliki panjang path yang sama.

• Disebut juga maximum binary tree.

Maximum Binary Tree

Jenis Tree(Complete Binary Tree)

• Seluruh node sebelah kiri terisi seluruhnya. Node sebelah kanan pada level n-1 ada yang kosong.

Complete Binary Tree

H

D K

B F J L

A C E G I

Incomplete Binary Tree

Gambar a Gambar b

Jenis Tree(Skewed Binary Tree)

• Binary tree yang semua nodenya (kecuali leaf) hanya memiliki satu anak.

• Disebut juga minimum binary tree.

Right Skewed Left Skewed

Binary Tree Representation

Representation

• Array representation• Linked list representation

ADT BinaryTree

public interface BinaryTree{ public boolean isEmpty(); public Object root(); public void makeTree(Object root, Object left, Object right); public BinaryTree removeLeftSubtree(); public BinaryTree removeRightSubtree(); public void preOrder(Method visit); public void inOrder(Method visit); public void postOrder(Method visit); public void levelOrder(Method visit);}

Array Representation

Struktur Data - Tree 36

Akses Elemen

• Posisi node dapat ditentukan berdasarkan rumus berikut :– Anak kiri dari node i berada pada indeks

: 2*i+1– Anak kanan dari node i berada pada

indeks : 2*i+2

Penambahan array size

• 1 node (root) = 20

• Root + node pada level 1 = 20 +21

• Root + node pada level 1 & 2 = 20

+21+22

• Root + node pada level 1,2,3 = 20

+21 +22 +23

• Root + node pada level 1,2,..n=20+21+22+...+2n

Array Representation

tree[]0 5 10

a b c d e f g h i j

b

a

c

d e f g

h i j

1

2 3

4 5 6 7

8 9 10

0 5 10

2 3

4 5 6 7

8 9 10

Right-Skewed Binary Tree

a

b

1

3

c7

d15

tree[]0 5 10

a - b - - - c - - - - - - -15d

1

37

15

0 5 10 15

Linked List Representation

Class BinaryTreeNode

class BinaryTreeNode

{

Object element;

BinaryTreeNode leftChild; // left subtree

BinaryTreeNode rightChild;// right subtree

// constructors and any other methods come here

}

Contoh Representasi Linked List

a

cb

d

f

e

g

hleftChildelementrightChild

root

leftChildelementrightChild

root

Binary Tree Traversal

Definisi

• Penelusuran seluruh node pada binary tree.

• Metode :– Preorder– Inorder– Postorder– Level order

Preorder Traversal

public static void preOrder(BinaryTreeNode t){ if (t != null) { visit(t); preOrder(t.leftChild); preOrder(t.rightChild); }}

PreOrder Traversal

• Preorder traversal1. Cetak data pada root2. Secara rekursif mencetak seluruh data

pada subpohon kiri3. Secara rekursif mencetak seluruh data

pada subpohon kanan

Preorder Example (visit = print)

a b c

Preorder Example (visit = print)

a b d g h e i c f j

Preorder Of Expression Tree

Gives prefix form of expression!

/ * + a b - c d + e f

Inorder Traversal

public static void inOrder(BinaryTreeNode t){ if (t != null) { inOrder(t.leftChild); visit(t); inOrder(t.rightChild); }}

InOrder Traversal

• Inorder traversal1.Secara rekursif mencetak seluruh data

pada subpohon kiri 2.Cetak data pada root3.Secara rekursif mencetak seluruh data

pada subpohon kanan

Inorder Example (visit = print)

a

b c

b a c

Inorder Example (visit = print)

g d h b e i a f j c

Inorder By Projection (Squishing)

a

b c

d ef

g h i j

g d h b e i a f j c

Inorder Of Expression Tree

Gives infix form of expression (sans parentheses)!

ea + b * c d / + f-

Postorder Traversal

public static void postOrder(BinaryTreeNode t){ if (t != null) { postOrder(t.leftChild); postOrder(t.rightChild); visit(t); }}

Postorder Traversal

• Postorder traversal1.Secara rekursif mencetak seluruh data

pada subpohon kiri2.Secara rekursif mencetak seluruh data

pada subpohon kanan3.Cetak data pada root

Postorder Example (visit = print)

a

b c

b c a

Postorder Example (visit = print)

g h d i e b j f c a

Postorder Of Expression Tree

Gives postfix form of expression!

a b + c d - * e f + /

Traversal Applicationsa

b c

d ef

g h i j

• Make a clone.

• Determine height.

•Determine number of nodes.

Level Order

while (t != null){ visit t and put its children on a FIFO queue; remove a node from the FIFO queue and call it t; // remove returns null when queue is empty}

Let t be the tree root.

Latihan

• Telusuri pohon biner berikut dengan menggunakan metode pre, in, post, dan level traversal.

Latihan 1

a. b.

+

*

3 5

-

2 /

8 4

Latihan 2

Level-Order Example (visit = print)

a

b c

d ef

g h i j

a b c d e f g h i j

Contoh : Pohon Ekspresi

PreOrder, PostOrder, InOrder

• Pre-order :– Node, left, right– Ekspresi Prefix : ++a*bc*+*defg

• Post-order :– Node, left, right– Ekspresi Postfix : abc*+de*f+g*+

• In-order :– Node, left, right– Ekspresi Infix : a+b*c+d*e+f*g

Pustaka

• Sartaj Sahni , “Data Structures & Algorithms”, Presentation L20-24.

• Mitchell Waite, “Data Structures & Algorithms in Java”, SAMS, 2001