Δυαδικό δέντρο στο C
Στο Γ, α δυαδικό δέντρο είναι μια παρουσία μιας δομής δεδομένων δέντρου με έναν γονικό κόμβο που μπορεί να διαθέτει έναν μέγιστο αριθμό δύο θυγατρικών κόμβων. 0, 1 ή 2 κόμβοι απόγονοι. Κάθε μεμονωμένος κόμβος σε ένα δυαδικό δέντρο έχει τη δική του τιμή και δύο δείκτες στα παιδιά του, έναν δείκτη για το αριστερό παιδί και τον άλλο για το δεξί παιδί.
Δήλωση δυαδικού δέντρου
ΕΝΑ δυαδικό δέντρο μπορεί να δηλωθεί στο C χρησιμοποιώντας ένα αντικείμενο που ονομάζεται struct που απεικονίζει έναν από τους κόμβους στο δέντρο.
struct κόμβος {
τύπος δεδομένων var_name ;
struct κόμβος * αριστερά ;
struct κόμβος * σωστά ;
} ;
Παραπάνω είναι μια δήλωση του ενός δυαδικό δέντρο όνομα κόμβου ως κόμβος. Έχει τρεις τιμές. Η μία είναι η μεταβλητή αποθήκευσης δεδομένων και οι άλλες δύο είναι οι δείκτες προς το παιδί. (αριστερό και δεξί παιδί του γονικού κόμβου).
Facts of Binary Tree
Ακόμη και για μεγάλα σύνολα δεδομένων, χρησιμοποιώντας α δυαδικό δέντρο κάνει την αναζήτηση ευκολότερη και ταχύτερη. Ο αριθμός των κλαδιών δέντρων δεν είναι περιορισμένος. Σε αντίθεση με μια συστοιχία, δέντρα κάθε είδους μπορούν να κατασκευαστούν και να αυξηθούν με βάση το τι απαιτείται από ένα άτομο.
Εφαρμογή δυαδικού δέντρου στο C
Ακολουθεί ένας οδηγός βήμα προς βήμα για την εφαρμογή α Δυαδικό δέντρο στο Γ.
Βήμα 1: Δηλώστε μια Δυαδική Δενδρική Αναζήτηση
Δημιουργήστε έναν κόμβο δομής που έχει τρεις τύπους δεδομένων, όπως δεδομένα, *left_child και *right_child, όπου τα δεδομένα μπορούν να είναι ακέραιου τύπου και οι κόμβοι *left_child και *right_child μπορούν να δηλωθούν ως NULL ή όχι.
struct κόμβος{
ενθ δεδομένα ;
struct κόμβος * δεξιά_παιδί ;
struct κόμβος * αριστερά_παιδί ;
} ;
Βήμα 2: Δημιουργήστε νέους κόμβους σε δυαδικό δέντρο αναζήτησης
Δημιουργήστε έναν νέο κόμβο δημιουργώντας μια συνάρτηση που δέχεται έναν ακέραιο ως όρισμα και παρέχει τον δείκτη στον νέο κόμβο που δημιουργήθηκε με αυτήν την τιμή. Χρησιμοποιήστε τη συνάρτηση malloc() στο C για δυναμική εκχώρηση μνήμης για τον κόμβο που δημιουργήθηκε. Αρχικοποιήστε το αριστερό και το δεξί παιδί σε NULL και επιστρέψτε το nodeName.
struct κόμβος * δημιουργώ ( δεδομένα τύπου δεδομένων )
{
struct κόμβος * nodeName = malloc ( μέγεθος του ( struct κόμβος ) ) ;
nodeName -> δεδομένα = αξία ;
nodeName -> αριστερά_παιδί = nodeName -> δεξιά_παιδί = ΜΗΔΕΝΙΚΟ ;
ΕΠΙΣΤΡΟΦΗ nodeName ;
}
Βήμα 3: Εισαγάγετε δεξιό και αριστερό Child στο Binary Tree
Δημιουργήστε τις συναρτήσεις insert_left και insert_right που θα δέχονται δύο εισόδους, οι οποίες είναι η τιμή που θα εισαχθεί και ο δείκτης στον κόμβο στον οποίο θα συνδεθούν και τα δύο παιδιά. Καλέστε τη συνάρτηση δημιουργίας για να δημιουργήσετε έναν νέο κόμβο και αντιστοιχίστε τον επιστρεφόμενο δείκτη στον αριστερό δείκτη του αριστερού παιδιού ή στον δεξιό δείκτη του δεξιού παιδιού του γονέα ρίζας.
struct κόμβος * insert_left ( struct κόμβος * ρίζα , δεδομένα τύπου δεδομένων ) {ρίζα -> αριστερά = δημιουργώ ( δεδομένα ) ;
ΕΠΙΣΤΡΟΦΗ ρίζα -> αριστερά ;
}
struct κόμβος * insert_right ( struct κόμβος * ρίζα , δεδομένα τύπου δεδομένων ) {
ρίζα -> σωστά = δημιουργώ ( δεδομένα ) ;
ΕΠΙΣΤΡΟΦΗ ρίζα -> σωστά ;
}
Βήμα 4: Εμφάνιση κόμβων δυαδικού δέντρου με χρήση μεθόδων διέλευσης
Μπορούμε να εμφανίσουμε δέντρα χρησιμοποιώντας τρεις μεθόδους διέλευσης στο C. Αυτές οι μέθοδοι διέλευσης είναι:
1: Διέλευση προπαραγγελίας
Σε αυτή τη μέθοδο διέλευσης, θα περάσουμε μέσα από τους κόμβους προς μια κατεύθυνση από parent_node->left_child->right_child .
κενός προ_παραγγελία ( κόμβος * ρίζα ) {αν ( ρίζα ) {
printf ( '%ρε \n ' , ρίζα -> δεδομένα ) ;
εμφάνιση_προ_παραγγελίας ( ρίζα -> αριστερά ) ;
εμφάνιση_προ_παραγγελίας ( ρίζα -> σωστά ) ;
}
}
2: Διέλευση μετά την παραγγελία
Σε αυτή τη μέθοδο διέλευσης, θα περάσουμε μέσα από τους κόμβους σε μια κατεύθυνση από το left_child->right_child->parent_node-> .
κενός display_post_order ( κόμβος * ρίζα ) {αν ( binary_tree ) {
display_post_order ( ρίζα -> αριστερά ) ;
display_post_order ( ρίζα -> σωστά ) ;
printf ( '%ρε \n ' , ρίζα -> δεδομένα ) ;
}
}
3: Διέλευση κατά σειρά
Σε αυτή τη μέθοδο διέλευσης, θα περάσουμε μέσα από τους κόμβους προς μια κατεύθυνση από left_node->root_child->right_child .
κενός εμφάνιση_κατά σειρά ( κόμβος * ρίζα ) {αν ( binary_tree ) {
εμφάνιση_κατά σειρά ( ρίζα -> αριστερά ) ;
printf ( '%ρε \n ' , ρίζα -> δεδομένα ) ;
εμφάνιση_κατά σειρά ( ρίζα -> σωστά ) ;
}
}
Βήμα 5: Εκτελέστε διαγραφή σε δυαδικό δέντρο
Μπορούμε να διαγράψουμε το δημιουργημένο Δυαδικό δέντρο διαγράφοντας και τα δύο παιδιά με τη συνάρτηση γονικού κόμβου στο C ως εξής.
κενός delete_t ( κόμβος * ρίζα ) {αν ( ρίζα ) {
delete_t ( ρίζα -> αριστερά ) ;
delete_t ( ρίζα -> σωστά ) ;
Ελεύθερος ( ρίζα ) ;
}
}
C Πρόγραμμα Δυαδικής Δενδρικής Αναζήτησης
Ακολουθεί η πλήρης υλοποίηση του δέντρου δυαδικής αναζήτησης στον προγραμματισμό C:
#include#include
struct κόμβος {
ενθ αξία ;
struct κόμβος * αριστερά , * σωστά ;
} ;
struct κόμβος * κόμβος 1 ( ενθ δεδομένα ) {
struct κόμβος * tmp = ( struct κόμβος * ) malloc ( μέγεθος του ( struct κόμβος ) ) ;
tmp -> αξία = δεδομένα ;
tmp -> αριστερά = tmp -> σωστά = ΜΗΔΕΝΙΚΟ ;
ΕΠΙΣΤΡΟΦΗ tmp ;
}
κενός Τυπώνω ( struct κόμβος * root_node ) // εμφάνιση των κόμβων!
{
αν ( root_node != ΜΗΔΕΝΙΚΟ ) {
Τυπώνω ( root_node -> αριστερά ) ;
printf ( '%ρε \n ' , root_node -> αξία ) ;
Τυπώνω ( root_node -> σωστά ) ;
}
}
struct κόμβος * insert_node ( struct κόμβος * κόμβος , ενθ δεδομένα ) // εισαγωγή κόμβων!
{
αν ( κόμβος == ΜΗΔΕΝΙΚΟ ) ΕΠΙΣΤΡΟΦΗ κόμβος 1 ( δεδομένα ) ;
αν ( δεδομένα < κόμβος -> αξία ) {
κόμβος -> αριστερά = insert_node ( κόμβος -> αριστερά , δεδομένα ) ;
} αλλού αν ( δεδομένα > κόμβος -> αξία ) {
κόμβος -> σωστά = insert_node ( κόμβος -> σωστά , δεδομένα ) ;
}
ΕΠΙΣΤΡΟΦΗ κόμβος ;
}
ενθ κύριος ( ) {
printf ( 'Γ υλοποίηση του Δυαδικού Δέντρου Αναζήτησης! \n \n ' ) ;
struct κόμβος * μητρική εταιρεία = ΜΗΔΕΝΙΚΟ ;
μητρική εταιρεία = insert_node ( μητρική εταιρεία , 10 ) ;
insert_node ( μητρική εταιρεία , 4 ) ;
insert_node ( μητρική εταιρεία , 66 ) ;
insert_node ( μητρική εταιρεία , Τέσσερα πέντε ) ;
insert_node ( μητρική εταιρεία , 9 ) ;
insert_node ( μητρική εταιρεία , 7 ) ;
Τυπώνω ( μητρική εταιρεία ) ;
ΕΠΙΣΤΡΟΦΗ 0 ;
}
Στον παραπάνω κωδικό δηλώνουμε πρώτα α κόμβος χρησιμοποιώντας struct . Στη συνέχεια αρχικοποιούμε έναν νέο κόμβο ως ' κόμβος 1 ” και εκχωρήστε τη μνήμη δυναμικά χρησιμοποιώντας malloc() στο C με δεδομένα και δύο δείκτες πληκτρολογήστε παιδιά χρησιμοποιώντας τον δηλωμένο κόμβο. Μετά από αυτό, εμφανίζουμε τον κόμβο κατά printf() λειτουργία και καλέστε το στο κύριος() λειτουργία. Μετά το insertion_node() δημιουργείται συνάρτηση, όπου αν τα δεδομένα κόμβου είναι NULL τότε κόμβος 1 είναι συνταξιούχος, διαφορετικά στοιχεία τοποθετούνται στο κόμβος (γονέας) του αριστερού και του δεξιού παιδιού. Το πρόγραμμα ξεκινά την εκτέλεση από το κύριος() συνάρτηση, η οποία δημιουργεί έναν κόμβο χρησιμοποιώντας μερικούς κόμβους δείγματος ως παιδιά και στη συνέχεια χρησιμοποιεί μεθόδους διέλευσης κατά σειρά για να εκτυπώσει τα περιεχόμενα του κόμβου.
Παραγωγή
συμπέρασμα
Τα δέντρα χρησιμοποιούνται συχνά για τη διατήρηση των δεδομένων σε μη γραμμική μορφή. Δυαδικά δέντρα είναι είδη δέντρων όπου κάθε κόμβος (γονέας) έχει δύο απογόνους το αριστερό παιδί και το δεξί παιδί. ΕΝΑ δυαδικό δέντρο είναι μια ευέλικτη μέθοδος μεταφοράς και αποθήκευσης δεδομένων. Είναι πιο αποτελεσματικό σε σύγκριση με το Linked-List στο C. Στο παραπάνω άρθρο, είδαμε την έννοια του a Δυαδικό δέντρο με τη σταδιακή εφαρμογή του α Δυαδικό δέντρο αναζήτησης στο Γ.