Binary Tree Traversal Μέθοδοι

Δυαδικά δέντρα ( BTS ) είναι δομές δεδομένων που χρησιμοποιούνται από τους προγραμματιστές υπολογιστών των οποίων το λογισμικό πρέπει να αντιπροσωπεύουν μεσαίου και μεγάλου μεγέθους σύνολα δεδομένων σε ένα οργανωμένο , δομημένο τρόπο . Η BT αποτελείται από μια μητρική κόμβο με μέγιστο αριθμό δύο προαιρετικών κόμβων παιδί : ένα αριστερό παιδί και το δικαίωμα του παιδιού . Συγκεκριμένη εφαρμογή δομών δεδομένων, όπως τα δέντρα αναζήτησης , σωροί και δέντρα έκφρασης είναι απλά συλλογές μεμονωμένων BTS συνδέονται μαζί για να σχηματίσουν ένα συλλογικό σύνολο δεδομένων. Υπάρχουν τρεις διαφορετικές μεθόδους για την διάσχιση BTS : preorder διάσχιση , Inorder διάσχιση και postorder διάσχισης . Preorder Traversal
Η

Preorder επισκέψεις διάσχισης των κόμβων του δέντρου με αυτή τη σειρά : γονέας , το αριστερό παιδί , το δικαίωμα του παιδιού . Ορισμένες εφαρμογές της διάσχισης preorder είναι η αξιολόγηση των εκφράσεων σε συμβολισμό πρόθεμα και η επεξεργασία των αφηρημένων δέντρα σύνταξη από compilers . Το ακόλουθο ψευδοκώδικα δείχνει την ακριβή διαδικασία για την διάσχιση preorder :

---------------------- ΔΙΑΔΙΚΑΣΙΑ το preorder ( Binary_Tree_Node T ) BEGINProcessNode ( T ) Αν ( αριστερό παιδί Τ δΕΝ είναι NULL ) BEGINPreOrder ( αριστερό παιδί Τ ) endif ( το δικαίωμα του παιδιού T είναι NOT NULL ) BEGINPreOrder ( το δικαίωμα του παιδιού Τ ) ENDEND εικόνων
Inorder Διέλευση
Η

κόμβους Inorder επισκέψεις διάσχιση δέντρου με αυτή τη σειρά : το αριστερό παιδί, γονέας , το δικαίωμα του παιδιού . Δυαδικά δένδρα αναζήτησης ( ένας ειδικός τύπος της BT) χρησιμοποιούν Inorder διάσχιση για να εκτυπώσετε όλα τα δεδομένα τους σε αλφαριθμητική σειρά . Το ακόλουθο ψευδοκώδικα δείχνει την ακριβή διαδικασία για την διάσχιση inorder :

---------------------- ΔΙΑΔΙΚΑΣΙΑ Inorder ( Binary_Tree_Node T ) BEGINIf ( αριστερά Τ το παιδί είναι NOT NULL ) BEGINInOrder ( αριστερό παιδί Τ ) ENDProcessNode ( T ) Αν ( το δικαίωμα του παιδιού T είναι NOT NULL ) BEGINInOrder ( το δικαίωμα του παιδιού Τ ) ENDEND ------------------- κόμβοι επισκέψεις

Η Postorder Διέλευση
Η

Postorder διάσχιση δέντρου με αυτή τη σειρά - : αριστερό παιδί , το δικαίωμα του παιδιού , γονέα . Μια δημοφιλής εφαρμογή για τη χρήση του postorder διάσχιση είναι η αξιολόγηση των εκφράσεων σε συμβολισμό postfix . Το ακόλουθο ψευδοκώδικα δείχνει την ακριβή διαδικασία για την διάσχιση postorder :

---------------------- ΔΙΑΔΙΚΑΣΙΑ PostOrder ( Binary_Tree_Node T ) BEGINIf ( αριστερά Τ το παιδί είναι NOT NULL ) BEGINPostOrder ( αριστερό παιδί Τ ) endif ( το δικαίωμα του παιδιού T είναι NOT NULL ) BEGINPostOrder ( το δικαίωμα του παιδιού Τ ) ENDProcessNode ( T ) ΤΕΛΟΣ ------------------- -
Η
εικόνων