Menambahkan Node Ke Binary Search Tree

Menambahkan node ke binary search tree cukup mudah. Logikanya mirip fungsi search yang dibahas pada modul sebelumnya.

def addNode(self, val):
    if self.data == val:
        return
    
    if val < self.data:
        if self.left is None:
            self.left = Node(val)
        else:
            self.left.addNode(val)
    
    if val > self.data:
        if self.right is None:
            self.right = Node(val)
        else:
            self.right.addNode(val)

Pembahasan Code

Buat fungsi baru dengan nama addNode dengan parameter value dari node yang akan ditambahkan.

Jika value terdapat dalam node, maka fungsi tidak akan melakukan tindakan. Ingat value node binary search tree harus unique.

Jika value lebih kecil dari node saat ini, cek apakah kaki kiri dari current node adalah None. Jika None, tambahkan node, jika tidak lakukan recursive dengan memanggil fungsi yang sama.

Lakukan hal yang sama untuk kaki kanan.

Tambahkan juga fungsi ini pada class wrapper Tree.

def addNode(self, val):
    self.root.addNode(val)

Berikut isi lengkap program 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)

    def height(self, h=0):
        leftHeight = self.left.height(h+1) if self.left else h
        rightHeight = self.right.height(h+1) if self.right else h
        return max(leftHeight, rightHeight)

    def getNodeAtDepth(self, depth, nodes=[]):
        if depth==0:
            nodes.append(self.data)
            return nodes

        if self.left:
            self.left.getNodeAtDepth(depth-1, nodes)
        else:
            nodes.extend([None]*2**(depth-1))

        if self.right:
            self.right.getNodeAtDepth(depth-1, nodes)
        else:
            nodes.extend([None]*2**(depth-1))

        return nodes

    def addNode(self, val):
        if self.data == val:
            return
        
        if val < self.data:
            if self.left is None:
                self.left = Node(val)
            else:
                self.left.addNode(val)
        
        if val > self.data:
            if self.right is None:
                self.right = Node(val)
            else:
                self.right.addNode(val)


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()

    def height(self):
        return self.root.height()

    def getNodeAtDepth(self, depth):
        return self.root.getNodeAtDepth(depth)

    def _nodeToChar(self, n, space):
        if n is None:
            return '_' + (' '*space)
        space = space - len(str(n))+1
        return str(n)+(' '*space)

    def printTree(self, label=''):
        print(self.name + ' ' + label)
        height = self.root.height()
        space = 3
        width = int((2**height-1) * (space+1) +1)

        offset = int((width-1)/2)
        for depth in range(0, height+1):
            if depth>0:
                print(' '*(offset+1) + (' '*(space+2)).join(['/' + (' '*(space-2)) + '\\']*(2**(depth-1))))
            row = self.root.getNodeAtDepth(depth, [])
            print ((' '*offset)+ ''.join([self._nodeToChar(n,space) for n in row]))
            space = offset + 1
            offset = int(offset/2)-1
        print ('')

    def addNode(self, val):
        self.root.addNode(val)

node = Node(55)

node.left = Node(25)
node.right = Node(70)

myTree = Tree(node, 'Basic BST')
myTree.addNode(10)
myTree.addNode(100)
myTree.addNode(60)
myTree.printTree()

$ python tree.py
Basic BST 
      55
   /     \        
  25      70      
 / \     / \      
10  _   60  100

Sesuai ekspetasi, node ditambahkan sesuai dengan aturan binary search tree.