Binary TreeHimpunan key karakter berikut ini disisipkan ke dalam suatu binary tree:{B, C, D, A, H, J.... Question from @qed

August 2022 1 25 Report

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.

henriyulianto

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.

Key B disisipkan. Node B menjadi root dari keseluruhan tree. Node B belum mempunyai subtree kiri maupun kanan.
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}$}$
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}$}$
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}$}$
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}$}$
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}$}$
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