Οδηγός Μελέτης - Εισαγωγή στον Προγραμματισμό

Α22.14 · Δυαδικά δένδρα

Εργαστήριο 9, Άσκηση 4 · Δυσκολία ★★☆ · programming · Κεφάλαια: 22, 21, 11

4.1 Δημιουργήστε το αρχείο tree.c και ορίστε μία αυτοαναφορική δομή δυαδικού δένδρου ακεραίων αριθμών.

typedef struct tnode *Treeptr;

struct tnode {
    int data;
    Treeptr left;
    Treeptr right;
};

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

Ορίστε την αναδρομική συνάρτηση:

Treeptr addtree(Treeptr p, int x);

Η συνάρτηση προσθέτει έναν αριθμό x στο ταξινομημένο δυαδικό δένδρο p, διατηρώντας το ταξινομημένο, και επιστρέφει το νέο δένδρο. Ο αλγόριθμος λειτουργεί ως εξής:

• Αν το δένδρο p είναι κενό (NULL), δημιουργείται ένας νέος κόμβος που περιέχει τον αριθμό x.
• Αν ο αριθμός που περιέχει ο τρέχων κόμβος είναι μεγαλύτερος από το x, η συνάρτηση καλείται για το αριστερό παιδί του κόμβου.
• Αν ο αριθμός είναι μικρότερος από το x, η συνάρτηση καλείται για το δεξί παιδί.
• Αν ο αριθμός είναι ίσος με το x, δεν γίνεται εισαγωγή.

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

4.3 Κατασκευάστε την αναδρομική συνάρτηση:

void treeprint(Treeptr p);

Η συνάρτηση δέχεται ως όρισμα το δένδρο και εκτυπώνει τα περιεχόμενά του με in-order διάσχιση. Ο αλγόριθμος λειτουργεί ως εξής:

1. Αν το δένδρο είναι κενό (NULL), η συνάρτηση επιστρέφει.
2. Διαφορετικά, εκτελούνται τα εξής βήματα:
   • Καλείται η treeprint για το αριστερό παιδί.
   • Εκτυπώνεται η τιμή του τρέχοντος κόμβου.
   • Καλείται η treeprint για το δεξί παιδί.

Καλέστε τη treeprint από τη συνάρτηση main για να εκτυπώσετε το δένδρο που κατασκευάσατε.

Υπόδειξη

Το κλειδί στην addtree είναι ότι επιστρέφει το (πιθανώς νέο) υποδένδρο: την τιμή της αναδρομικής κλήσης πρέπει να την αναθέσετε πίσω στο left ή στο right του κόμβου, αλλιώς ο νέος κόμβος χάνεται. Νέοι κόμβοι ξεκινούν με NULL παιδιά. Η in-order διάσχιση ταξινομημένου δένδρου τυπώνει τους αριθμούς σε αύξουσα σειρά, κάτι που σας δίνει έναν εύκολο έλεγχο ορθότητας.

Αριθμός στον οδηγό: Α22.14 (στο κεφάλαιο) · Μόνιμο αναγνωριστικό: lab-lab09-tree · Σύνδεσμος: https://progintro.github.io/study/questions/labs/lab-lab09-tree.html · Markdown (GitHub)