Το Στέκι των Πληροφορικών

Γενικό Λύκειο => Γ΄ Λυκείου => Δομές δεδομένων => Μήνυμα ξεκίνησε από: sensible στις 27 Μαρ 2020, 07:23:11 μμ

Τίτλος: Απλό δένδρο ερώτηση
Αποστολή από: sensible στις 27 Μαρ 2020, 07:23:11 μμ
Γεια σας συνάδελφοι.

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

Το να έχω το πολύ δύο παιδιά, σημαίνει, κανένα, ένα ή δύο, άρα και κανένα.
Τίτλος: Απ: Απλό δένδρο ερώτηση
Αποστολή από: alkisg στις 27 Μαρ 2020, 09:22:21 μμ
Δέντρο είναι η δομή, ο κώδικας, όχι τα δεδομένα.
Αν έχεις γράψει κώδικα για δυαδικό δέντρο τότε είναι δυαδικό ακόμα και με μηδέν δεδομένα μέσα.

Αντίστοιχα και η ουρά και η στοίβα, ακόμα και άδειες να είναι, ακόμα και με πίνακες να υλοποιούνται και οι δύο, χαρακτηρίζονται ως ουρά ή στοίβα λόγω του κώδικα, των λειτουργιών εισαγωγή  / εξαγωγή / ώθηση / απώθηση κλπ.
Τίτλος: Απ: Απλό δένδρο ερώτηση
Αποστολή από: gbougioukas στις 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. Για τον ίδιο λόγο το εν λόγω δέντρο είναι και δυαδικό δέντρο αναζήτησης: για το δεξιό υποδέντρο του μοναδικού κόμβου (και ρίζας) το οποίο είναι κενό, ισχύει η ιδιότητα ότι "κάθε κόμβος του έχει τιμή μεγαλύτερη ή ίση από την τιμή της ρίζας". Παρόμοια για το αριστερό το οποίο είναι και αυτό κενό ισχύει ότι  "κάθε κόμβος του έχει τιμή μικρότερη από την τιμή της ρίζας".