Binære træer (BTS) er datastrukturer anvendes af edb-programmører , hvis software skal repræsentere mellemstore til store datasæt i en organiseret og struktureret måde. En BT består af en forælder node med et maksimum på to valgfrie barn noder : en venstre barn og en højre barn. Applikationsspecifikke datastrukturer såsom søgetræer , dynger og udtryk træer er simpelthen samlinger af individuelle BTs knyttet sammen for at danne en kollektiv datasæt. Der er tre forskellige metoder til at gennemkører BTs : preorder traversal , inorder traversal og Postorder traversal . Preorder Traversal
Preorder traversal besøger træet noder i denne rækkefølge: forælder, venstre barn , højre barn. Nogle programmer for preorder traversal er evalueringen af udtryk i præfiks notation og behandlingen af abstrakte syntaks træer ved compilere . Den følgende pseudokode viser den nøjagtige procedure for en forudbestilling traversal : Hej
---------------------- PROCEDURE preorder ( Binary_Tree_Node T) BEGINProcessNode (T) Hvis (T venstre barn er NOT NULL) BEGINPreOrder (T venstre barn ) endif (T ret barn er NOT NULL ) BEGINPreOrder (T ret barn ) ENDEND
Med sigte Traversal
med sigte traversal besøger træet noder i denne rækkefølge: venstre barn , forældre , højre barn. Binær søgning træer ( en særlig type BT ) brug sigte traversal at udskrive alle deres data i alfanumerisk rækkefølge . Den følgende pseudokode viser den præcise procedure for et sigte traversal : Hej
---------------------- PROCEDURE sigte ( Binary_Tree_Node T) BEGINIf (T venstre barn er NOT NULL ) BEGINInOrder (T venstre barn ) ENDProcessNode (T) Hvis (T ret barn er NOT NULL ) BEGINInOrder (T ret barn ) ENDEND ------------------- -
Postorder traversal
Postorder traversal besøger træet noder i denne rækkefølge: venstre barn , højre barn , forælder. En populær ansøgning om anvendelse af Postorder traversal er den evaluerende af udtryk i postfix notation. Den følgende pseudokode viser den nøjagtige procedure for en Postorder traversal : Hej
---------------------- PROCEDURE Postorder ( Binary_Tree_Node T) BEGINIf (T venstre barn er NOT NULL ) BEGINPostOrder (T venstre barn ) endif (T ret barn er NOT NULL ) BEGINPostOrder (T ret barn ) ENDProcessNode (T) END ------------------- -