Question

Buat dan rancanglah program (dalam Python) yang mengimplementasikan struktur Pohon Biner, dilengkapi:
1. method untuk menyisipkan elemen simpul secara terurut, dengan aturan subpohon kiri memiliki simpul-simpul yang berelemen lebih kecil dari subpohon kanan.
2. method untuk melakukan dan menampilkan hasil preorder traversal terhadap pohon biner.

Data/key untuk setiap simpul bertipe string 1 karakter, atau integer (kedua tipe tersebut harus ditangani).
Data/key untuk pengujian: K M J A E S P D C

(Sertakan kode program dan hasil eksekusinya)

Answer 1

Kode Program (Python)

# binary-tree-01.py
# oleh: hy

# Helpers
def ascii_kurangdari(a, b) -> bool:
   return ord(str(a)) < ord(str(b))    
def ascii_lebihdari(a, b) -> bool:
   return ord(str(a)) > ord(str(b))
def list_to_str(l) -> None:
   if len(l) > 0:
       return ', '.join(str(x) for x in l)
   else:
       return 'kosong'

class Simpul:
   # Konstruktor
   def __init__(self, data = None) -> None:
       """KONSTRUKTOR"""
       self.data = data
       self.kiri = None
       self.kanan = None

   # Penyisipan elemen
   def sisipkan(self, data) -> None:
       """Menyisipkan satu elemen data"""
       if self.data:
           if ascii_kurangdari(data, self.data):
               if self.kiri is None:
                   self.kiri = Simpul(data)
               else:
                   self.kiri.sisipkan(data)
           elif ascii_lebihdari(data, self.data):
               if self.kanan is None:
                   self.kanan = Simpul(data)
               else:
                   self.kanan.sisipkan(data)
       else: # self.data is None
           self.data = data

   # Inorder Traversal
   def inorder_traversal(self):
       pass

   # Preorder Traversal
   def preorder_traversal(self):
       hasil = []
       if self.data:
           hasil += [self.data]
       if self.kiri:
           hasil += self.kiri.preorder_traversal()
       if self.kanan:
           hasil += self.kanan.preorder_traversal()
       return hasil

   # Postorder Traversal
   def postorder_traversal(self):
       pass    

class PohonBiner:
   def __init__(self, data = None) -> None:
       """KONSTRUKTOR"""
       self.akar = Simpul(data)

   def sisipkan(self, data) -> None:
       """Shortcut untuk penyisipan elemen"""
       self.akar.sisipkan(data)

   def traversal(self, str_mode):
       """Traversal pohon biner
       str_mode = inorder|preorder|postorder
       """
       return eval(f'self.akar.{str_mode}_traversal()')

   # ----------------------------------------------
   def __repr__(self) -> str:
       # stripped (tidak disertakan, tapi ada kodenya)
       # karena kurang relevan

   def _build_tree_string(
       self,
       simpul: Optional[Simpul],
       curr_index: int,
       include_index: bool = False,
       delimiter: str = "-",
   ) -> tuple:
       """Menelusuri pohon secara rekursif dengan level-order,
       dan mencetak visualisasi pohon.
       """
       # stripped (tidak disertakan, tapi ada kodenya)
       # karena kurang relevan

def main():
   """Program Utama"""
   # Data: K M J A E S P D C
   data = 'K M J A E S P D C'
   pohon = PohonBiner()
   for x in data.split():
       pohon.sisipkan(x)
   print(f'\nVISUALISASI POHON BINER\nData = {data}')
   print(str(pohon))
   mode_traversal = 'preorder'
   print(f'{mode_traversal.upper()} TRAVERSAL: {list_to_str(pohon.traversal("preorder"))}\n')

if __name__ == "__main__":
   main()
___________________

Pembahasan

Pada implementasi dengan program, class utama adalah class Simpul, yang memiliki atribut

• "data" untuk menyimpan data/key dari simpul
• "kiri" untuk menyimpan simpul atau subpohon kiri
• "kanan" untuk menyimpan simpul atau subpohon kanan

Class PohonBiner berperan sebagai wrapper class saja. Tanpa class PohonBiner, class Simpul sudah cukup.

Khusus untuk menangani tipe data dari key/data simpul, digunakan perbandingan dengan nilai kode ASCII dari karakter. Jadi, rancangan struktur data PohonBiner di atas telah dapat mencakup tipe data string atau karakter, dan bilangan bulat. Kekurangannya adalah program ini hanya bisa menangani data dalam bentuk bilangan bulat 1 digit saja, sehingga jika kita menggunakan bilangan, maka banyak maksimum dari simpul adalah 10. Sedangkan jika menggunakan string/karakter, banyak maksimum dari simpul adalah 52, dengan membedakan karakter uppercase dan lowercase.

Kemudian, yang perlu diingat adalah bahwa preorder traversal melakukan penelusuran terhadap semua simpul pohon biner dengan urutan node/simpul - subpohon kiri - subpohon kanan. Yang pertama diambil adalah data simpul, kemudian secara rekursif menelusuri subpohon kiri secara preorder, lalu subpohon kanan.

Pada program di atas, terdapat method-method traversal yang lain, yang berisi "pass" saja. Maksudnya adalah sebagai template, siapa tahu di waktu mendatang akan dilengkapi.

Contoh hasil eksekusi program dapat dilihat pada gambar tangkapan layar yang disertakan.