Το ύψος της Binary Tree σε Java

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

Ένα δυαδικό δένδρο αποτελείται από ένα σύνολο διασυνδεόμενων κόμβων . Κάθε κόμβος έχει μεταξύ μηδέν και δύο κόμβων του παιδιού . Κάθε κόμβος με την εξαίρεση του κόμβου ρίζας έχει ακριβώς ένα μητρικό κόμβο . Ο κόμβος δεν έχει γονέα κόμβους . Η Java δεν έχει ένα ενσωματωμένο στο δυαδικό κατηγορία δέντρο , αλλά μπορείτε να δημιουργήσετε το δικό σας από την αρχή ή να κατεβάσετε ένα από το Internet .
Εικόνων Δέντρο Ύψος
Η

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

Η Θεωρία
Η

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

Η ακόλουθη μέθοδος Java θα υπολογίσει το ύψος ενός δυαδικού δέντρου. Αποδέχεται την ριζικό κόμβο ενός δυαδικού δέντρου ως επιχείρημα . Εναλλακτικά , θα μπορούσε να περάσει ένα διαφορετικό κόμβο του δυαδικού δένδρου στη μέθοδο να βρει το ύψος του δέντρου κάτω από αυτόν τον κόμβο . Ο ακόλουθος κώδικας υποθέτει ότι κάθε κόμβος του δυαδικού δέντρου είναι του τύπου " BinaryTreeNode » και κάθε κόμβος περιέχει μεθόδους που επιστρέφουν την αριστερή και δεξιά παιδιά αυτού του κόμβου ονομάζεται " getLeftChild " και " getRightChild . "

ιδιωτικών int findHeight ( BinaryTreeNode currentNode ) {if ( currentNode.equals ( null ) ) {επιστροφή -1 ? } int leftHeight = findHeight ( currentNode.getLeftChild ( ) ) ? int rightHeight = findHeight ( currentNode.getRightChild ( ) ) ? int greatestHeight = Math.max ( leftHeight , rightHeight ) ? επιστρέψει greatestHeight ? }
Η
εικόνων