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

Α22.19 · Reverse Inorder Traversal

Εξέταση Ιουλίου 2024, Θέμα 4 · Δυσκολία ★★☆ · programming · Κεφάλαια: 22, 11, 15

Γράψτε μια συνάρτηση reverse_inorder η οποία παίρνει ως όρισμα ένα δέντρο ακεραίων τύπου Tree και τυπώνει τους αριθμούς των κόμβων σε σειρά reverse inorder traversal, δηλαδή όπως βλέπουμε τους αριθμούς από δεξιά προς τα αριστερά (πρώτο το δεξί παιδί, μετά ο γονιός και στην συνέχεια το αριστερό). Για παράδειγμα, για το ακόλουθο δέντρο:

flowchart TD
  N1(("1")) --> N2(("2"))
  N1 --> N3(("3"))
  N2 --> N4(("4"))
  N2 --> N5(("5"))
  N3 --> N6(("6"))
  N3 --> N7(("7"))

Σχήμα: το δέντρο του παραδείγματος.

περιμένουμε να εκτυπωθεί η ακολουθία: 7 3 6 1 5 2 4. Ποια είναι η χρονική και η χωρική πολυπλοκότητα του αλγορίθμου σας (8/25 της βαθμολογίας); Ο τύπος Tree δίνεται παρακάτω:

typedef struct node {
  int value;
  struct node * left;
  struct node * right;
} * Tree;

Υπόδειξη

Ξεκινήστε από την αναδρομική inorder διάσχιση και αλλάξτε τη σειρά με την οποία επισκέπτεστε τα δύο υποδέντρα. Μην ξεχάσετε τη βασική περίπτωση του κενού δέντρου (NULL). Για τη χωρική πολυπλοκότητα, σκεφτείτε πόσο βαθιά μπορεί να φτάσει η στοίβα των αναδρομικών κλήσεων στη χειρότερη περίπτωση.

Αριθμός στον οδηγό: Α22.19 (στο κεφάλαιο) · Μόνιμο αναγνωριστικό: exam-2024-jul-q4 · Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2024-jul-q4.html · Markdown (GitHub)