Binary TreeHimpunan key karakter berikut ini disisipkan ke dalam suatu

Berikut ini adalah pertanyaan dari unknown pada mata pelajaran TI untuk jenjang Sekolah Dasar

Binary TreeHimpunan key karakter berikut ini disisipkan ke dalam suatu binary tree:
{B, C, D, A, H, J, E}

Gambarkanlah struktur binary tree tersebut, dan jabarkan penelusuran node (traversal) secara preorder, inorder, dan postorder.

Jawaban dan Penjelasan

Berikut ini adalah pilihan jawaban terbaik dari pertanyaan diatas.

Gambar struktur binary tree:
\large\text{$\begin{array}{c}\tt B\\/\!\!\quad\!\backslash\\\tt A\!\!\!\qquad\!\!C\\\qquad\quad\!\!\backslash\\\qquad\qquad\!\!\!\tt D\\\qquad\qquad\,\backslash\\\tt\qquad\qquad\ \ \,H\\\qquad\qquad\quad\!/\,\backslash\\\tt\qquad\qquad\quad\!E\ \ J\\\end{array}$}

Traversal:

  • Preorder: B A C D H E J
  • Inorder: A B C D E H J
  • Postorder: A E J H D C B

Pembahasan

Proses pembentukan binary tree

Pada jawaban ini, saya menggunakan skema binary sorted tree, di mana node yang lebih kecil nilainya ditempatkan pada subtree kiri, dan node yang lebih besar nilainya ditempatkan pada subtree kanan.

Himpunan key: {B, C, D, A, H, J, E}. Kondisi inisial: Tree masih kosong.

  1. Key B disisipkan. Node B menjadi root dari keseluruhan tree. Node B belum mempunyai subtree kiri maupun kanan.
  2. Key C disisipkan. Karena C > B, maka C ditempatkan pada subtree kanan dari node B.
    \large\text{$\begin{array}{c}\tt B\\\quad\!\backslash\\\qquad\!\tt C\\\end{array}$}
  3. Key D disisipkan. Karena D > C > B, maka D ditempatkan pada subtree kanan dari node C.
    \large\text{$\begin{array}{c}\tt B\\\quad\!\backslash\\\qquad\!\!\tt C\\\qquad\quad\!\!\backslash\\\qquad\qquad\!\!\!\tt D\end{array}$}
  4. Key A disisipkan. Karena A < B, maka A ditempatkan pada subtree kiri dari node B.
    \large\text{$\begin{array}{c}\tt B\\/\!\!\quad\!\backslash\\\tt A\!\!\!\qquad\!\!C\\\qquad\quad\!\!\backslash\\\qquad\qquad\!\!\!\tt D\end{array}$}
  5. Key H disisipkan. Karena H > D > C > B, maka H ditempatkan pada subtree kanan dari node D.
    \large\text{$\begin{array}{c}\tt B\\/\!\!\quad\!\backslash\\\tt A\!\!\!\qquad\!\!C\\\qquad\quad\!\!\backslash\\\qquad\qquad\!\!\!\tt D\\\qquad\qquad\,\backslash\\\tt\qquad\qquad\ \ H\end{array}$}
  6. Key J disisipkan. Karena J > H > D > C > B, maka J ditempatkan pada subtree kanan dari node H.
    \large\text{$\begin{array}{c}\tt B\\/\!\!\quad\!\backslash\\\tt A\!\!\!\qquad\!\!C\\\qquad\quad\!\!\backslash\\\qquad\qquad\!\!\!\tt D\\\qquad\qquad\,\backslash\\\tt\qquad\qquad\ \ \,H\\\qquad\qquad\quad\ \ \backslash\\\tt\qquad\qquad\qquad\ J\\\end{array}$}
  7. Key E disisipkan. E > D, dan subtree kiri dari D masih kosong. Namun, E harus berada di subtree kanan dari D. Sedangkan subtree kanan dari node D sudah terisi node H. Maka, karena E < H, E ditempatkan sebagai subtree kiri dari node H.
    \large\text{$\begin{array}{c}\tt B\\/\!\!\quad\!\backslash\\\tt A\!\!\!\qquad\!\!C\\\qquad\quad\!\!\backslash\\\qquad\qquad\!\!\!\tt D\\\qquad\qquad\,\backslash\\\tt\qquad\qquad\ \ \,H\\\qquad\qquad\quad\!/\,\backslash\\\tt\qquad\qquad\quad\!E\ \ J\\\end{array}$}

Selesai.
\blacksquare

Traversal

  • Traversal Preorder (Node, Left, Right)
    Proses: B A C {} D {} H E J
    B A C D H E J
  • Traversal Inorder (Left, Node, Right)
    Proses: A B {} C {} D E H J
    A B C D E H J
  • Traversal Postorder (Left, Right, Node)
    Proses: A {} {} E J H D C B
    A E J H D C B

Semoga dengan pertanyaan yang sudah terjawab oleh henriyulianto dapat membantu memudahkan mengerjakan soal, tugas dan PR sekolah kalian.

Apabila terdapat kesalahan dalam mengerjakan soal, silahkan koreksi jawaban dengan mengirimkan email ke yomemimo.com melalui halaman Contact

Last Update: Mon, 14 Nov 22