Question

(Lanjutan dari tugas sebelumnya)
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 inorder traversal terhadap pohon biner.
3. method untuk melakukan dan menampilkan hasil postorder 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-02.py
# Lanjutan dari binary-tree-01.py
# oleh: hy

from typing import Optional

# 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(f'[bold bright_cyan]{str(x)}[/]' for x in l)
   else:
       return 'kosong'

class Simpul:
   def __init__(self, data = None) -> None:
       """KONSTRUKTOR"""
       self.data = data
       self.kiri = None
       self.kanan = None
  def sisipkan(self, data) -> None:
       """Penyisipan elemen"""
       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
  def inorder_traversal(self):
       """Inorder Traversal
       LNR = Left - Node - Right
       Implementasi dengan stack.
       """
       hasil = []; simpul_skrg = self
       s = [] # stack
       while True:
           if simpul_skrg is not None:
               s.append(simpul_skrg) # push
               simpul_skrg = simpul_skrg.kiri
           elif s:
               simpul_skrg = s.pop()
               hasil.append(simpul_skrg.data)
               simpul_skrg = simpul_skrg.kanan
           else:
               break
       return hasil
  def preorder_traversal(self):
       """Preorder Traversal
       NLR = Node - Left - Right
       """
       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
   def postorder_traversal(self):
       """Postorder Traversal
       LRN = Left - Right - Node
       Implementasi dengan stack.
       """
       hasil = []; simpul_skrg = self
       s = [] # stack
       while True:
           while simpul_skrg:
               if simpul_skrg.kanan is not None:
                   s.append(simpul_skrg.kanan)
               s.append(simpul_skrg)
               simpul_skrg = simpul_skrg.kiri
           simpul_skrg = s.pop()
           if simpul_skrg.kanan is not None and\
           len(s) > 0 and\
           s[-1] == simpul_skrg.kanan:
               s.pop()
               s.append(simpul_skrg)
               simpul_skrg = simpul_skrg.kanan
           else:
               hasil.append(simpul_skrg.data)
               simpul_skrg = None
           if len(s) <= 0:
               break
       return hasil    

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():
   # 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 = ['inorder', 'preorder', 'postorder']
   for str_mode in mode_traversal:
       print(f'=> {str_mode.upper()}TRAVERSAL:', end=' ')
       print(list_to_str(pohon.traversal(str_mode)))
   print()

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

Pembahasan

Nah, ternyata pertanyaan/tugas di tautan brainly.co.id/tugas/51854764 ada kelanjutannya.

Untuk tugas ini, kita hanya tinggal melengkapi dengan method inorder dan postorder traversal. Selain menyelesaikan tugas ini, program di atas juga melengkapi tugas sebelumnya.

Jika sebelumnya preorder traversal dilakukan secara rekursif, kali ini, agar tidak monoton dan dapat menambah wawasan sekaligus keterampilan memprogram, method untuk inorder traversal dan postorder traversal kita kerjakan dengan algoritma iteratif menggunakan Stack.

Inorder Traversal secara singkat dapat dinyatakan dengan Left - Node - Right (LNR). Dengan stack, prinsipnya adalah selama simpul tidak kosong, ambil subpohon kiri, dan push ke stack. Jika subpohon kiri kosong, pop (ambil) setiap simpul dari stack, dan proses subpohon kanan dari simpul yang di-pop tersebut, sambil memasukkan hasil pop ke dalam sebuah array/list.

Untuk Postorder Traversal (Left - Right - Node / LRN), prinsipnya hampir sama, namun perlu penanganan khusus karena simpul akar dari setiap subpohon dicetak terakhir.

Dengan cara iteratif seperti ini, kita telah menerapkan backtracking sederhana.

Silahkan amati kode programnya.

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