Pokok Binari Lengkap lwn Pokok Perduaan Penuh
Pokok binari ialah 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 induknya. Pokok binari lengkap ialah pokok binari di mana setiap peringkat pokok binari diisi sepenuhnya kecuali tahap terakhir. Dalam tahap tidak terisi, nod dilampirkan bermula dari kedudukan paling kiri. Pokok binari penuh ialah pokok di mana setiap nod dalam pokok itu mempunyai dua anak kecuali daun pokok.
Apakah Pokok Binari Penuh?
Pokok binari penuh ialah pokok perduaan di mana setiap nod dalam pepohon mempunyai betul-betul sifar atau dua anak. Dalam erti kata lain, setiap nod dalam pokok kecuali daun mempunyai dua anak. Rajah 1 di bawah menggambarkan pokok binari penuh. Dalam pokok binari penuh, bilangan nod (n), bilangan laves (l) dan bilangan nod dalaman (i) adalah berkaitan dengan cara yang istimewa supaya jika anda mengetahui mana-mana satu daripadanya anda boleh menentukan dua yang lain. nilai seperti berikut:
1. Jika pepohon binari penuh mempunyai nod dalaman i:
– Bilangan daun l=i+1
– Jumlah bilangan nod n=2i+1
2. Jika pokok binari penuh mempunyai n nod:
– Bilangan nod dalaman i=(n-1)/2
– Bilangan daun l=(n+1)/2
3. Jika pokok binari penuh mempunyai l daun:
– Jumlah Bilangan nod n=2l-1
– Bilangan nod dalaman i=l-1
Apakah Pokok Binari Lengkap?
Seperti yang ditunjukkan dalam rajah 2, pokok binari lengkap ialah pokok binari di mana setiap peringkat pokok itu diisi sepenuhnya kecuali tahap terakhir. Juga, di peringkat terakhir, nod harus dilampirkan bermula dari kedudukan paling kiri. Pokok binari lengkap ketinggian h memenuhi syarat berikut:
– Daripada nod akar, tahap di atas tahap terakhir mewakili pokok binari penuh ketinggian h-1
– Satu atau lebih nod pada tahap terakhir mungkin mempunyai 0 atau 1 anak
– Jika a, b ialah dua nod dalam tahap di atas tahap terakhir, maka a mempunyai lebih ramai anak daripada b jika dan hanya jika a terletak di sebelah kiri b
Apakah perbezaan antara Pokok Binari Lengkap dan Pokok Binari Penuh?
Pokok binari lengkap dan pokok binari penuh mempunyai perbezaan yang jelas. Walaupun pokok binari penuh ialah pokok binari di mana setiap nod mempunyai sifar atau dua anak, pokok binari lengkap ialah pokok binari di mana setiap peringkat pokok binari diisi sepenuhnya kecuali tahap terakhir. Sesetengah struktur data khas seperti timbunan perlu menjadi pokok binari yang lengkap manakala ia tidak perlu menjadi pokok binari penuh. Dalam pokok binari penuh, jika anda mengetahui bilangan jumlah nod atau bilangan lave atau bilangan nod dalaman, anda boleh mencari dua yang lain dengan mudah. Tetapi pokok perduaan yang lengkap tidak mempunyai sifat khas yang berkaitan dengan tiga atribut ini.
