Διαφορά μεταξύ πλήρους δυαδικού δέντρου και πλήρους δυαδικού δέντρου

Πλήρες Δυαδικό Δέντρο vs Πλήρες Δυαδικό Δέντρο

Δυαδικό δέντρο είναι ένα δέντρο όπου κάθε κόμβος έχει ένα ή δύο παιδιά. Σε ένα δυαδικό δέντρο, ένας κόμβος δεν μπορεί να έχει περισσότερα από δύο παιδιά. Σε ένα δυαδικό δέντρο, τα παιδιά ονομάζονται "αριστερά" και "σωστά" παιδιά. Οι παιδικοί κόμβοι περιέχουν αναφορά στον γονέα τους. Ένα πλήρες δυαδικό δέντρο είναι ένα δυαδικό δέντρο στο οποίο κάθε επίπεδο του δυαδικού δέντρου γεμίζεται εντελώς εκτός από το τελευταίο επίπεδο. Στο κενό επίπεδο, οι κόμβοι συνδέονται ξεκινώντας από την αριστερή θέση. Ένα πλήρες δυαδικό δέντρο είναι ένα δέντρο στο οποίο κάθε κόμβος στο δέντρο έχει δύο παιδιά εκτός από τα φύλλα του δέντρου.

Τι είναι το πλήρες δυαδικό δέντρο;

Το πλήρες δυαδικό δέντρο είναι ένα δυαδικό δέντρο στο οποίο κάθε κόμβος στο δέντρο έχει ακριβώς μηδέν ή δύο παιδιά. Με άλλα λόγια, κάθε κόμβος στο δέντρο εκτός από τα φύλλα έχει ακριβώς δύο παιδιά. Το σχήμα 1 παρακάτω απεικονίζει ένα πλήρες δυαδικό δέντρο. Σε ένα πλήρες δυαδικό δέντρο, ο αριθμός των κόμβων (n), ο αριθμός των laves (l) και ο αριθμός των εσωτερικών κόμβων (i) σχετίζεται με έναν ειδικό τρόπο έτσι ώστε αν γνωρίζετε κάποιο από αυτά μπορείτε να προσδιορίσετε τα άλλα δύο τιμές ως εξής:

1. Αν ένα πλήρες δυαδικό δέντρο έχει εσωτερικούς κόμβους:

- Αριθμός φύλλων l = i + 1

- Συνολικός αριθμός κόμβων n = 2 * i + 1

2. Εάν ένα πλήρες δυαδικό δένδρο έχει n κόμβους:

- Αριθμός εσωτερικών κόμβων i = (n-1) / 2

- Αριθμός φύλλων l = (n + 1) / 2

Αν ένα πλήρες δυαδικό δέντρο έχει φύλλα l:

- Σύνολο Αριθμός κόμβων n = 2 * l-1

- Αριθμός εσωτερικών κόμβων i = l-1

Τι είναι το πλήρες δυαδικό δέντρο;

Όπως φαίνεται στο σχήμα 2, ένα πλήρες δυαδικό δέντρο είναι ένα δυαδικό δέντρο στο οποίο κάθε επίπεδο του δέντρου γεμίζεται εντελώς εκτός του τελευταίου επιπέδου. Επίσης, στο τελευταίο επίπεδο, οι κόμβοι θα πρέπει να συνδέονται ξεκινώντας από την πιο αριστερή θέση. Ένα πλήρες δυαδικό δένδρο ύψους h ικανοποιεί τις ακόλουθες συνθήκες:

- Από τον ριζικό κόμβο, το επίπεδο πάνω από το τελευταίο επίπεδο αντιπροσωπεύει ένα πλήρες δυαδικό δέντρο ύψους h-1

- Ένας ή περισσότεροι κόμβοι στο τελευταίο επίπεδο μπορεί να έχουν 0 ή 1 παιδί

- Εάν a, b είναι δύο κόμβοι στο επίπεδο πάνω από το τελευταίο επίπεδο, τότε το a έχει περισσότερα παιδιά από το b αν και μόνο εάν το a βρίσκεται αριστερά από το b

Ποια είναι η διαφορά μεταξύ Complete Binary Tree και το πλήρες δυαδικό δέντρο;

Τα πλήρης δυαδικά δέντρα και τα δυαδικά δέντρα έχουν σαφή διαφορά. Ενώ ένα πλήρες δυαδικό δέντρο είναι ένα δυαδικό δέντρο στο οποίο κάθε κόμβος έχει μηδέν ή δύο παιδιά, ένα πλήρες δυαδικό δέντρο είναι ένα δυαδικό δέντρο στο οποίο κάθε επίπεδο του δυαδικού δένδρου είναι πλήρες πλην του τελευταίου επιπέδου. Ορισμένες ειδικές δομές δεδομένων, όπως οι σωροί, πρέπει να είναι πλήρεις δυαδικές δένδρων, ενώ δεν χρειάζεται να είναι πλήρες δυαδικό δένδρο. Σε ένα πλήρες δυαδικό δέντρο, αν γνωρίζετε τον αριθμό των συνολικών κόμβων ή τον αριθμό των λαβών ή τον αριθμό των εσωτερικών κόμβων, μπορείτε να βρείτε τα άλλα δύο πολύ εύκολα.Αλλά ένα πλήρες δυαδικό δέντρο δεν έχει ειδική ιδιότητα που σχετίζεται με αυτές τις τρεις ιδιότητες.