Skip to content Skip to sidebar Skip to footer

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

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 :

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 :

tes implementasi tree python
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 :

tes in-order traversal

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 :

tes pre-order traversal
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 :

tes post order traversal

Memasukkan Node ke Dalam Binary Tree

Misal saya punya binary tree seperti ini

binary tree sebelum insert

Kemudian saya ingin memasukkan node 12 di samping node 8 maka akhirnya akan jadi seperti ini binary tree nya

binary tree sesudah insert


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 ? "