Ορισμοί

Ένα δένδρο (tree) είναι ένα σύνολο από κόμβους (nodes) που ενώνονται με ακμές (edges) και εκπληρεί την παρακάτω ιδιότητα:
- Αν ορίσουμε ως μονοπάτι (path) ένα σύνολο κόμβων ενωμένων με ακμές και ένα συγκεκριμένο κόμβο ως ρίζα (root) του δέδρου τότε κάθε άλλος κόμβος ενώνεται με τη ρίζα με ένα και μόνο ένα μονοπάτι.
Αν παραστήσουμε το δένδρο με τη ρίζα προς τα πάνω τότε κάθε κόμβος - εκτός από τη ρίζα - θα έχει ακριβώς ένα κόμβο από πάνω του ο οποίος και ονομάζεται πατέρας (father) του.
Αντίστοιχα οι κόμβοι που βρίσκονται κάτω από τον πατέρα ονομάζονται παιδιά (children) του.
Βαθμός (Degree) ενός κόμβου ορίζεται ως ο αριθμός των παιδιών του.
Βαθμός ενός δένδρου είναι ο μεγιστός βαθμός όλων των κόμβων του.
Κόμβοι χωρίς παιδιά ονομάζονται τερματικοί κόμβοι (terminal nodes) ή εξωτερικοί κόμβοι (external nodes) ή φύλλα (leaves).
Κόμβοι με παιδιά ονομάζονται μη τερματικοί κόμβοι (non-terminal nodes) ή εσωτερικοί κόμβοι (internal nodes) ή κλαδιά (branches).
Επίπεδο (Level) ενός κόμβου ορίζεται ως ο αριθμός των κόμβων στο μονοπάτι από τον κόμβο μέχρι τη ρίζα.
Το μέγιστο επίπεδο των κόμβων του δδένδρου ονομάζεται βάθος (depth) ή ύψος (height) του δένδρου.
Υπόδενδρο (Subtree) είναι ένα δένδρο το οποίο σχηματίζεται έχοντας ως ρίζα κάποιον άλλο κόμβο.
Δάσος (Forest) είναι ένα σύνολο από δένδρα και σχηματίζεται αν κόψουμε ένα δένδρο σε έναν κόμβο με παιδιά.
Ένα δένδρο του οποίου κάθε κόμβος έχει δύο το πολύ ακμές ονομάζεται δυαδικό δένδρο (binary tree).