Content deleted Content added
m →Types: More specific link/redirect. |
m Fix grammar in description of pre-order traversal |
||
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 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.
| |||