απορια στα δεντρα

[ΜΑΚΡΙΔΑΚΗ ΣΤΕΛΛΑ]

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

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

Και ρωτώ εγώ: Η γραμμική σχέση μεταξύ των παιδιών του είαι τυχαία, την ορίζουμε εμείς και απλά πρέπει να ακολουθείτε η ίδια για όλο το δέντρο ή πρέπει υποχρετικά να είναι απο το μικρότερο στο μεγαλύτερο πηγαίνοντας από αριστερά προς τα δεξιά; γιατί δεν αναφέρει πουθενά το 2ο έτσι ακριβώς αλλά πολύ φοβάμαι ότι το εννοεί (κλασική περίπτωση :Ρ )

Ευχαριστώ!

[Foto]

Μόνο η γενήτρια τυχαίων αριθμών κάνει κάτι τυχαίο (αν και αυτό παίζεται). Τίποτα άλλο δεν έχει να κάνει με τύχη στο προγραμματισμό.

Η γραμμική σχέση είναι απλή: Για κάθε κόμβο συμβαίνουν ένα από τα δύο: Είτε έχει παιδιά, είτε είναι τερματικός (δεν έχει παιδιά). Για να βρεις ένα κόμβο ξεκινάς από τη ρίζα, και εδώ η σχέση μας λέει ποιον κόμβο πρέπει να διαλέξω. Πχ αν το δένδρο έχει λέξεις ενός λεξικού τα παιδιά του Α θα είναι όλες οι λέξεις που ξεκινούν από Α, και η γραμμική τους σχέση θα λέει ότι στον πλέον αριστερό κόμβο βάζουμε την μικρότερη λέξη. Εδώ έχουμε αμέσως μια σχέση που δηλώνει μια σειρά. Όμως δεν μπορώ από το πλέον αριστερό παιδι να πάω στο αμέσως πιο δεξιό, γιατί δεν έχω "δείκτη" από το ένα παιδί στο άλλο. Θα πρέπει να το κάνω από το γονέα, γιατί αυτός έχει τους δείκτες, αυτός δηλαδή "κατά τη διαμόρφωσή του" έγγραψε στο χώρο του τα παιδιά του.
Το πώς θα κάνω tree traversal έχει να κάνει πάλι με τη διαμόρφωση του δένδρου, με το πώς το έχω ορίσει. Οι κανόνες δηλαδή "αναδύονται" από τη κατασκευή, που αποδεδειγμένα λειτουργεί και όχι το αντίθετο, αν και σε μια άσκηση διαβάζουμε τους κανόνες και κάνουμε τη κατασκευή, ουσιαστικά οι κανόνες υπάρχουν εφόσον η υλοποίηση υπάρχει ή υπήρξε. Μιλάμε για Abstract δομές, όχι γιατί έχουν "ασάφεια" ως προς τη κατασκευή τους, αλλά επειδή έχουν κανόνες ανεξάρτητα από τους τύπους δεδομένων που υλοποιούνται. 
Για το ερώτημα και μετά από τη "θρασύτατη" εισαγωγή: Το τι πρέπει το δηλώνει ο κανόνας μιας "τυπικής" κατασκευής δένδρου. Στα παιδιά θα πρέπει να δηλώσεις ότι οι κόμβοι είναι πραγματικές "αποθήκες" δεδομένων, δηλαδή περιέχουν κάτι, και σε ένα δένδρο τα "αδέλφια", οι κόμβοι με κοινό γονέα έχουν μια σχέση μεταξύ τους, την οποία την κρατάει ο γονέας, και βάσει της σχέσης αυτής προγραμματιστικά αποφασίζουμε τα "δεδομένα" να τα εισάγουμε σε συγκεκριμένο γονέα, σε συγκεκριμένη θέση παιδιού. Υπάρχουν αλγόριθμοι που η εισαγωγή ενός κόμβου προκαλεί αναδιάταξη του δένδρου, επειδή στην τρέχουσα διαμόρφωση δεν μπορεί να καταχωρηθεί ο κόμβος (δεν έχει χώρο, ενώ αν είχε επειδή ισχύει η "γραμμική σχέση" θα μπορούσε να μπει).
Όταν λες για "μικρότερο" ήδη ορίζεις μια σχέση, ενώ μιλάμε γενικά για όποια σχέση έχουν τα "αδέλφια" μεταξύ τους. Οπότε αυτό θα μπερδέψει τα παιδιά.