Binary Trees in C: A Complete Beginner's Guide

Informatec Digital » Αλγόριθμοι » Δυαδικά Δέντρα σε C: Ένας Πλήρης Οδηγός για Αρχάριους

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

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

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

Ας ξεκινήσουμε λοιπόν!

Τι είναι τα δυαδικά δέντρα;

Τα δυαδικά δέντρα είναι ιεραρχικές δομές δεδομένων που αποτελούνται από διασυνδεδεμένους κόμβους. Κάθε κόμβος μπορεί να έχει έως και δύο θυγατρικούς κόμβους: έναν στα αριστερά και έναν στα δεξιά. Αυτή η δομή δύο κλάδων είναι αυτό που διακρίνει τα δυαδικά δέντρα από άλλες δομές δεδομένων.

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

Οφέλη από δυαδικά δέντρα

Τα δυαδικά δέντρα προσφέρουν πολλά πλεονεκτήματα όσον αφορά την αποτελεσματική αποθήκευση και αναζήτηση δεδομένων. Μερικά από τα βασικά οφέλη περιλαμβάνουν:

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

Δομή ενός δυαδικού δέντρου

Πριν βουτήξουμε στην υλοποίηση δυαδικών δέντρων στο C, είναι σημαντικό να κατανοήσουμε τη βασική δομή τους. Κάθε κόμβος σε ένα δυαδικό δέντρο περιέχει μια τιμή και αναφορές στους αριστερούς και δεξιούς θυγατρικούς κόμβους του, εάν έχει.

Ο παρακάτω πίνακας δείχνει τη δομή ενός κόμβου σε ένα δυαδικό δέντρο:

Δυαδικός κόμβος
αξία
Αριστερός κόμβος
Δεξιός κόμβος

Κάθε κόμβος μπορεί να αποθηκεύσει οποιοδήποτε τύπο δεδομένων, όπως ακέραιους αριθμούς, χαρακτήρες ή πιο σύνθετες δομές. Ο ριζικός κόμβος είναι το σημείο εκκίνησης του δέντρου και από αυτόν μπορούμε να έχουμε πρόσβαση σε όλους τους άλλους κόμβους.

Εφαρμογή δυαδικών δέντρων στο C

Τώρα που έχουμε μια βασική κατανόηση των δυαδικών δέντρων, ήρθε η ώρα να τα υλοποιήσουμε στη γλώσσα προγραμματισμού C. Στη συνέχεια, θα δούμε πώς να δηλώσουμε και να χρησιμοποιήσουμε μια δομή δυαδικού δέντρου σε C.

Δήλωση της δυαδικής δομής δέντρου

Στο C, μπορούμε να δηλώσουμε τη δομή ενός δυαδικού δέντρου χρησιμοποιώντας μια δομή και δείκτες. Ακολουθεί η βασική δήλωση της δομής:

struct NodoArbol {
    int valor;
    struct NodoArbol* izquierdo;
    struct NodoArbol* derecho;
};

Σε αυτή τη δομή, valor αντιπροσωπεύει την τιμή που είναι αποθηκευμένη στον κόμβο και izquierdo y derecho είναι δείκτες στους αριστερούς και δεξιούς θυγατρικούς κόμβους, αντίστοιχα.

Δημιουργία νέου κόμβου

Για να δημιουργήσουμε έναν νέο κόμβο στο δυαδικό δέντρο, πρέπει να εκχωρήσουμε μνήμη για τον κόμβο και να ορίσουμε τις τιμές του. Εδώ είναι μια συνάρτηση C που δημιουργεί έναν νέο κόμβο:

struct NodoArbol* crearNodo(int valor) {
    struct NodoArbol* nodo = (struct NodoArbol*)malloc(sizeof(struct NodoArbol));
    nodo->valor = valor;
    nodo->izquierdo = NULL;
    nodo->derecho = NULL;
    return nodo;
}

Η λειτουργία malloc Χρησιμοποιείται για την εκχώρηση δυναμικής μνήμης στον κόμβο. Στη συνέχεια ορίζουμε τις τιμές του κόμβου και επιστρέφουμε τον κόμβο που δημιουργήθηκε.

Εισαγωγή κόμβων

Η εισαγωγή κόμβου είναι μια θεμελιώδης διαδικασία σε δυαδικά δέντρα. Σας επιτρέπει να προσθέσετε νέα στοιχεία στο δέντρο στη σωστή θέση με βάση την τιμή του κόμβου. Παρακάτω είναι μια συνάρτηση C για την εισαγωγή ενός κόμβου σε ένα δυαδικό δέντρο:

struct NodoArbol* insertarNodo(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL) {
        return crearNodo(valor);
    }

    if (valor < raiz->valor) {
        raiz->izquierdo = insertarNodo(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = insertarNodo(raiz->derecho, valor);
    }

    return raiz;
}

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

Διαγραφή κόμβων

Η διαγραφή κόμβων σε ένα δυαδικό δέντρο μπορεί να είναι λίγο πιο περίπλοκη. Εξαρτάται από πολλές περιπτώσεις, όπως αν ο κόμβος που θα διαγραφεί έχει παιδιά ή όχι. Παρακάτω είναι μια συνάρτηση C για τη διαγραφή ενός κόμβου σε ένα δυαδικό δέντρο:

struct NodoArbol* eliminarNodo(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL) {
        return raiz;
    }

    if (valor < raiz->valor) {
        raiz->izquierdo = eliminarNodo(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = eliminarNodo(raiz->derecho, valor);
    } else {
        if (raiz->izquierdo == NULL) {
            struct NodoArbol* temp = raiz->derecho;
            free(raiz);
            return temp;
        } else if (raiz->derecho == NULL) {
            struct NodoArbol* temp = raiz->izquierdo;
            free(raiz);
            return temp;
        }

        struct NodoArbol* sucesor = encontrarSucesor(raiz->derecho);
        raiz->valor = sucesor->valor;
        raiz->derecho = eliminarNodo(raiz->derecho, sucesor->valor);
    }

    return raiz;
}

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

• Εάν η τιμή είναι μικρότερη, πηγαίνουμε στα αριστερά του δέντρου.
• Εάν η τιμή είναι μεγαλύτερη, πηγαίνουμε στα δεξιά του δέντρου.
• Εάν η τιμή είναι ίση, βρίσκουμε τον πλησιέστερο διάδοχο του κόμβου (τον μικρότερο κόμβο στο δεξί υποδέντρο) και τον αντικαθιστούμε με τον τρέχοντα κόμβο. Στη συνέχεια αφαιρούμε τον διάδοχο από το δεξί υποδέντρο.

Διαβάσεις σε δυαδικά δέντρα

Οι διελεύσεις είναι λειτουργίες που μας επιτρέπουν να επισκεφτούμε όλους τους κόμβους ενός δυαδικού δέντρου με μια συγκεκριμένη σειρά. Υπάρχουν τρεις συνήθεις τύποι περιηγήσεων:

Διάσχιση κατά σειρά : Επισκέπτεται πρώτα το αριστερό υποδέντρο, έπειτα τον τρέχοντα κόμβο και τέλος το δεξί υποδέντρο. Ακολουθεί μια συνάρτηση C που εκτελεί μια διάσχιση κατά σειρά ενός δυαδικού δέντρου:

void inOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        inOrden(raiz->izquierdo);
        printf("%d ", raiz->valor);
        inOrden(raiz->derecho);
    }
}

Προ-ταξινόμηση : Επισκέπτεται πρώτα τον τρέχοντα κόμβο, έπειτα το αριστερό υποδέντρο και τέλος το δεξί υποδέντρο. Ακολουθεί μια συνάρτηση C που εκτελεί μια προ-ταξινόμηση ενός δυαδικού δέντρου:

void preOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        printf("%d ", raiz->valor);
        preOrden(raiz->izquierdo);
        preOrden(raiz->derecho);
    }
}

Μεταγενέστερη διέλευση : Επισκέπτεται πρώτα το αριστερό υποδέντρο, μετά το δεξί υποδέντρο και τέλος τον τρέχοντα κόμβο. Ακολουθεί μια συνάρτηση C που εκτελεί μια μεταγενέστερη διέλευση ενός δυαδικού δέντρου:

void postOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        postOrden(raiz->izquierdo);
        postOrden(raiz->derecho);
        printf("%d ", raiz->valor);
    }
}

Αναζήτηση στοιχείων

Η αναζήτηση στοιχείων σε ένα δυαδικό δέντρο μας επιτρέπει να βρούμε γρήγορα μια συγκεκριμένη τιμή μέσα στη δομή δεδομένων. Εδώ είναι μια συνάρτηση C για την αναζήτηση ενός στοιχείου σε ένα δυαδικό δέντρο:

struct NodoArbol* buscarElemento(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL || raiz->valor == valor) {
        return raiz;
    }

    if (valor < raiz->valor) {
        return buscarElemento(raiz->izquierdo, valor);
    } else {
        return buscarElemento(raiz->derecho, valor);
    }
}

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

Παραδείγματα υλοποίησης δυαδικών δέντρων στο C

Τώρα που καλύψαμε τα βασικά των δυαδικών δέντρων και πώς να τα εφαρμόσουμε στο C, ας δούμε μερικά πρακτικά παραδείγματα.

Παράδειγμα 1: Δημιουργία δυαδικού δέντρου

Ας υποθέσουμε ότι θέλουμε να δημιουργήσουμε ένα δυαδικό δέντρο με τις ακόλουθες τιμές: 10, 5, 15, 3, 7, 13, 18. Δείτε πώς μπορούμε να το κάνουμε στο C:

int main() {
    struct NodoArbol* raiz = NULL;

    raiz = insertarNodo(raiz, 10);
    raiz = insertarNodo(raiz, 5);
    raiz = insertarNodo(raiz, 15);
    raiz = insertarNodo(raiz, 3);
    raiz = insertarNodo(raiz, 7);
    raiz = insertarNodo(raiz, 13);
    raiz = insertarNodo(raiz, 18);

    return 0;
}

Σε αυτό το παράδειγμα, δημιουργούμε έναν δείκτη στη ρίζα του δέντρου και στη συνέχεια χρησιμοποιούμε τη συνάρτηση insertarNodo για να προσθέσετε τις τιμές στο δέντρο.

Παράδειγμα 2: Διέλευση κατά σειρά του δυαδικού δέντρου

Για να εκτυπώσουμε τις τιμές του δυαδικού δέντρου με τη σειρά, μπορούμε να καλέσουμε τη συνάρτηση inOrden ως εξής:

int main() {
    // Crear el árbol binario

    printf("Recorrido en orden: ");
    inOrden(raiz);
    printf("\n");

    return 0;
}

Αυτό το παράδειγμα θα εκτυπώσει τις τιμές στο δέντρο με αύξουσα σειρά.

Συχνές ερωτήσεις

1. Ποια είναι η διαφορά μεταξύ ενός δυαδικού δέντρου και ενός δυαδικού δέντρου αναζήτησης;

Ένα δυαδικό δέντρο αναζήτησης (BST) είναι ένας ειδικός τύπος δυαδικού δέντρου στο οποίο τα στοιχεία είναι διατεταγμένα έτσι ώστε οι μικρότερες τιμές να βρίσκονται στα αριστερά και οι μεγαλύτερες τιμές στα δεξιά. Αυτό επιτρέπει την πιο αποτελεσματική αναζήτηση στοιχείων σε σύγκριση με ένα κανονικό δυαδικό δέντρο.

2. Μπορώ να έχω κόμβους με διπλότυπες τιμές σε ένα δυαδικό δέντρο;

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

3. Πώς μπορώ να αφαιρέσω έναν συγκεκριμένο κόμβο από ένα δυαδικό δέντρο;

Για να αφαιρέσετε έναν συγκεκριμένο κόμβο από ένα δυαδικό δέντρο, πρέπει να ακολουθήσετε τα εξής βήματα:

1. Βρείτε τον κόμβο που θέλετε να διαγράψετε χρησιμοποιώντας μια αναζήτηση δέντρου.
2. Εξετάστε τις διάφορες περιπτώσεις εξάλειψης:
   • Εάν ο κόμβος δεν έχει παιδιά, μπορείτε απλά να τον διαγράψετε και να ελευθερώσετε τη μνήμη του.
   • Εάν ο κόμβος έχει μόνο ένα παιδί, μπορείτε να αντικαταστήσετε τον κόμβο με το παιδί του.
   • Εάν ο κόμβος έχει δύο παιδιά, πρέπει να βρείτε τον πλησιέστερο διάδοχο (τον μικρότερο κόμβο στο δεξί υποδέντρο) και να αντικαταστήσετε την τιμή του κόμβου που πρόκειται να διαγραφεί με την τιμή του διαδόχου. Στη συνέχεια, αφαιρέστε τον διάδοχο από το δέντρο.
3. Προσαρμόζει συνδέσμους και δείκτες όπως απαιτείται για να διατηρήσει τη σωστή δομή δέντρου.

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

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

5. Ποιο είναι το ύψος ενός δυαδικού δέντρου;

Το ύψος ενός δυαδικού δέντρου είναι το μήκος της μεγαλύτερης διαδρομής από τη ρίζα μέχρι το φύλλο. Με άλλα λόγια, είναι ο μέγιστος αριθμός άκρων μεταξύ της ρίζας και οποιουδήποτε φύλλου του δέντρου. Το ύψος μετριέται ως προς τον αριθμό των επιπέδων, επομένως ένα δέντρο με μόνο έναν κόμβο έχει ύψος 0 και ένα κενό δέντρο δεν έχει ύψος.

6. Πότε πρέπει να χρησιμοποιήσω ένα δυαδικό δέντρο στα προγράμματά μου;

Τα δυαδικά δέντρα είναι χρήσιμα σε διάφορες καταστάσεις. Μερικές συνηθισμένες περιπτώσεις όπου μπορείτε να χρησιμοποιήσετε δυαδικά δέντρα περιλαμβάνουν:

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

Θυμηθείτε να αξιολογήσετε τις απαιτήσεις σας και να εξετάσετε την πολυπλοκότητα των λειτουργιών σε δυαδικά δέντρα πριν αποφασίσετε να τις χρησιμοποιήσετε στα προγράμματά σας.

Συμπέρασμα

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

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

Θυμηθείτε να εξασκηθείτε και να πειραματιστείτε με τα παρεχόμενα παραδείγματα για να ενισχύσετε την κατανόησή σας για τα δυαδικά δέντρα στο C. Καλή τύχη στο ταξίδι εκμάθησης και ανάπτυξης λογισμικού!