Perbedaan antara pohon biner lengkap dan pohon biner penuh

Pohon biner lengkap vs pohon biner penuh

Pohon biner adalah pohon di mana setiap node memiliki satu atau dua anak. Di pohon biner, sebuah simpul tidak dapat memiliki lebih dari dua anak. Di pohon biner, anak -anak disebut sebagai "kiri" dan "kanan" anak -anak. Node anak berisi referensi ke orang tua mereka. Pohon biner lengkap adalah pohon biner di mana setiap level pohon biner sepenuhnya terisi kecuali level terakhir. Di level yang tidak terisi, node terpasang 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 biner penuh?

Pohon biner penuh adalah pohon biner di mana setiap simpul di pohon memiliki nol atau dua anak persis. Dengan kata lain, setiap simpul di pohon kecuali daun memiliki tepat dua anak. Gambar 1 di bawah ini menggambarkan pohon biner lengkap. Dalam pohon biner penuh, jumlah node (n), jumlah lave (l) dan jumlah node internal (i) terkait dengan cara khusus sehingga jika Anda tahu salah satu dari mereka, Anda dapat menentukan dua lainnya Nilai sebagai berikut:

1. Jika pohon biner penuh memiliki node internal:

- Jumlah daun l = i+1

- Jumlah total node n = 2*i+1

2. Jika pohon biner penuh memiliki n node:

- Jumlah node internal i = (n-1)/2

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

3. Jika pohon biner penuh memiliki daun L:

- Jumlah total node n = 2*L-1

- Jumlah node internal i = l-1

Apa itu pohon biner lengkap?

Seperti yang ditunjukkan pada Gambar 2, pohon biner lengkap adalah pohon biner di mana setiap level pohon sepenuhnya terisi kecuali level terakhir. Juga, di level terakhir, node harus dipasang mulai dari posisi paling kiri. Pohon biner lengkap dengan tinggi h memenuhi syarat berikut:

- Dari simpul akar, level di atas level terakhir mewakili pohon biner penuh dengan tinggi H-1

- Satu atau lebih node di level terakhir mungkin memiliki 0 atau 1 anak

- Jika A, B adalah dua node di level di atas level terakhir, maka A memiliki lebih banyak anak daripada B jika dan hanya jika A terletak di kiri B dari B

Apa perbedaan antara pohon biner lengkap dan pohon biner penuh?

Pohon biner lengkap dan pohon biner penuh memiliki perbedaan yang jelas. Sementara pohon biner penuh adalah pohon biner di mana setiap simpul memiliki nol atau dua anak, pohon biner lengkap adalah pohon biner di mana setiap level pohon biner sepenuhnya terisi kecuali level terakhir. Beberapa struktur data khusus seperti tumpukan harus menjadi pohon biner lengkap sementara mereka tidak perlu menjadi pohon biner penuh. Dalam pohon biner lengkap, jika Anda tahu jumlah total node atau jumlah lave atau jumlah node internal, Anda dapat menemukan dua lainnya dengan sangat mudah. Tapi pohon biner lengkap tidak memiliki properti khusus yang berhubungan dengan tesis tiga atribut.