算法和数据结构09.ppt

2004-3 L.Chen Chapter 8 BINARY AND OTHER TREES Overview Trees. Terminology. Traversal of Binary Trees. Expression Trees. Binary Search Trees. 8.1 Trees Parts of a Tree Parts of a Tree Parts of a Tree Parts of a Tree Parts of a Tree Parts of a Tree Parts of a Tree Parts of a Tree Parts of a Tree Parts of a Tree Parts of a Tree height = depth = number of levels Node Degree = Number Of Children Tree Degree = Max Node Degree 8.2 Binary Trees Differences Between A Tree A Binary Tree The subtrees of a binary tree are ordered; those of a tree are not ordered. Examples of Binary Trees Binary Expression Trees Use binary trees to represent arithmetic expressions e.g., Arithmetic Expressions (a + b) * (c + d) + e – f/g*h + 3.25 Expressions comprise three kinds of entities. Operators (+, -, /, *). Operands (a, b, c, d, e, f, g, h, 3.25, (a + b), (c + d), etc.). Delimiters ((, )). 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 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 + 3.25 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. 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 Delimiters Subexpression within delimiters is treated as a single operand, independent from the remainder of the expression. (a + b) * (c – d) / (e – f) Infix Expression Is Hard To Parse Need operator priorities, tie breaker, and delimiters. This makes computer evaluation more difficult than is necessary. Po