Membuat Fungsi Traversal pada Binary Search Tree

Traversal bertujuan menemukan atau mengunjungi setiap node dari tree. Terdapat 3 metoda traversal yang umum digunakan, yaitu:

• Pre-Order akan mulai dari root, lalu selalu mengunjungi node paling kiri dahalu sampai habis, lalu kekanan.
• In-Order akan memulai dari nilai dari yang paling kecil.
• Post-Order akan dimulai dari node paling kiri, kemudian kekanan, baru mengunjungi parent.

Untuk lebih jelasnya lihat gambar dibawah.

Tambahkan fungsi traversal pada class Node

def traversePreorder(self):
    print(self.data)

    if self.left:
        self.left.traversePreorder()
    
    if self.right:
        self.right.traversePreorder()

def traverseInorder(self):
    if self.left:
        self.left.traverseInorder()

    print(self.data)

    if self.right:
        self.right.traverseInorder()

def traversePostorder(self):
    if self.left:
        self.left.traversePostorder()
    
    if self.right:
        self.right.traversePostorder()
    
    print(self.data)

Dapat diperhatikan dari code diatas, fungsi traverse dapat dibedakan hanya dengan memindahkan posisi perintah print. Dimana pre-order ada diawal fungsi, in-order ada ditengah fungsi dan post-order diakhir fungsi.

Tambahkan juga fungsi traverse pada class Tree.

def traversePreorder(self):
    self.root.traversePreorder()

def traverseInorder(self):
    self.root.traverseInorder()

def traversePostorder(self):
    self.root.traversePostorder()

Berikut isi lengkap code tree

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
    
    def search(self, target):
        if self.data == target:
            print("Node found")
            return self
        
        if self.left and self.data > target:
            return self.left.search(target)

        if self.right and self.data < target:
            return self.right.search(target)

        print("No Node Found")

    def traversePreorder(self):
        print(self.data)
        if self.left:
            self.left.traversePreorder()
        
        if self.right:
            self.right.traversePreorder()

    def traverseInorder(self):
        if self.left:
            self.left.traverseInorder()
        print(self.data)
        if self.right:
            self.right.traverseInorder()

    def traversePostorder(self):
        if self.left:
            self.left.traversePostorder()
        
        if self.right:
            self.right.traversePostorder()
        
        print(self.data)

class Tree:
    def __init__(self, root, name=''):
        self.root = root
        self.name = name

    def search(self, target):
        return self.root.search(target)

    def traversePreorder(self):
        self.root.traversePreorder()

    def traverseInorder(self):
        self.root.traverseInorder()

    def traversePostorder(self):
        self.root.traversePostorder()

node = Node(10)

node.left = Node(5)
node.right = Node(15)

node.left.left = Node(3)
node.left.right = Node(6)

node.right.left = Node(12)
node.right.right = Node(30)

myTree = Tree(node, 'Basic BST')

print("PreOrder")
myTree.traversePreorder()
print("\n")

print("InOrder")
myTree.traverseInorder()
print("\n")

print("PostOrder")
myTree.traversePostorder()
print("\n")

PS F:\Project\bst> python tree.py
PreOrder
10     
5      
3      
6      
15     
12     
30     
       
       
InOrder
3      
5
6
10
12
15
30


PostOrder
3
6
5
12
30
15
10