Tree traversal: Difference between revisions

Revision as of 21:15, 21 February 2023

Revision as of 11:02, 22 February 2023

Line 95:

==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 ''A'' * (''B'' − ''C'') + (''D'' + ''E'') 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. Preorder traversal is also used to create a copy of the tree.

Post-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]]. Postorder 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.