Perbedaan antara pohon biner lengkap dan pohon biner penuh
Pohon Binari Penuh vs Pohon Binari Penuh
Pohon biner adalah pohon tempat setiap simpul memiliki satu atau dua anak. Dalam sebuah pohon biner, sebuah simpul tidak bisa memiliki lebih dari dua anak. Di pohon biner, anak-anak diberi nama sebagai anak "kiri" dan "benar". Simpul anak berisi referensi ke orang tua mereka. Pohon biner lengkap adalah pohon biner dimana setiap tingkat pohon biner terisi penuh kecuali tingkat terakhir. Pada level yang tidak terisi, node dilekatkan mulai dari posisi paling kiri. Pohon biner penuh adalah pohon di mana setiap simpul di pohon memiliki dua anak kecuali daun pohon.
Apa itu Pohon Binari Penuh?
Pohon biner penuh adalah pohon biner di mana setiap simpul di pohon memiliki tepat nol atau dua anak. Dengan kata lain, setiap simpul di pohon kecuali dedaunan memiliki dua anak. Gambar 1 di bawah menggambarkan sebuah pohon biner penuh. Dalam sebuah pohon biner penuh, jumlah node (n), jumlah lave (l) dan jumlah node internal (i) berhubungan dengan cara khusus sehingga jika Anda mengetahui salah satu dari keduanya, Anda dapat menentukan dua lainnya. nilai sebagai berikut:
1. Jika pohon biner penuh memiliki simpul internal saya:
- Jumlah daun l = i + 1
- Jumlah total nodes n = 2 * i + 1
2. Jika sebuah pohon biner penuh memiliki n node:
- Jumlah simpul internal i = (n-1) / 2
- Jumlah daun l = (n + 1) / 2
3. Jika pohon biner penuh telah saya tinggalkan:
- Jumlah Jumlah node n = 2 * l-1
- Jumlah simpul internal i = l-1
Apa itu Pohon Binari Lengkap?
Seperti yang ditunjukkan pada gambar 2, sebuah pohon biner yang lengkap adalah pohon biner di mana setiap tingkat pohon benar-benar terisi kecuali tingkat terakhir. Juga, pada tingkat terakhir, simpul harus dilekatkan mulai dari posisi paling kiri. Sebuah pohon biner lengkap dengan tinggi h memenuhi kondisi berikut:
- Dari simpul akar, tingkat di atas tingkat terakhir mewakili pohon biner penuh dengan tinggi h-1
- Satu atau lebih simpul pada tingkat terakhir mungkin memiliki 0 atau 1 anak
- Jika a, b adalah dua titik pada tingkat di atas tingkat terakhir, maka a memiliki lebih banyak anak daripada b jika dan hanya jika terletak di kiri b
Apa perbedaan antara Pohon Binari Lengkap dan Full Binary Tree?
Pohon biner lengkap dan pohon biner lengkap memiliki perbedaan yang jelas. Sementara pohon biner penuh adalah pohon biner di mana setiap node memiliki nol atau dua anak, pohon biner yang lengkap adalah pohon biner di mana setiap tingkat pohon biner benar-benar terisi kecuali tingkat terakhir. Beberapa struktur data khusus seperti tumpukan harus berupa pohon biner lengkap sedangkan pohon induk tidak perlu penuh. Dalam pohon biner penuh, jika Anda mengetahui jumlah total simpul atau jumlah lave atau jumlah simpul internal, Anda bisa menemukan dua lainnya dengan sangat mudah.Tapi pohon biner yang lengkap tidak memiliki properti khusus yang berhubungan dengan tesis tiga atribut.
