Ένα δέντρο είναι ένα μοντέλο απεικόνισης μια ιεραρχικής δομής.Πρώτα όμως θα πρέπει να δώσουμε τους απαραίτητους ορισμούς.



Βασικά χαρακτηριστικά των Δέντρων:

  1. Γράφημα ακυκλικό και συνεκτικό.
  2. Δέντρο με n κορυφές έχει m = n – 1 ακμές.
  3. Ρίζα: κόμβος χωρίς πρόγονο. Δέντρο με ρίζα : ιεραρχία.
  4. Φύλλο: κόμβος χωρίς απογόνους.
  5. Πρόγονοι t: κόμβοι στο (μοναδικό) μονοπάτι t προς ρίζα.
  6. Απόγονοι t: κόμβοι σε μονοπάτια από t προς φύλλα.
  7. Υποδέντρο t: Δέντρο αποτελούμενο από t και απογόνους του.
  8.  Επίπεδο t: μήκος μονοπατιού από t προς ρίζα.
  9.  Ύψος: μέγιστο επίπεδο κόμβου (φύλλου). Μέγιστη απόσταση από ρίζα.
  10. Βαθμός t : αριθμός παιδιών t.

Βασικός ορισμός 

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

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

Δυαδικό Δέντρο Ορισμός 


Ένα δυαδικό δένδρο (binary tree, BT) Τ είναι μία πεπερασμένη (πιθανώς
κενή) συλλογή στοιχείων. Όταν το δυαδικό δένδρο δεν είναι κενό, τότε έχει
μία ρίζα και τα υπόλοιπα στοιχεία (αν υπάρχουν) επιμερίζονται σε δύο
δυαδικά δένδρα που ονομάζονται το αριστερό και το δεξιό υποδένδρο του
Τ.

Ιδιότητες


  • Το σχέδιο ενός δυαδικού δένδρου με n στοιχεία (n > 0) έχει ακριβώς n-1 ακμές.
  • Ένα δυαδικό δένδρο ύψους h (h ≥ 0) έχει τουλάχιστον h και το πολύ (2^h+1)-1 στοιχεία.

Έστω i (1 ≤ i ≤ n) ο αριθμός ενός στοιχείου ενός συμπληρωμένου δυαδικού δένδρου:
  1. Αν i = 1, το στοιχείο είναι η ρίζα, αλλιώς είναι παιδί του κόμβου με αριθμό int[i/2].
  2. Το αριστερό του παιδί έχει αριθμό 2i (αν 2i ≤ n, αλλιώς δεν έχει αριστερό παιδί).
  3. Το δεξιό του παιδί έχει αριθμό 2i+1 (αν 2i+1 ≤ n, αλλιώς δεν έχει δεξιό παιδί).

Διάσχιση:

– Προδιατεταγμένη διάσχιση (preorder): Για κάθε κόμβο, επισκεπτόμαστε πρώτα τον ίδιο τον κόμβο, έπειτα τους κόμβους του αριστερού του υποδένδρου και στη συνέχεια τους κόμβους του δεξιού του υποδένδρου.
– Μεταδιατεταγμένη διάσχιση (postorder): Για κάθε κόμβο, επισκεπτόμαστε πρώτα τους κόμβους του αριστερού του υποδένδρου, έπειτα τους κόμβους του δεξιού του υποδένδρου και στη συνέχεια τον ίδιο τον κόμβο.
– Ενδοδιατεταγμένη διάσχιση (inorder): Για κάθε κόμβο, επισκεπτόμαστε πρώτα τους κόμβους του αριστερού του υποδένδρου, έπειτα τον ίδιο τον κόμβο και στη συνέχεια τους κόμβους του δεξιού του υποδένδρου.
– Κατά σειρά επιπέδων (level order): Επισκεπτόμαστε τους κόμβους κατά επίπεδα, από πάνω (τη ρίζα) προς τα κάτω, και μέσα σε ένα επίπεδο από αριστερά προς τα δεξιά.

Παράδειγμα :

Προδιατεταγμένη:
A, B, D, C, E, G, F, H, I

Μεταδιατεταγμένη:
D, B, G, E, H, I, F, C, A

Ενδοδιατεταγμένη:
B, D, A, G, E, C, H, F, I

Κατά σειρά επιπέδων:
A, B, C, D, E, F, G, H, I
– δένδρων)