Perbezaan Antara Pokok Perduaan Lengkap dan Pokok Perduaan Penuh

Pokok Perduaan 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 orang anak. Dalam pokok binari, kanak-kanak dinamakan sebagai "kiri" dan "kanan" kanak-kanak. Nod kanak-kanak mengandungi rujukan kepada ibu bapa mereka. Pokok binari lengkap ialah pokok binari di mana setiap peringkat pokok binari sepenuhnya diisi kecuali tahap terakhir. Dalam tahap yang tidak dibina, nod dilampirkan bermula dari kedudukan paling kiri. Pokok binari penuh ialah pokok di mana setiap nod di dalam pokok mempunyai dua anak kecuali daun pokok.

Apakah Pokok Perduaan Penuh?

Pokok binari penuh adalah pokok binari di mana setiap nod di dalam pokok itu mempunyai sifar atau dua anak. Dalam erti kata lain, setiap nod di pokok kecuali daun mempunyai dua anak. Rajah 1 di bawah menggambarkan pokok binari penuh. Dalam pokok binari yang penuh, bilangan nod (n), bilangan lave (l) dan bilangan nod dalaman (i) dikaitkan dengan cara yang istimewa supaya jika anda mengetahui mana-mana satu daripada anda, anda boleh menentukan dua yang lain nilai seperti berikut:

1. Jika pokok binari penuh mempunyai nod dalaman:

- Bilangan daun l = i + 1

- Jumlah nod n = 2 * i + 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:

- Jumlah nod n = 2 * l-1

- Bilangan nod dalaman i = l-1

Apakah Pokok Perduaan Lengkap?

Seperti yang ditunjukkan dalam rajah 2, pokok binari yang lengkap adalah pokok binari di mana setiap peringkat pokok diisi sepenuhnya kecuali tahap terakhir. Juga, pada peringkat terakhir, nod harus dilampirkan bermula dari kedudukan paling kiri. Pokok binari lengkap ketinggian h memenuhi syarat-syarat berikut:

- Dari nod akar, tahap di atas paras terakhir mewakili pokok binari penuh ketinggian h-1

- Satu atau lebih nod dalam tahap terakhir mungkin mempunyai 0 atau 1 kanak-kanak

- Jika a, b adalah dua nod di peringkat di atas tahap terakhir, maka mempunyai lebih banyak kanak-kanak daripada b jika dan hanya jika terletak di sebelah b

Apakah perbezaan antara Binary Lengkap dan pokok perduaan penuh?

Pokok binari yang lengkap dan pokok binari yang penuh mempunyai perbezaan yang jelas. Walaupun pokok binari penuh ialah pokok binari di mana setiap nod mempunyai sifar atau dua anak, pokok binari yang lengkap adalah pokok binari di mana setiap peringkat pokok binari sepenuhnya diisi kecuali tahap terakhir. Sesetengah struktur data khas seperti timbunan perlu lengkap dengan pokok binari sementara mereka tidak perlu menjadi pokok binari penuh. Dalam pokok binari yang penuh, jika anda tahu bilangan nod jumlah atau bilangan gumpalan atau bilangan nod dalaman, anda boleh mencari dua yang lain dengan mudah.Tetapi pokok binari yang lengkap tidak mempunyai harta khas yang merangkumi tesis tiga sifat.