25
Κεφάλαιο 2
Θεωρητικό υπόβαθρο
Στο παρακάτω κεφάλαιο παρουσιάζονται όλα τα εργαλεία που χρησιμοποιήθηκαν στην
υλοποίηση της παρούσας πτυχιακής εργασίας. Αναφέρονται το λογισμικό και οι τεχνικές που
χρησιμοποιήθηκαν, και εξηγούνται οι λέξεις κλειδιά, ώστε να μπορεί ο αναγνώστης να
κατανοήσει καλύτερα τα κεφάλαια που θα ακολουθήσουν.
2.1 Δεντρική δομή
Στη θεωρία γραφημάτων, ως δεντρική δομή ή δέντρο ορίζεται ένα συνεκτικό και μη
κατευθυνόμενο γράφημα το οποίο δεν περιέχει κύκλους [29]. Η δεντρική δομή είναι ένας
τρόπος να αναπαρασταθεί γραφικά η ιεραρχία μιας δομής. Είναι η δομή δεδομένων που
αποτελείται από ένα σύνολο κόμβων που συνδέονται με ακμές. Σε κάθε μία πεπερασμένη
δενδρική δομή υπάρχει ο ανώτατος αρχικός κόμβος, από τον οποίο ξεκινάει η διακλάδωση, και
ονομάζεται ρίζα του δέντρου. Οι κόμβοι που δεν διακλαδώνονται περαιτέρω ονομάζονται
φύλλα του δέντρου. Οι κόμβοι μεταξύ τους έχουν σχέσεις γονιού - παιδιού. Κάθε παιδί έχει
μόνον ένα γονιό. Μια δομή δέντρου έχει την μορφή που παρουσιάζεται στο
Σχήμα 2 Παράδειγμα ισορροπημένου δυαδικού δέντρου
4
.
Μια υποκατηγορία δέντρων αποτελούν τα δυαδικά δέντρα, τα οποία έχουν μέχρι δυο παιδιά
ανά κόμβο, και τα ισορροπημένα δέντρα, που τα φύλλα τους έχουν μέγιστη διαφορά βάθους
έναν κόμβο.
4
Πηγή του σχήματος είναι η ιστοσελίδα
https://math.stackexchange.com/questions/2856956/binary-tree-
equation-describing-path. Η επίσκεψη έγινε στις 11/5/2020