TI 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. ​

ursulastreichulv – June 10, 2023

Binary Tree

Himpunan 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.
​

Gambar struktur binary tree:
[tex]\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}$}[/tex]

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.
   [tex]\large\text{$\begin{array}{c}\tt B\\\quad\!\backslash\\\qquad\!\tt C\\\end{array}$}[/tex]
3. Key D disisipkan. Karena D > C > B, maka D ditempatkan pada subtree kanan dari node C.
   [tex]\large\text{$\begin{array}{c}\tt B\\\quad\!\backslash\\\qquad\!\!\tt C\\\qquad\quad\!\!\backslash\\\qquad\qquad\!\!\!\tt D\end{array}$}[/tex]
4. Key A disisipkan. Karena A < B, maka A ditempatkan pada subtree kiri dari node B.
   [tex]\large\text{$\begin{array}{c}\tt B\\/\!\!\quad\!\backslash\\\tt A\!\!\!\qquad\!\!C\\\qquad\quad\!\!\backslash\\\qquad\qquad\!\!\!\tt D\end{array}$}[/tex]
5. Key H disisipkan. Karena H > D > C > B, maka H ditempatkan pada subtree kanan dari node D.
   [tex]\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}$}[/tex]
6. Key J disisipkan. Karena J > H > D > C > B, maka J ditempatkan pada subtree kanan dari node H.
   [tex]\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}$}[/tex]
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.
   [tex]\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}$}[/tex]

Selesai.
[tex]\blacksquare[/tex]

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

[answer.2.content]