Perbezaan antara pokok binari lengkap dan pokok binari penuh

Lengkapkan pokok binari lengkap vs pokok binari penuh

Pokok binari adalah pokok di mana setiap nod mempunyai satu atau dua anak. Di pokok binari, nod tidak boleh mempunyai lebih daripada dua anak. Di pokok binari, kanak -kanak dinamakan sebagai kanak -kanak "kiri" dan "kanan". Nod kanak -kanak mengandungi rujukan kepada ibu bapa mereka. Pokok binari lengkap adalah pokok binari di mana setiap tahap pokok binari sepenuhnya diisi kecuali tahap terakhir. Di peringkat yang tidak terisi, nod dilampirkan bermula dari kedudukan kiri-paling. Pokok binari penuh adalah pokok di mana setiap nod di dalam pokok mempunyai dua anak kecuali daun pokok.

Apa itu pokok binari penuh?

Pokok binari penuh adalah pokok binari di mana setiap nod di dalam pokok mempunyai sifar atau dua kanak -kanak. Dengan kata lain, setiap nod di 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) berkaitan dengan cara yang istimewa sehingga jika anda tahu salah satu daripada mereka, anda dapat menentukan dua yang lain nilai seperti berikut:

1. Sekiranya pokok binari penuh mempunyai nod dalaman:

- Bilangan daun l = i+1

- Jumlah nod n = 2*i+1

2. Sekiranya pokok binari penuh mempunyai nod n:

- Bilangan nod dalaman i = (n-1)/2

- Bilangan daun l = (n+1)/2

3. Sekiranya pokok binari penuh mempunyai daun:

- Jumlah nod n = 2*l-1

- Bilangan nod dalaman i = l-1

Apa itu pokok binari yang lengkap?

Seperti yang ditunjukkan dalam Rajah 2, pokok binari yang lengkap adalah pokok binari di mana setiap tahap pokok dipenuhi sepenuhnya kecuali tahap terakhir. Juga, pada tahap terakhir, nod harus dilampirkan bermula dari kedudukan paling kiri. Pohon binari yang lengkap H Ketinggian H memenuhi syarat -syarat berikut:

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

- Satu atau lebih nod di peringkat terakhir mungkin mempunyai 0 atau 1 anak

- Jika A, B adalah dua nod di peringkat di atas tahap terakhir, maka A mempunyai lebih banyak anak daripada B jika dan hanya jika A terletak kiri b

Apakah perbezaan antara pokok binari yang 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 nod mempunyai sifar atau dua kanak -kanak, pokok binari lengkap adalah pokok binari di mana setiap tahap pokok binari sepenuhnya diisi kecuali tahap terakhir. Beberapa struktur data khas seperti timbunan perlu lengkap pokok binari sementara mereka tidak perlu menjadi pokok binari penuh. Dalam pokok binari penuh, jika anda mengetahui jumlah nod atau jumlah laves atau bilangan nod dalaman, anda boleh mencari dua yang lain dengan mudah. Tetapi pokok binari yang lengkap tidak mempunyai harta khas yang berkaitan dengan tiga atribut.