Pokok Binari Lengkap vs Pokok Perduaan Penuh
Pokok binari adalah pokok di mana setiap nod mempunyai satu atau dua anak. Dalam pokok binari, nod tidak boleh mempunyai lebih daripada dua anak. Dalam pokok binari, kanak-kanak dinamakan sebagai kanak-kanak "kiri" dan "kanan". Nod anak mengandungi rujukan kepada ibu bapa mereka. Pokok binari lengkap adalah pokok binari di mana setiap peringkat pokok binari diisi sepenuhnya kecuali tahap terakhir. Pada tahap yang tidak diisi, nod dilampirkan bermula dari kedudukan paling kiri. Pokok binari penuh adalah pokok di mana setiap simpul di dalam pokok mempunyai dua anak kecuali daun pokok.
Apa itu Pokok Perduaan Penuh?
Pokok binari penuh adalah pokok binari di mana setiap simpul di pokok mempunyai anak-anak yang betul-betul sifar atau dua. Dengan kata lain, setiap simpul di pokok kecuali daun mempunyai dua anak. Gambar 1 di bawah menunjukkan pokok binari penuh. Dalam pokok binari penuh, bilangan nod (n), bilangan laves (l) dan bilangan nod dalaman (i) berkaitan dengan cara khas sehingga jika anda mengetahui salah satu daripadanya, anda dapat menentukan dua yang lain nilai seperti berikut:
1. Sekiranya pokok binari penuh mempunyai nod dalaman:
- Bilangan daun l = i + 1
- Jumlah node n = 2 * i + 1
2. Sekiranya pokok binari penuh mempunyai n nod:
- Bilangan nod dalaman i = (n-1) / 2
- Bilangan daun l = (n + 1) / 2
3. Sekiranya pokok binari penuh mempunyai daun:
- Jumlah Node n = 2 * l-1
- Bilangan nod dalaman i = l-1
Apakah Pokok Perduaan Lengkap?
Seperti yang ditunjukkan dalam gambar 2, pokok binari lengkap adalah pokok binari di mana setiap peringkat pokok diisi sepenuhnya kecuali tahap terakhir. Juga, pada tahap terakhir, simpul harus dilampirkan bermula dari kedudukan paling kiri. Pokok binari lengkap dengan ketinggian h memenuhi syarat berikut:
- Dari simpul akar, tahap di atas tahap terakhir mewakili pokok binari penuh dengan ketinggian h-1
- Satu atau lebih nod di peringkat terakhir mungkin mempunyai 0 atau 1 anak
- Jika a, b adalah dua node pada tahap di atas tahap terakhir, maka a mempunyai lebih banyak anak daripada b jika dan hanya jika a terletak di sebelah kiri b
Apakah perbezaan antara Pokok Perduaan Lengkap dan Pokok Binari Penuh?
Pokok binari lengkap dan pokok binari penuh mempunyai perbezaan yang jelas. Walaupun pokok binari penuh adalah pokok binari di mana setiap simpul mempunyai sifar atau dua anak, pokok binari lengkap adalah pokok binari di mana setiap peringkat pokok binari diisi sepenuhnya kecuali tahap terakhir. Beberapa struktur data khas seperti timbunan mestilah pokok binari lengkap sementara mereka tidak perlu menjadi pokok binari penuh. Dalam pokok binari penuh, jika anda mengetahui jumlah node total atau bilangan laves atau bilangan nod dalaman, anda dapat mencari dua yang lain dengan sangat mudah. Tetapi pokok binari yang lengkap tidak mempunyai harta khas yang berkaitan dengan tiga sifat ini.
