11.3 Tree Traversal

Question 1

Universal Address Systems

Answer 1

A way to totally order the vertices of and ordered rooted tree. We do this recursively:
• Label the root with the integer 0. Then label its k children (at level 1) from left to right with
1, 2, 3, . . . , k.
• For each vertex v at level n with label A, label its kv children, as they are drawn from left to
right, with A.1, A.2, . . . , A.kv.

ex. The lexicographic ordering for this tree is 0

Question 2

PreOrder Traversal

Answer 2

Root->Left->Right

Question 3

InOrder Traversal

Answer 3

Left->Root->Right

Question 4

PostOrder Traversal

Answer 4

Left->Right->Root

Question 5

PostOrder Traversal

Answer 5

Left->Right->Root

Question 6

A tree used to solve arithmetic

Answer 6

Internal vertices: operations

Leaves: variables or numbers

Question 7

Infix Notation

Answer 7

produces the original expression with
the elements and operations in the same order as they originally occurred, except unary operations.
The fully parenthesized expression is the infix form.
Infix form: (6 − 4) ∗ (3 + (5 − 1))

Question 8

Prefix Notation

Answer 8

obtained by traversing its rooted tree in preorder. Binary
operator precedes its two operands. Evaluate an expression in prefix form by working right to left.
Prefix form: ∗ − 64 + 3 − 51

Question 9

Postfix Notation

Answer 9

obtained by traversing its rooted tree in postorder. Binary operator follows its two operands. Evaluate an expression in postfix form by working left to right.
Postfix form: 64 − 351 − +∗