Simulic
Bahasa Indonesia

Pohon pencarian biner – sisip, cari, hapus, dan penelusuran pohon

InformatikaAlgoritma dan pemecahan masalahUsia 17–18

Memuat…

Gunakan di kelas saya ✨ Sesuaikan dengan AI Laporkan masalah

Sisipkan, cari, dan hapus kunci dalam pohon pencarian biner, lalu amati jalur perbandingan melalui setiap simpul, tinggi pohon, dan jumlah perbandingan; penghapusan simpul dengan 0, 1, atau 2 anak memakai suksesor inorder. Menyisipkan kunci yang terurut membuat pohon merosot menjadi list, dan tabel hasil membandingkannya dengan urutan penyisipan acak dan seimbang. Mode Penelusuran pohon menjalankan penelusuran preorder, inorder, postorder, dan level-order langkah demi langkah, dan mode Pohon ekspresi menghasilkan notasi prefiks, infiks, dan postfiks.

Pelajaran: Pohon biner dan pohon pencarian biner; penelusuran preorder, inorder, postorder, dan breadth-first; pohon ekspresi dan notasi Polandia

Yang ditunjukkan

Pohon pencarian biner menjaga agar setiap kunci di subpohon kiri lebih kecil dan setiap kunci di subpohon kanan lebih besar daripada kunci simpulnya, sehingga pencarian, penyisipan, dan penghapusan mengikuti satu jalur dari akar dan memerlukan paling banyak h + 1 perbandingan, dengan h adalah tinggi pohon. Urutan penyisipan acak menghasilkan pohon yang cukup pendek, tetapi masukan terurut menghasilkan rantai yang selambat pencarian sekuensial. Penelusuran mengunjungi setiap simpul satu kali: urutan depth-first memakai tumpukan panggilan fungsi rekursif, level-order memakai antrean, dan pada pohon ekspresi penelusuran menghasilkan notasi prefiks, infiks, dan postfiks.

Cara menggunakan

Pada mode Pohon pencarian biner, ketik Kunci lalu klik Sisipkan, Cari, atau Hapus; perbandingan ditampilkan langkah demi langkah. Pilih Urutan penyisipan dan Jumlah kunci, lalu klik Bangun pohon baru untuk menambah baris ke tabel perbandingan. Pada mode Penelusuran pohon, pilih Penelusuran lalu klik Putar atau Langkah. Pada mode Pohon ekspresi, pilih sebuah ekspresi atau ketik ekspresi Anda sendiri.

Parameter yang dapat diubah

  • Mode Pohon pencarian biner, Penelusuran pohon, Pohon ekspresi
  • Urutan penyisipan awal Acak, Menaik (terurut), Kunci tengah dulu (seimbang)
  • Jumlah kunci awal 3–15 kunci
  • Kunci awal yang disisipkan (bilangan 1–99, mis. 50 30 70; kosong = dibuat otomatis)
  • Penelusuran Preorder (NLR), Inorder (LNR), Postorder (LRN), Level-order (BFS)
  • Contoh ekspresi (3 + 4) * 5, 3 + 4 * 5, (8 - 2) / (1 + 2), 2 * (x + 3) - y / 4, (a + b) * (c - d) ^ 2, Kustom
  • Ekspresi kustom (kosong = pakai contoh ekspresi)
  • Kecepatan jalan 0,5–4 langkah/s

Pertanyaan untuk dijelajahi

  1. Berapa tinggi pohon jika tujuh kunci disisipkan secara menaik, dan berapa perbandingan yang diperlukan untuk menemukan kunci terbesar?
  2. Mengapa penelusuran inorder pada pohon pencarian biner selalu menghasilkan kunci dalam urutan menaik?
  3. Bagaimana (3 + 4) * 5 ditulis dalam notasi postfiks, dan mengapa tanda kurung tidak diperlukan?

Simulasi terkait