Αποστολέας Θέμα: Απλό δένδρο ερώτηση  (Αναγνώστηκε 570 φορές)

sensible

  • Θαμώνας
  • ***
  • Μηνύματα: 37
Απλό δένδρο ερώτηση
« στις: 27 Μαρ 2020, 07:23:11 μμ »
Γεια σας συνάδελφοι.

Μία ερώτηση:
Ένα απλό δένδρο αποτελείται από ένα κόμβο και με περιεχόμενο έναν αριθμό, ας πούμε το 5. Μπορεί να χαρακτηριστεί το συγκεκριμένο απλό δένδρο και ως δυαδικό δένδρο ή ακόμα και δυαδικό δένδρο αναζήτησης;
Βάση ορισμών νομίζω πως ναι.
Ευχαριστώ

bagelis

  • Ομάδα διαγωνισμάτων 2009
  • *
  • Μηνύματα: 568
Απ: Απλό δένδρο ερώτηση
« Απάντηση #1 στις: 27 Μαρ 2020, 08:35:12 μμ »
Και εγώ ναι πιστεύω...

Το να έχω το πολύ δύο παιδιά, σημαίνει, κανένα, ένα ή δύο, άρα και κανένα.

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 6014
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Απλό δένδρο ερώτηση
« Απάντηση #2 στις: 27 Μαρ 2020, 09:22:21 μμ »
Δέντρο είναι η δομή, ο κώδικας, όχι τα δεδομένα.
Αν έχεις γράψει κώδικα για δυαδικό δέντρο τότε είναι δυαδικό ακόμα και με μηδέν δεδομένα μέσα.

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

gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 203
Απ: Απλό δένδρο ερώτηση
« Απάντηση #3 στις: 28 Μαρ 2020, 01:36:02 πμ »
Η λεγόμενη "κενή αλήθεια" (vacuous truth) είναι θεμελιώδης για την πληροφορική. Η πρόταση "κάθε στοιχείο μιας κενής συλλογής έχει την ιδιότητα Ι" είναι αληθής ανεξάρτητα από το ποια είναι η ιδιότητα Ι (αν δεν ήταν αληθής θα έπρεπε να υπάρχει στοιχείο της συλλογής που δεν έχει την ιδιότητα - και αυτό βέβαια σε μια κενή συλλογή είναι απίθανο).

Δυστυχώς, η Γλώσσα δεν περιλαμβάνει τον κενό πίνακα. Αυτό όμως δεν ισχύει στις περισσότερες μοντέρνες γλώσσες προγραμματισμού, οι οποίες όχι απλά περιλαμβάνουν κενές συλλογές, αλλά o προγραμματισμός σ' αυτές τις γλώσσες θεμελιώνεται στις κενές συλλογές (όπως τα μοντέρνα μαθηματικά θεμελιώνονται πάνω στο κενό σύνολο)! Στην Python αν θέλουμε να δούμε αν κάθε στοιχείο της λίστας L έχει την ιδιότητα predicate, όπου predicate κάποια συνάρτηση μιας παραμέτρου που επιστρέφει ένα αντικείμενο κλάσης bool, θα κάναμε κάτι τέτοιο:

Κώδικας: [Επιλογή]
true_for_all = True
for item in L:
    if not predicate(item):
        true_for_all = False
        break
print(true_for_all)

Φυσικά, το παραπάνω θα εμφανίσει True στην περίπτωση που η L είναι η κενή λίστα, ανεξάρτητα από το πως ορίζεται η συνάρτηση predicate. Για τον ίδιο λόγο το εν λόγω δέντρο είναι και δυαδικό δέντρο αναζήτησης: για το δεξιό υποδέντρο του μοναδικού κόμβου (και ρίζας) το οποίο είναι κενό, ισχύει η ιδιότητα ότι "κάθε κόμβος του έχει τιμή μεγαλύτερη ή ίση από την τιμή της ρίζας". Παρόμοια για το αριστερό το οποίο είναι και αυτό κενό ισχύει ότι  "κάθε κόμβος του έχει τιμή μικρότερη από την τιμή της ρίζας".