Ορισμοί

Δέντρο είναι ένα σύνολο κόμβων που συνδέονται με ακμές. Υπάρχει ένας μόνο κόμβος που ονομάζεται ρίζα και στον οποίο δεν καταλήγουν, αλλά μόνο ξεκινούν ακμές. Από κάθε κόμβο μπορούν να ξεκινήσουν καμία, μία ή περισσότερες ακμές. Σε κάθε κόμβο (εκτός της ρίζας) καταλήγει μία μόνο ακμή.

Πατέρας - Παιδί

Ένας κόμβος α είναι ο πατέρας των κόμβων β και γ, όταν από τον α αρχίζουν ακμές που καταλήγουν στους β και γ. Αντίστοιχα, οι β και γ είναι τα παιδιά του α. Η ορολογία αυτή επεκτείνεται προς τα πάνω ή κάτω με παππούδες και εγγονούς και γενικότερα προγόνους και απογόνους. Οι κόμβοι που έχουν παιδιά ονομάζονται και εσωτερικοί ή μη τερματικοί ή κλαδιά. Οι κόμβοι που δεν έχουν παιδιά ονομάζονται τερματικοί ή φύλλα.

Βαθμός Κόμβου - Δεντρου

Βαθμός ενός κόμβου είναι ο αριθμός των παιδιών του. Βαθμός ενός δέντρου είναι ο μέγιστος από τους βαθμούς των κόμβων του.

Επίπεδο

Επίπεδο ενός κόμβου είναι ο αριθμός των προγόνων του μέχρι τη ρίζα συν 1.

Βάθος

Το μέγιστο επίπεδο των κόμβων ενός δέντρου λέγεται βάθος ή ύψος του δέντρου.

Υποδέντρο

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

Ποσοτικά Στοιχεία

Ένα δέντρο βαθμού d και ύψους h μπορεί να έχει το πολύ

κόμβους.

Τύποι Δέντρων

• Δυαδικά Δέντρα?
• AVL
• B - Δέντρα