Tree traversal: Difference between revisions

Revision as of 14:57, 24 May 2023

Revision as of 15:39, 10 June 2023

Line 96:

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-orderPostorder 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.