Mengakses Semua Node Pada Kedalaman Tertentu

by

Mengakses semua node pada kedalaman tertentu umumnya bermanfaat untuk keperluan lain, misalnya digunakan untuk menampilkan struktur tree.

Untuk mengakses node pada kedalaman tertentu mirip dengan proses traversal. 

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

Fungsi memerlukan 2 parameter yaitu depth untuk kedalaman yang akan dicari dan nodes akan berisi list dari node-node pada kedalaman yang dimaksud.

Fungsi akan recursive hingga depth == 0, dan mengembalikan seluruh node pada kedalaman yang dimaksud.

Code dibawah bertujuan menambahkan None value pada list nodes jika node tidak ditemukan pada kedalaman tersebut.

nodes.extend([None]*2**(depth-1))

Jangan lupa tambahkan juga fungsi diatas pada class Tree agar mudah diakses melalui program.

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

Berikut code lengkap dari 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


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)

node = Node(55)

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

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

node.right.right = Node(75)

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

node.left.left.left.left = Node(1)

myTree = Tree(node, 'Basic BST')

print(myTree.getNodeAtDepth(3))
$ python tree.py

[5, 20, None, None, None, None, None, None]

Sesuai ekspektasi, pada kedalaman 3, tree hanya terdapat node dengan value 5 dan 20. Perhatikan nilai None menunjukan node tidak ditemukan pada level tersebut.

Menampilkan Tree Ke Console

Contoh penggunaan fungsi diatas pada fungsi menampilkan tree ke console.

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

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

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

node = Node(55)

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

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

node.right.right = Node(75)

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

node.left.left.left.left = Node(1)

myTree = Tree(node, 'Basic BST')
myTree.printTree()
$ python tree.py
Basic BST 
                              55  
               /                             \
              25                              70
       /             \                 /             \
      15              35              _               75
   /     \         /     \         /     \         /     \
  5       20      _       _       _       _       _       _
 / \     / \     / \     / \     / \     / \     / \     / \
1   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _

Sharing is caring:

Leave a Comment