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

https://en.wikipedia.org/wiki/Binary_tree

Types of binary trees[edit]
Tree terminology is not well-standardized and so varies in the literature.

• A rooted binary tree has a root node and every node has at most two children.

• A full binary tree (sometimes referred to as a proper^[15] or plane binary tree)^[16][17] is a tree in which every node has either 0 or 2 children. Another way of defining a full binary tree is a recursive definition. A full binary tree is either:^[11]
  
  
  • A single vertex.
  • A tree whose root node has two subtrees, both of which are full binary trees.
• A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level.^[18] An example of a perfect binary tree is the (non-incestuous) ancestry chart of a person to a given depth, as each person has exactly two biological parents (one mother and one father). Provided the ancestry chart always displays the mother and the father on the same side for a given node, their sex can be seen as an analogy of left and right children, children being understood here as an algorithmic term.
• A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes at the last level h.^[19] A perfect tree is therefore always complete but a complete tree is not necessarily perfect. An alternative definition is a perfect tree whose rightmost leaves (perhaps all) have been removed. Some authors use the term complete to refer instead to a perfect binary tree as defined above, in which case they call this type of tree (with a possibly not filled last level) an almost complete binary tree or nearly complete binary tree.^[20][21] A complete binary tree can be efficiently represented using an array.^[19]

• In the infinite complete binary tree, every node has two children (and so the set of levels is countably infinite). The set of all nodes is countably infinite, but the set of all infinite paths from the root is uncountable, having the cardinality of the continuum. That's because these paths correspond by an order-preserving bijection to the points of the Cantor set, or (using the example of a Stern–Brocot tree) to the set of positive irrational numbers.
• A balanced binary tree is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1.^[22] One may also consider binary trees where no leaf is much farther away from the root than any other leaf. (Different balancing schemes allow different definitions of "much farther".^[23])
• A degenerate (or pathological) tree is where each parent node has only one associated child node.^[24] This means that the tree will behave like a linked list data structure.

Discrete Mathematics:Proofs, Structures and Applications, Third Edition, Third Edition. CRC Press. p. 620. ISBN 978-1-4398-1280-8.

Παράθεση από: evry στις 14 Απρ 2022, 05:50:41 ΜΜΟ ορισμός που ισχύει είναι ότι όταν λέμε δυαδικό δέντρο είναι default διατεταγμένο, δηλαδή υπάρχει διάκριση αριστερού/δεξιού παιδιού. Για αυτό υπάρχει στην βιβλιογραφία το unordered binary tree που είναι αυτό ακριβώς που λες.
Απλά κάποιοι όταν μιλάνε για ordered εννοούν ταξινομημένο και όχι διάκριση left/right και εκεί υπάρχει η σύγχυση

Ακριβώς αλλιώς πχ δεν θα υπήρχε preorder, inorder, postorder διάσχιση των δυαδικών δένδρων

Παράθεση από: KosTzag στις 13 Μαΐου 2022, 08:35:59 ΠΜΣυμφωνώ ότι σαν πρώτη σκέψη είναι λάθος.

Αλλά έχω την εξής δεύτερη σκέψη:
Το ότι δεν αναγράφονται οι ιδιότητες της κλάσης Α στην κλάση Β δεν σημαίνει ότι δεν είναι ιδιότητες της κλάσης Β (προφανώς δεν αναγράφονται στην κλάση Β γιατί κληρονομούνται).
Μήπως θα έπρεπε η πρόταση να είναι «Ένα αντικείμενο της κλάσης Β θα έχει μόνο τις ιδιότητες και τις μεθόδους που αναγράφονται στην κλάση Β»;

Εξάλλου αν δεχτούμε την 8η πρόταση ως σωστή, γιατί η 6η να είναι λάθος;

Πολύ σωστή παρατήρηση. Το συγκεκριμένο ΣΛ είναι απαράδεκτο, αφού η Β κληρονομεί από την Α και προφανώς θα έχει και όλα όσα έχει η Α. Αν μιλάγαμε για Private και Protected ίσως να είχε κάποιο νόημα αλλά και πάλι ελέγχεται.
Ήθελε άλλη διατύπωση.
Το έσωσαν με την λέξη μόνο, ώστε όλοι να καταλάβουν τι εννοούν αλλά και πάλι δεν είναι σωστό.

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

Καλησπέρα σε όλους

Ο τελευταίος κόμβος της λίστας θα είναι αυτός με τον πρώτο δείκτη null που θα συναντήσουμε,  τα υπόλοιπα περιεχόμενο της μνήμης σύμφωνα και με το  βιβλίο δε ""διαγράφονται ""αλλά σωστά αναφέρετε πως ""παραχωρούνται για άλλη  χρήση"".. εγώ θα τα έγραφα ξανά, αυτο θεωρώ πως είναι το πιο σωστό,  εφόσον γίνεται μια προσπάθεια αναπαράσταση της μορφής της μνήμης

Δεν υποστηρίζεται Multiple Inheritance από Java
https://courses.e-ce.uth.gr/ECE326/doku.php?id=java:multiple_inheritance

Γιώργο,

έχεις δίκιο ότι το παράδειγμα πολυμορφισμού με πρόσθεση είναι διαφορετικό είδος πολυμορφισμού (μεν), αλλά είναι πολυμορφισμός (δε).
Με την λογική σου λοιπόν ΔΕΝ απαιτείται η πρόσθεση αλφαριθμητικών να ονομάζεται προσθεση, αλλά θα μπορούσε να ονομάζεται συνένωση. Ναι αλλά τότε ο προγραμματιστής όμως δεν θα μπορούσε να εκμεταλλεύεται το χαρακτηριστικό του πολυμορφισμού με αποτέλεσμα ο κώδικας να είναι πιο σύνθετος καθώς θα έπρεπε να σκέφτεται κάθε φορά τι προσθέτει. Δηλαδή, πολυμορφικά θα μπορούσε να πει Πρόσθεση(χ1,χ2) χωρίς να τον νοιάζει τι είναι τα χ1, χ2. Μη πολυμορφικά θα έπρεπε να σκεφτεί τι τύπο έχουν τα χ1, χ2 ώστε να χρησιμοποιήσει την κατάλληλη μέθοδο.

Ο προγραμματιστής επιλέγει. Όμως οι επιλογές έχουν συνέπειες. Έτσι, αν κάποιος ονομάσει με το ίδιο όνομα πετάει() δύο άσχετες μεθόδους (ενώ για τη μία εννοεί ίπταται() ενώ για την άλλη ρίχνει()), θα μπορεί να τις καλέσει πολυμορφικά αλλά το πρόγραμμα πιθανώς να μη βγάζει νόημα και έτσι να δημιουργηθούν bugs.
Γι' αυτό σου έγγραψα (και επιμένω) ότι όταν επιλέγουμε κάποιο όνομα πρέπει να είμαστε συνειδητοποιημένοι γιατί αυτό έχει συνέπειες.


Στο παράδειγμα σου με τη λίστα η μία Εισαγωγή πολυμορφίζει την άλλη.
Δες στον παρακάτω κώδικα (μη υπαρκτής αλλά pythonοειδούς γλώσσας προγραμματισμού) τι πλεονέκτημα έχει αυτό:

Α=νέα ΜηΤαξινομένηΛιστα()
Β=νέα ΤαξινομημένηΛιστα()
Για χ σε [Α,Β]
   Για υ σε [9,8,7,6,5]
      χ.Εισαγωγη(υ)

Στη μία περίπτωση θα κληθεί η ταξινομημένη εισαγωγή στην άλλη η μη ταξινομημένη. Ο προγραμματιστής δεν χρειάζεται να βάλει if, δεν χρειάζεται να κάνει διπλή δουλειά. Η 'μαγεία' του πολυμορφισμού απλοποιεί έτσι κατά πολύ τον κώδικα.
Θα μπορούσες να το ονομάσεις παρεμβολή, αλλά τότε θα έχανες την ευκολία.

Κατά τη γνώμη μου το λάθος της διαίσθησής σου είναι ότι νομίζεις ότι υποχρεωτικά πρέπει να χρησιμοποιηθεί πολυμορφισμός μέσω κληρονομικότητας επειδή υπάρχει σχέση κλάσης-υποκλάσης. Όμως αυτό δεν ισχύει κατ' ανάγκη. Έτσι ενώ στην ερώτηση του akouts (συμφωνούμε ότι) δεν υπάρχει πολυμορφισμός μέσω κληρονομικότητας (αφού δεν ορίζουμε τη μέθοδο στην υπερκλάση), εσύ αποκλείεις να υπάρχει άλλου είδους πολυμορφισμός ενώ εγώ δέχομαι ότι μπορεί να υπάρχει. Θεωρώ ότι αυτό όχι μόνο δεν απαγορεύεται ούτε από την πραγματικότητα ούτε από τη θεωρία του βιβλίου αλλά υλοποιεί τόσο το πνεύμα όσο και το γράμμα του πολυμορφισμού.

Παράθεση από: George Eco στις 13 Μαΐου 2022, 12:16:28 ΠΜΕίναι ξεκάθαρα λάθος, επειδή έχει και της Α.

Συμφωνώ ότι σαν πρώτη σκέψη είναι λάθος.

Αλλά έχω την εξής δεύτερη σκέψη:
Το ότι δεν αναγράφονται οι ιδιότητες της κλάσης Α στην κλάση Β δεν σημαίνει ότι δεν είναι ιδιότητες της κλάσης Β (προφανώς δεν αναγράφονται στην κλάση Β γιατί κληρονομούνται).
Μήπως θα έπρεπε η πρόταση να είναι «Ένα αντικείμενο της κλάσης Β θα έχει μόνο τις ιδιότητες και τις μεθόδους που αναγράφονται στην κλάση Β»;

Εξάλλου αν δεχτούμε την 8η πρόταση ως σωστή, γιατί η 6η να είναι λάθος;

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

Ας αρχίσω με το παράδειγμα του πολυμορφισμού της πρόσθεσης. Αυτό το παράδειγμα δείχνει μια διαφορετική περίπτωση πολυμορφισμού, κατά την οποία μέσα στην ίδια κλάση (ή σε υποκλάσεις της) μπορώ να ορίσω πολλαπλές φορές την ίδια μέθοδο , με διαφορετικά ορίσματα σε κάθε ορισμό της (άρα και διαφορετική «υπογραφή»/signature), ώστε αυτή η μέθοδος να λειτουργεί διαφορετικά σε κάθε περίπτωση, ανάλογα με τα ορίσματά της. Έτσι κι αλλιώς δε συζητάμε για κάτι τέτοιο στο θέμα της ΟΕΦΕ.

Παράθεση από: pgrontas στις 12 Μαΐου 2022, 01:41:49 ΜΜΕπιπλέον στην άσκηση Ε.2 δέχεται ότι ο πολυμορφισμός είναι η δυνατότητα αντικειμένων να διαθέτουν μεθόδους με ίδιο όνομα αλλά διαφορετική υλοποίηση (δική μου σημείωση: οποιονδήποτε αντικειμένων).

Η σημείωση «οποιωνδήποτε αντικειμένων» που προσθέτεις, νομίζω δεν ευσταθεί και μάλλον ευθύνεται για τις παρανοήσεις.
Έστω η κλάση πουλί με μέθοδο πετάει() και η κλάση παίκτης (έστω του ράγκμπυ) με μεθόδους πιάνει(), κλοτσάει(), πετάει(), εννοείται τη μπάλα. Εδώ οι κλάσεις είναι ασυσχέτιστες, οι δύο λειτουργίες που υλοποιούνται με τις μεθόδους πετάει() είναι εντελώς διαφορετικές (δεν έχει νόημα καν η σύγκρισή τους), δεν συσχετίζονται με κανέναν τρόπο, καμία δεν κάνει override την άλλη, και το κοινό τους όνομα είναι όντως σύμπτωση (με την έννοια ότι δεν υπάρχει καμία σκοπιμότητα να έχουν το ίδιο όνομα, απλά τυχαίνει). Θα μπορούσα να μετονομάσω την πρώτη σε ίπταται() ή τη δεύτερη σε ρίχνει() χωρίς να αλλάξει τίποτα στη σχεδίασή μου (ενώ ταυτόχρονα τηρώ και την αρχή πως τα ονόματα παραπέμπουν στην σημασία των μεθόδων και δεν επιλέχτηκαν τυχαία). Ομοίως στην υποθετική ερώτηση του akouts θα μπορούσε η μέθοδος Γ πχ να ονομάζει τη μέθοδο ΛαμβάνειΠαραγγελία() χωρίς πρόβλημα (αν φαίνεται αδόκιμο το μεθ2() που πρότεινα πριν) , πράγμα που δεν θα μπορούσε όμως να γίνει στην περίπτωση που η υπερκλάση Α ορίζει την ΔέχεταιΠαραγγελία() .

Για να δούμε το ερώτημα του akouts σε ένα πιο ρεαλιστικό πλαίσιο, ας δούμε τις δύο υλοποιήσεις στην επισυναπτόμενη εικόνα (αν είναι καλές ή κακές δεν το συζητάμε). Στην 1^η υλοποίηση, η ΤαξινομημένηΛίστα επανακαθορίζει την εισαγωγή() προφανώς γιατί θέλει να εισαγάγει το στοιχείο με ταξινομημένο τρόπο. Εδώ είναι φανερό ότι η εισαγωγή() της Ταξινομημένης Λίστας κάνει override την εισαγωγή() της Λίστας (άρα αποτελεί πολυμορφισμό αυτής).
Στη δεύτερη υλοποίηση, η υπερκλάση δεν ορίζει την εισαγωγή(), την οποία ορίζει η κάθε υποκλάση για λογαριασμό της. Εδώ, η εισαγωγή() της Ταξινομημένης Λίστας ποια μέθοδο κάνει override; (οπότε ποιανής αποτελεί πολυμορφισμό; ) Και γιατί να μην την ονομάσει παρεμβολή(), εφόσον θα παρεμβάλλει το στοιχείο στη σωστή του θέση και επιπλέον τα αντικείμενα της κλάσης Λίστα (άρα και της ΤαξινομημένηΛίστα) σε αυτή την υλοποίηση δεν υποχρεούνται να έχουν μέθοδο εισαγωγή() ;

Παράθεση από: KosTzag στις 12 Μαΐου 2022, 07:04:11 ΜΜΚαλησπέρα σε όλους! Θα ήθελα να κάνω μια ερώτηση: στο Β2 πάντα, το 6 θα το δίνατε ως σωστό ή ως λάθος;

Είναι ξεκάθαρα λάθος, επειδή έχει και της Α.