Scribd
Upload
11 views1 page

Hydron 2

The document discusses the traversal methods of expression trees, specifically pre-order, post-order, and in-order traversals. Pre-order traversal generates a prefix expression, while post-order traversal produces a postfix representation, both of which can be used for evaluating expressions. In-order traversal is highlighted for its utility in binary search trees, returning values in a sorted order.

Uploaded by

shivamsuyal21
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
11 views1 page

Hydron 2

The document discusses the traversal methods of expression trees, specifically pre-order, post-order, and in-order traversals. Pre-order traversal generates a prefix expression, while post-order traversal produces a postfix representation, both of which can be used for evaluating expressions. In-order traversal is highlighted for its utility in binary search trees, returning values in a sorted order.

Uploaded by

shivamsuyal21
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 1

Applications

Tree representing the arithmetic expression: A * (B − C) + (D + E)


Pre-order traversal can be used to make a prefix expression (Polish notation)
from 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. Pre-order 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. Post-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 trees because it returns
values from the underlying set in order, according to the comparator that set up the
binary search tree.

You might also like