Materi Tree - Struktur Data

Materi Tree

Pengertian

• Struktur data pohon memiliki akar, ranting, dan daun.
• Perbedaan antara pohon di alam dan pohon dalam ilmu komputer adalah bahwa struktur data pohon memiliki akarnya di bagian atas dan daunnya di bagian bawah.

Beberapa istilah dalam Tree :

• Node adalah bagian mendasar dari sebuah tree.
• Edge menghubungkan dua node untuk menunjukkan bahwa ada hubungan di antara mereka. Setiap node (kecuali root) terhubung dengan tepat satu ujung yang masuk dari node lain.
• Root adalah satu-satunya simpul di tree yang tidak memiliki tepi yang masuk.
• Path adalah daftar node yang disusun secara berurutan. Misalnya, Mammal → → Carnivora → → Felidae → → Felis → → Domestica adalah sebuah jalan.
• Children adalah kumpulan node yang memiliki tepi masuk dari node yang sama dikatakan sebagai children dari node tersebut.
• Parent adalah Sebuah node adalah induk dari semua node yang terhubung dengan tepi keluar. Node di tree yang merupakan anak dari orang tua yang sama dikatakan saudara kandung. The node etc / dan usr / adalah saudara kandung di pohon filesystem.
• Subtree adalah seperangkat node dan ujung-ujungnya terdiri dari parent dan semua childrennya.
• Leaf Node adalah node yang tidak memiliki children.
• Level adalah jumlah sisi pada jalur dari simpul akar ke n. Misalnya, tingkat simpul Felis pada Gambar 1 adalah lima. Secara definisi, level dari root node adalah nol.
• Height sama dengan tingkat maksimum dari setiap simpul di tree.

Parse Tree

Digunakan membuat sebuat tree dari sebuah inputan user.

Algoritma :

Contoh :

Tree Tranversal :
Merupakan sebuah cara untuk menampilkan data tree dalam beberapa tampilan.

• PreOrder dengan operator/ root di depan operand
• InOrder dengan operator/ root di antara operand
• PostOrder dengan operator/ root di belakang operand

Source Code dalam Python :

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

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

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

     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,rootObj):
        self.key = rootObj
        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 setRootVal(self,obj):
        self.key = obj

    def getRootVal(self):
        return self.key



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 preorder(tree):
    if tree != None:
        print(tree.getRootVal(), end=' ')
        preorder(tree.getLeftChild())
        preorder(tree.getRightChild())


def postorder(tree):
    if tree != None:
        postorder(tree.getLeftChild())
        postorder(tree.getRightChild())
        print(tree.getRootVal(), end=' ')


def inorder(tree):
  if tree != None:
      inorder(tree.getLeftChild())
      print(tree.getRootVal(), end=' ')
      inorder(tree.getRightChild())

def postordereval(tree):
    opers = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv}
    res1 = None
    res2 = None
    if tree:
        res1 = postordereval(tree.getLeftChild())
        res2 = postordereval(tree.getRightChild())
        if res1 and res2:
            return opers[tree.getRootVal()](res1,res2)
        else:
            return tree.getRootVal()


pt = buildParseTree("( ( 10 + 5 ) * ( 5 - 6 ) )")


preorder(pt)
print()
postorder(pt)
print()
inorder(pt)
print()
print(postordereval(pt))