Tree traversal: Difference between revisions

Revision as of 15:39, 10 June 2023

Revision as of 15:49, 10 June 2023

Line 94:

==Applications==

[[File:AST binary tree arith variables.svg|260px|thumb|Tree representing the arithmetic expression: ''A'' * {{nowrap|(''B'' − ''C'')}} + {{nowrap|(''D'' + ''E'')}}]]

Pre-order traversal can be used to make a prefix expression ([[Polish notation]]) from [[Parse tree|expression trees]]: traverse the expression tree pre-orderly. For example, traversing the depicted arithmetic expression in pre-order yields "+ * ''A'' − ''B'' ''C'' + ''D'' ''E''". In prefix notation, there is no need for any parentheses as long as each operator has a fixed number of operands. PreorderPre-order traversal is also used to create a copy of the tree.

PostorderPost-order traversal can generate a postfix representation ([[Reverse Polish notation]]) of a binary tree. Traversing the depicted arithmetic expression in post-order yields "''A'' ''B'' ''C'' − * ''D'' ''E'' + +"; the latter can easily be transformed into [[machine code]] to evaluate the expression by a [[stack machine]]. PostorderPost-order traversal is also used to delete the tree. Each node is freed after freeing its children.

In-order traversal is very commonly used on [[binary search tree]]s because it returns values from the underlying set in order, according to the comparator that set up the binary search tree.