Apa itu Struktur Data Binary Tree ?
Tree artinya pohon.Mengacu pada pohon pada dunia nyata yang di mana memiliki akar daun dan ranting
Istilah-istilah yang penting pada Tree :
- Node paling atas (tidak punya predecessor) disebut Root
- Node yang berada di atas node tertentu = Predecessor
- Node yang berada di bawah node tertentu = Successor
- Predecessor satu level = Parent
- Sucessor satu level = Child
- Seluruh Node sebelum node tertentu dan berada pada jalur yang sama = Ancestor
- Seluruh Node setelah node tertentu dan berada pada jalur yang sama = Descendants
- Node-node yang memiliki parent yang sama = Sibling
- Bagian dari tree beserta descendants nya = Subtree
- Node yang tidak punya successor = Leaf
- Jumlah node dalam suatu tree = Size
- Jumlah tingkatan tree = Height
- Banyaknya child yang dimiliki suatu node = Degree
Contoh paling simple penerapan tree adalah direktori dalam komputer di dalam direktori ada folder kemudian di dalam ada subfolder dst.
Sebenarnya ini sudah dikenalkan saat sd dulu pada pelajaran matematika di mana untuk membuat faktorisasi prima dari suatu bilangan kita bisa memakai pohon faktor.Seperti ini contoh pohon faktor
Dalam pohon faktor di atas,
- 120 adalah Root
- 2,3,5 adalah Leaf karena mereka tidak bercabang
- 60 dan 2,30 dan 2, 15 dan 2,3 dan 5 descendants dari 120
- 30 dan 2,15 dan 2,3 dan 5 descendants dari 60
- 15 dan 2,3 dan 5 descendants dari 30
- 3 dan 5 descendats dari 15
Kali ini kita akan membahas jenis tree yang lebih spesifik yaitu Binary Tree.Binary Tree merupakan tree di mana setiap node hanya boleh memiliki maksimal 2 child
Contoh Binary Tree :
Implementasi Binary Tree Pada Python :
Kita memakai Python saja yang paling mudah implementasinya
Kodenya sebagai berikut
class Node:
def __init__(self,data):
self.left = None
self.right = None
self.data = data
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
root = Node(2)#root
root.left = Node(3) #child kiri dari root
root.right = Node(5) #child kanan dari root
root.left.left = Node(7) #child kiri dari 3
root.left.right = Node(9) #child kanan dari 3
root.right.left = Node(11) #child kiri dari 5
root.right.right = Node(13) #child kanan dari 5
root.PrintTree()
Hasil output kode di atas :
Traversal Pada Binary Tree
Traversal merupakan proses mengunjungi seluruh node pada sebuah tree.Semua node saling terhubung dan dimulai dari root.Karena itulah,kita tidak bisa sembarangan mengakses suatu node.Ada 3 cara untuk traversal yaitu :
1) In-Order Traversal
Urutan kunjungan --> subtreee kiri - root - subtree kanan
Contoh program Python untuk in order traversal
class Node:
def __init__(self,data):
self.left = None
self.right = None
self.data = data
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
def inorderTraversal(self, root):
res = []
if root:
res = self.inorderTraversal(root.left)
res.append(root.data)
res = res + self.inorderTraversal(root.right)
return res
root = Node(2)#root
root.left = Node(3) #child kiri dari root
root.right = Node(5) #child kanan dari root
root.left.left = Node(7) #child kiri dari 3
root.left.right = Node(9) #child kanan dari 3
root.right.left = Node(11) #child kiri dari 5
root.right.right = Node(13) #child kanan dari 5
print(root.inorderTraversal(root))
Hasil output :
2) Pre-Order Traversal
Urutan kunjungan --> root - subtree kiri - subtree kanan
class Node:
def __init__(self,data):
self.left = None
self.right = None
self.data = data
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
def PreorderTraversal(self, root):
res = []
if root:
res.append(root.data)
res = res + self.PreorderTraversal(root.left)
res = res + self.PreorderTraversal(root.right)
return res
root = Node(2)#root
root.left = Node(3) #child kiri dari root
root.right = Node(5) #child kanan dari root
root.left.left = Node(7) #child kiri dari 3
root.left.right = Node(9) #child kanan dari 3
root.right.left = Node(11) #child kiri dari 5
root.right.right = Node(13) #child kanan dari 5
print(root.PreorderTraversal(root))
Hasil output :
3) Post-Order Traversal
Urutan kunjungan --> subtree kiri - subtree kanan - root
class Node:
def __init__(self,data):
self.left = None
self.right = None
self.data = data
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
def PostorderTraversal(self, root):
res = []
if root:
res = self.PostorderTraversal(root.left)
res = res + self.PostorderTraversal(root.right)
res.append(root.data)
return res
root = Node(2)#root
root.left = Node(3) #child kiri dari root
root.right = Node(5) #child kanan dari root
root.left.left = Node(7) #child kiri dari 3
root.left.right = Node(9) #child kanan dari 3
root.right.left = Node(11) #child kiri dari 5
root.right.right = Node(13) #child kanan dari 5
print(root.PostorderTraversal(root))
Hasil output :
Memasukkan Node ke Dalam Binary Tree
Misal saya punya binary tree seperti ini
Kemudian saya ingin memasukkan node 12 di samping node 8 maka akhirnya akan jadi seperti ini binary tree nya
Insertion (memasukkan node) hanya bisa dilakukan kalau ada ruas yang kosong dikasus di atas node 9 pada awalnya hanya memiliki satu child yaitu 8 di bagian kiri.Nah,karena 9 tidak memiliki child kanan maka kita memasukkan node 12 sebagai child kanan dari 9
Implementasi Insert Dengan Python
class Node:
def __init__(self,data):
self.left = None
self.right = None
self.data = data
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
def inorder(self, root):
res = []
if root:
res = self.inorder(root.left)
res.append(root.data)
res = res + self.inorder(root.right)
return res
def insert(temp,data):
q = []
q.append(temp)
#level order traversal sampai menemukan tempat yang kosong
while (len(q)):
temp = q[0]
q.pop(0)
if (not temp.left):
temp.left = Node(data)
break
else:
q.append(temp.left)
if (not temp.right):
temp.right = Node(data)
break
else:
q.append(temp.right)
root = Node(5)#root
root.left = Node(7)
root.right = Node(9)
root.left.left = Node(6)
root.left.right = Node(10)
root.right.left = Node(8)
print("Sebelum memasukkan node",end = " ")
print(root.inorder(root))
data = 12
root.insert(data)
print()
print("Setelah memasukkan node",end = " ")
print(root.inorder(root))
Hasil output dari kode di atas
Dalam inorder Traversal, Node 12 berhasil dimasukkan dan menjadi child kanan dari 9
Mungkin itu saja dulu tentang binary tree kalau ada tambahan poin lagi akan saya update..
Post a Comment for "Apa itu Struktur Data Binary Tree ? "
Jangan spam atau promosi di sini jgn juga taruh link aktif kalau mau dapat backlink bisa taruh di profil saja (Name/URL)