文档介绍：算法和数据结构09
Overview
Trees.
Terminology.
Traversal of Binary Trees.
Expression Trees.
Binary Search Trees.
2019-3
n
Examples of Binary Trees
A
B
A
B
empty
empty
A
B
C
D
E
F
G
H
I
# nodes = 9
height of root = 4
2019-3
23
Binary Expression Trees
Use binary trees to represent arithmetic expressions
.,
/
a
*
e
-
c
d
2019-3
24
Arithmetic Expressions
(a + b) * (c + d) + e – f/g*h +
Expressions comprise three kinds of entities.
Operators (+, -, /, *).
Operands
(a, b, c, d, e, f, g, h, , (a + b), (c + d), etc.).
Delimiters ((, )).
2019-3
25
Operator Degree
Number of operands that the operator requires.
Binary operator requires two operands.
a + b
c / d
e - f
Unary operator requires one operand.
+ g
- h
2019-3
26
Infix Form
Normal way to write an expression.
Binary operators come in between their left and right operands.
a * b
a + b * c
a * b / c
(a + b) * (c + d) + e – f/g*h +
2019-3
27
Operator Priorities
How do you figure out the operands of an operator?
a + b * c
a * b + c / d
This is done by assigning operator priorities.
priority(*) = priority(/) > priority(+) = priority(-)
When an operand lies between two operators, the operand associates with the operator that has higher priority.
2019-3
28
Tie Breaker
When an operand lies between two operators that have the same priority, the operand associates with the operator on the left.
a + b - c
a * b / c / d
2019-3
29
Delimiters
Subexpression within delimiters is treated as a single operand, independent from the remainder of the expression.
(a + b) * (c – d) / (e – f)
2019-3
30
Infix Expression Is Hard To Parse
Need operator priorities, tie breaker, and delimiters.
This makes computer evaluation more difficult than is necessary.
Postfix and prefix expression forms do not rely on operator priorities, a tie breaker, or delimiters.
So it is easier for a computer to evaluate expressions