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

Α22.18 · Αθροιστής Δέντρων - sumtree

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

Αθροιστής Δέντρων - sumtree [20 Μονάδες]

Γράψτε μια συνάρτηση sumtree η οποία παίρνει ως όρισμα ένα δέντρο ακεραίων τύπου Tree και επιστρέφει το άθροισμα όλων των κόμβων του δέντρου. Για παράδειγμα, για το ακόλουθο δέντρο:

flowchart TD
  N3(("3")) --> N4(("4"))
  N3 --> N5(("5"))
  N4 --> N6(("6"))
  N4 --> N7(("7"))
  N5 --> N8(("8"))
  N5 --> N9(("9"))

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

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

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

Υπόδειξη

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

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