Τα δυαδικά δέντρα αναζητήσεως είναι πιο χρήσιμα από τις λίστες για δύο λόγους: Πρώτον επειδή τα δυαδικά δέντρα είναι ταξινομημένα και δεύτερον διότι έχουν γρηγορότερο χρόνο εκτέλεσης. Για παράδειγμα σε μία λίστα με 1.000.000.000 κόμβους η αναζήτηση ενός κόμβου μπορεί να διασχίσει όλη τη λίστα. Στα δυαδικά δέντρα η αναζήτηση θα διασχίσει περίπου 30 μόνο κόμβους.
Η διάσχιση ενός δυαδικού δέντρο αναζητήσεως μπορεί να γίνει με τέσσερις τρόπους:
α) Ενθεματική διάσχιση
β) Προθεματική διάσχιση
γ) Επιθεματική διάσχιση
δ) Επίπεδο - επίπεδο (κατά πλάτος)
Η ενθεματική διάσχιση (inorder) ακολουθεί τον κανόνα: Πριν εκτυπώσουμε την πληροφορία κάποιου κόμβου, θα πρέπει να έχουμε προσπελάσει όλους τους κόμβους που βρίσκονται αριστερά του (στο αριστερό υπόδεντρο του). Στη συνέχεια εκτυπώνουμε την πληροφορία του κόμβου και μετά εκτυπώνουμε την πληροφορία του δεξιού υπόδεντρου. Η καλύτερη προσέγγιση είναι η αναδρομή. Προγραμματιστικά η ενθεματική διάσχιση υλοποιείται ως εξής:
public void inorder(node n)
{
if (n!=null)
{
inorder(n.getLeft());
System.out.println("Node key="+n.getItem().getKey());
inorder(n.getRight());
}
}
Παρακάτω έχουμε ένα παράδειγμα ενθεματικής διάσχισης:
Η σειρά διέλευσης των κόμβων είναι: 2 4 6 7 12 23 30
Η προθεματική διάσχιση (preorder) ακολουθεί τον κανόνα: Προσπελαύνουμε έναν κόμβο πρώτα και στη συνέχεια προσπελαύνουμε πρώτα το αριστερό υπόδεντρο του και μετά το δεξιό υπόδεντρο του. Η καλύτερη προσέγγιση είναι η αναδρομή. Προγραμματιστικά η προθεματική διάσχιση υλοποιείται ως ακολούθως:
public void preorder(node n)
{
if (n!=null)
{
System.out.println("Node key="+n.getItem().getKey());
preorder(n.getLeft());
preorder(n.getRight());
}
}
Παρακάτω έχουμε ένα παράδειγμα προθεματικής διάσχισης:
Η σειρά διέλευσης των κόμβων είναι: 7 4 2 6 23 12 30
Η επιθεματική διέλευση (postorder) δυαδικού δέντρου ακολουθεί τον κανόνα: Πριν εκτυπώσουμε την πληροφορία κάποιου κόμβου, θα πρέπει να έχουμε προσπελάσει όλους τους κόμβους που βρίσκονται στα αριστερά του (στο αριστερό υπόδεντρο του), στη συνέχεια προσπελαύνουμε το δεξιό υπόδεντρο του και τελευταία εκτυπώνουμε την πληροφορία του κόμβου. Η καλύτερη προσέγγιση είναι η αναδρομή. Προγραμματιστικά η επιθεματική διέλευση υλοποιείται ως εξής:
public void postorder(node n)
{
if (n!=null)
{
postorder(n.getLeft());
postorder(n.getRight());
System.out.println("Node key="+n.getItem().getKey());
}
}
Παρακάτω φαίνεται ένα παράδειγμα επιθεματικής διέλευσης δυαδικού δέντρου:
Η σειρά διέλευσης των κόμβων είναι: 2 6 4 12 30 23 7
Στη διέλευση δυαδικού δέντρου κατά πλάτος πρώτα προσπελαύνουμε (τυπώνουμε) όλους τους κόμβους ενός επιπέδου πριν προχωρήσουμε στο επόμενο επίπεδο. Για να το κάνουμε αυτό χρησιμοποιούμε μία ουρά. Ξεκινάμε βάζοντας τη ρίζα του δέντρου στην ουρά. Μέχρι να αδειάσει η ουρά επαναλαμβάνουμε:
1. Βγάζουμε από την ουρά έναν κόμβο
2. Εκτυπώνουμε τον κόμβο
3. Βάζουμε στην ουρά τα παιδιά του κόμβου
Προγραμματιστικά αυτή η διέλευση υλοποιείται ως ακολούθως:
public void printLevelByLevel(BTNode n)
{
Queue<BTNode> nodeQueue = new LinkedList<BTNode>();
nodeQueue.add(n);
while (!nodeQueue.isEmpty())
{
BTNode currentNode = nodeQueue.remove();
System.out.println("LeveByLevel:Node key="+currentNode.getItem().getKey());
if (currentNode.getLeft()!=null)
nodeQueue.add(currentNode.getLeft());
if (currentNode.getRight()!=null) {
nodeQueue.add(currentNode.getRight());
}
}