uraikan ciri ciri struktur data tree (struktur pohon)

<p>Struktur data <strong>tree (pohon)</strong> adalah salah satu struktur data yang digunakan untuk merepresentasikan hierarki dan hubungan antar elemen dalam bentuk yang menyerupai pohon. Berikut adalah ciri-ciri utama dari struktur data tree:</p><p>1. <strong>Node (Simpul)</strong></p><ul><li><strong>Root (Akar)</strong>: Node paling atas dalam pohon yang tidak memiliki parent (induk). Setiap pohon memiliki satu root node.</li><li><strong>Leaf (Daun)</strong>: Node yang tidak memiliki child (anak). Mereka adalah node paling bawah dalam pohon.</li><li><strong>Internal Node</strong>: Node yang memiliki child node, berbeda dengan leaf node.</li></ul><p>2. <strong>Edge (Sisi)</strong></p><ul><li>Merupakan hubungan atau koneksi antara dua node. Setiap edge menghubungkan dua node, yaitu parent dan child.</li></ul><p>3. <strong>Parent (Induk) dan Child (Anak)</strong></p><ul><li><strong>Parent</strong>: Node yang memiliki cabang menuju node lainnya.</li><li><strong>Child</strong>: Node yang merupakan hasil cabang dari node lainnya. Setiap node bisa memiliki lebih dari satu child, tetapi hanya satu parent.</li></ul><p>4. <strong>Subtree (Subpohon)</strong></p><ul><li>Bagian dari pohon yang terdiri dari node tertentu dan semua keturunannya. Setiap node dalam pohon dapat dianggap sebagai root dari subtree-nya sendiri.</li></ul><p>5. <strong>Level dan Depth (Kedalaman)</strong></p><ul><li><strong>Level</strong>: Menunjukkan posisi atau kedalaman suatu node dalam pohon, dihitung dari root node (level root adalah 0).</li><li><strong>Depth</strong>: Jarak dari root node ke node tertentu, dihitung dengan jumlah edge dari root ke node tersebut.</li></ul><p>6. <strong>Height (Tinggi)</strong></p><ul><li>Tinggi sebuah node adalah panjang dari jalur terpanjang dari node tersebut ke leaf node.</li><li>Tinggi sebuah pohon adalah tinggi dari root node, atau bisa juga didefinisikan sebagai level maksimum dari pohon.</li></ul><p>7. <strong>Degree (Derajat)</strong></p><ul><li><strong>Degree dari Node</strong>: Jumlah child yang dimiliki oleh node tersebut.</li><li><strong>Degree dari Pohon</strong>: Derajat maksimum dari semua node dalam pohon.</li></ul><p>8. <strong>Binary Tree (Pohon Biner)</strong></p><ul><li>Pohon di mana setiap node memiliki paling banyak dua child, sering disebut left child (anak kiri) dan right child (anak kanan).</li></ul><p>9. <strong>Balanced Tree (Pohon Seimbang)</strong></p><ul><li>Pohon di mana tinggi dari dua subtree dari setiap node berbeda paling banyak satu. Contoh terkenal adalah AVL Tree dan Red-Black Tree.</li></ul><p>10. <strong>Traversal (Penelusuran)</strong></p><ul><li><strong>Preorder Traversal</strong>: Mengunjungi root node, kemudian subtree kiri, lalu subtree kanan.</li><li><strong>Inorder Traversal</strong>: Mengunjungi subtree kiri, kemudian root node, lalu subtree kanan.</li><li><strong>Postorder Traversal</strong>: Mengunjungi subtree kiri, kemudian subtree kanan, lalu root node.</li><li><strong>Level-order Traversal</strong>: Mengunjungi node dalam level yang sama dari kiri ke kanan, satu level pada satu waktu.</li></ul><p>Contoh Struktur Pohon</p><p>mathematica</p><p>Salin kode</p><p>&nbsp; &nbsp; &nbsp; &nbsp;A &nbsp; &nbsp; &nbsp;/ \ &nbsp; &nbsp; B &nbsp; C &nbsp; &nbsp;/ \ &nbsp; \ &nbsp; D &nbsp; E &nbsp; F </p><ul><li><strong>Root</strong>: A</li><li><strong>Leaf Nodes</strong>: D, E, F</li><li><strong>Internal Nodes</strong>: A, B, C</li><li><strong>Level</strong>: A (0), B dan C (1), D, E, dan F (2)</li><li><strong>Degree of Node B</strong>: 2 (D dan E)</li><li><strong>Height of Node B</strong>: 1 (karena D dan E adalah leaf node)</li><li><strong>Height of Tree</strong>: 2 (dari A ke D/E/F)</li></ul>