TREE

TREE

1.     PENGERTTIAN TREE

Kumpulan node yang saling terhubung satu sama lain dalam suatu kesatuan yang membentuk layaknya struktur sebuah pohon. Struktur pohon adalah suatu cara merepresentasikan suatu struktur hirarki (one-to-many) secara grafis yang mirip sebuah pohon, walaupun pohon tersebut hanya tampak sebagai kumpulan node-node dari atas ke bawah. Suatu struktur data yang tidak linier yang menggambarkan hubungan yang hirarkis (one-to-many) dan tidak linier antara elemen-elemennya.

2.     ISTILAH DALAM TREE

Ø  Prodecessor : node yang berada diatas node tertentu.

Ø  Successor : node yang berada di bawah node tertentu.

Ø  Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.

Ø  Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.

Ø  Parent : predecssor satu level di atas suatu node.

Ø  Child : successor satu level di bawah suatu node.

Ø  Sibling : node-node yang memiliki parent yang sama dengan suatu node.

Ø  Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.

Ø  Size : banyaknya node dalam suatu tree.

Ø  Height : banyaknya tingkatan/level dalam suatu tree.

Ø  Root : satu-satunya node khusus dalam tree yang tak punya predecssor.

Ø  Leaf : node-node dalam tree yang tak memiliki seccessor.

Ø  Degree : banyaknya child yang dimiliki suatu node.

3.     JENIS-JENIS BINARY TREE

Tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua sub pohon dan kedua subpohon harus terpisah. Berikut Kelebihan struktur Binary Tree :

Ø  Mudah dalam penyusunan algoritma sorting

Ø  Searching data relatif cepat

Ø  Fleksibel dalam penambahan dan penghapusan data

4.     IMPLEMENTASI ALGORITMA TREE

Ø  Insert

Insert yaitu menambahkan node dalam tree. Jika data yang akan dimasukkan lebih besar daripada elemen root, maka akan diletakkan di node sebelah kanan, sebaliknya jika lebih kecil maka akan diletakkan di node sebelah kiri. Untuk data pertama akan menjadi elemen root.

Ø  PreOrder

PreOrder yaitu cetak node yang dikunjungi,kunjungi left, kunjungi right.

Ø  InOrder

InOrder yaitu kunjungi left, cetak node yang dikunjungi, kunjungi right.

Ø  PostOrder

PostOrder yaitu kunjungi left, kunjungi right, cetak node yang dikunjungi.

Ø  Searching Data

Searching Data yaitu untuk searching data kita tinggal menjelajahi node yang ada di dalam tree, algoritmanya adalah jika data yang di cari sama dengan root maka data di temukan,jika tidak maka akan mengecek kembali apakah data lebih lebih kecil dari root maka secara rekursi akan mencari kekiri, jika data lebih besar dari root maka secara rekursif akan mencari ke kanan.

5.     CONTOH 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

def Inorder(root):

    if root:

        Inorder(root.getleftChild())

        print(root.getrootVal(),end=" ")

        Inorder(root.getrightChild())

def Preorder(root):

    if root:

        print(root.getrootVal(),end=" ")

        Preorder(root.getleftChild())

        Preorder(root.getrightChild())

def Postorder(root):

    if root:

        Postorder(root.getleftChild())

        Postorder(root.getrightChild())

        print(root.getrootVal(),end=" ")

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

Inorder(root)

print ()

Preorder(root)

print ()

Postorder(root)

Di post oleh :

1. FITRI ANISA (170411100014)

2. DHEA OKY SYAFITRI (170411100006)