Binary Tree

Definisi

            Binary Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkanhubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya ( disebut subtree).

            Dalam tree terdapat jenis-jenis tree yang memiliki sifat khusus, diantaranya adalah binary tree.

                            Binary tree adalah suatu tree dengan syarat bahawa tiap node (simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul), secara khusus anaknya  dinamakan kiri dan kanan.

                          Binary Tree merupakan himpunan  vertex-vertex yang terdiri dari 2 subtree (dengan disjoint) yaitu subtree kiri dan subtree kanan. Setiap vertex dalam binary tree mempunyai derajat keluar max =2. 

     Ilustrasi

Algoritma

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 setRootVal(self,obj):

        self.key = obj

    def getRootVal(self):

        return self.key

Kode Program

import Stack

import BinaryTree

def buildParseTree(fpexp):

    fplist = fpexp.split()

    pStack = Stack()

    eTree = BinaryTree('')

    pStack.push(eTree)

    currentTree = eTree

    for i in fplist:

        if i == '(':

            currentTree.insertLeft('')

            pStack.push(currentTree)

            currentTree = currentTree.getLeftChild()

        elif i not in ['+', '-', '*', '/', ')']:

            currentTree.setRootVal(int(i))

            parent = pStack.pop()

            currentTree = parent

        elif i in ['+', '-', '*', '/']:

            currentTree.setRootVal(i)

            currentTree.insertRight('')

            pStack.push(currentTree)

            currentTree = currentTree.getRightChild()

        elif i == ')':

            currentTree = pStack.pop()

        else:

            raise ValueError

    return eTree

def postorder(tree):

    while tree != None:

        print(tree.getRootVal())

def preorder(tree):

    while tree:

        print(tree.getRootVal())

def inorder(tree):

  while tree != None:

      print(tree.getRootVal())

pt = buildParseTree("( ( 10 + 5 ) * 3 )")

print("== postorder ==")

pt.postorder()

print("== preorder ==")

pt.preorder()

print("== inorder ==")

pt.inorder()