Post,In, dan Preorder BinaryTree (Rekursif dan Non-Rekursif)

Post,In, dan Preorder BinaryTree (Rekursif dan Non-Rekursif)

Ada tiga pola umum yang digunkaan untuk mengunjungi semua node dalam tree. Perbedaan antara 3 pola ini adalah urutan kunjungan terhadap node. Kunjungan ini dinamakan “traversal.”, yaitu preorder, inorder dan postorder. Berikut ini adalah definisinya:

1. Preorder
Dalam suatu preorder traversal, node root dikunjungi pertama, kemudian secara rekursif melakukan preorder traversal dari subtree kiri, diikuti oleh suatu preorder traversal rekursif dari subtree kanan.

2. Inorder
Pada suatu inorder traversal, secara rekursif dilakukan inorder traversal pada subtree kiri, mengunjungi node root dan terakhir melakukan inorder traversal rekursif dari subtree kanan.

3. Postorder
Dalam suatu postorder traversal, dilakukan suatu postorder traversal rekursif dari subtree kiri dan subtree kanan diikuti dengan kunjungan ke node root.

Source code :

from __future__ import print_function

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items==[]

    def push(self,items):
        self.items.append(items)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)
 
class Binarytree:
    def __init__(self,root):
        self.key = root
        self.leftChild = None
        self.rightChild = None

    def insertLeft(self,newNode):
        if self.leftChild == None :
            self.leftChild = Binarytree(newNode)

        else :
            t = Binarytree(newNode)
            t.leftChild = self.leftChild
            self.leftChild = t

    def insertRight(self,newNode):
        if self.rightChild == None :
            self.rightChild = Binarytree(newNode)

        else :
            t = Binarytree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t

    def getrightChild(self):
        return self.rightChild

    def getleftChild(self):
        return self.leftChild

    def getrootVal(self):
        return self.key

    def setrootVal(self,obj):
        self.key = obj

    def size(self):
        count = 0
        selfleft = self
        selfright = self
        while selfleft.getleftChild() != None or selfright.getrightChild() != None :
            count += 1
            if selfleft.getleftChild() != None:
                selfleft = selfleft.getleftChild()
            else :
                selfright = selfright.getrightChild()
        return count

#Post,In,Pre dengan Rekursif
def Inorder(root):
    if root!= None:
        Inorder(root.getleftChild())
        print(root.getrootVal(),end=" ")
        Inorder(root.getrightChild())

def Preorder(root):
    if root!= None:
        print(root.getrootVal(),end=" ")
        Preorder(root.getleftChild())
        Preorder(root.getrightChild())

def Postorder(root):
    if root!= None:
        Postorder(root.getleftChild())
        Postorder(root.getrightChild())
        print(root.getrootVal(),end=" ")

#Post,In,Pre tanpa Rekursif
def pre_order(root):
    s=Stack()
    current = root
    s.push(current)
    while not s.isEmpty():
        current = s.pop()
        print(current.getrootVal(),end =" ")
     
        if current.getrightChild()!=None:
            s.push(current.getrightChild())
         
        if current.getleftChild()!=None:
            s.push(current.getleftChild())

def post_order(root):
    s1=Stack()
    s2=Stack()
    current = root
    s1.push(current)
    while not s1.isEmpty():
        current = s1.pop()
        s2.push(current.getrootVal())
         
        if current.getleftChild()!= None:
            s1.push(current.getleftChild())
     
        if current.getrightChild()!=None:
            s1.push(current.getrightChild())
         
    while not s2.isEmpty():
        print(s2.pop(),end=" ")
 
def in_order(root):
    s=Stack()
    current = root
    done = False
    while not done:
        if current != None:
            s.push(current)
            current = current.getleftChild()
        else:
            if s.size() > 0 :
                current = s.pop()
                print(current.getrootVal(),end=" ")
                current = current.getrightChild()
            else:
                done = True
#Main_program
     
root = Binarytree('P')
root.insertLeft('F')
root.getleftChild().insertLeft('B')
root.getleftChild().insertRight('H')
root.getleftChild().getleftChild().insertLeft('A')
root.getleftChild().getrightChild().insertRight('M')
root.insertRight('S')
root.getrightChild().insertLeft("R")
root.getrightChild().insertRight("W")
print ("=".center(40,"="))
print ("Tugas Praktikum 7\nBy : Moh. Irsad(170411100024)")
print ("=".center(40,"="))
print ("Tree :\n")
print(root.getrootVal(),end = " ")
print(root.getleftChild().getrootVal(),end = " ")
print(root.getleftChild().getleftChild().getrootVal(),end = " ")
print(root.getleftChild().getrightChild().getrootVal(),end = " ")
print(root.getleftChild().getleftChild().getleftChild().getrootVal(),end = " ")
print(root.getleftChild().getrightChild().getrightChild().getrootVal(),end = " ")
print(root.getrightChild().getrootVal(),end = " ")
print(root.getrightChild().getleftChild().getrootVal(),end = " ")
print(root.getrightChild().getrightChild().getrootVal())
print ("=".center(25,"="))
print ("No. 1".center(25))
print ("=".center(25,"="))
print ("Menggunakan Rekursif\n")
print ("Inorder :\n")
Inorder(root)
print ()
print ("\nPreorder :\n")
Preorder(root)
print ()
print ("\nPostorder :\n")
Postorder(root)
print ()
print ("=".center(25,"="))
print ("No. 2".center(25))
print ("=".center(25,"="))
print ("Tanpa Menggunakan Rekursif\n")
print ("Inorder :\n")
in_order(root)
print ()
print ("\nPreorder :\n")
pre_order(root)
print ()
print ("\nPostorder :\n")
post_order(root)
print ()
print ("=".center(25,"="))