4.3 - Fundamentals of algorithms
No description yet. This curated deck is ready for daily study.
Card preview (5)
What is in-order traversal and what is it used for?
Each node is visitedbetween each of its subtrees (flag under nodes) Returns the values of a binary search tree in ascending order
What is pre-order traversal and what is it used for?
Each node is visitedbefore the algorithm traverses either of the node’s subtrees (flag left of nodes) Creates a copy of the tree
What is post-order traversal and what are its 2 uses?
Each node is visitedafter both of its subtrees (flag right of nodes) • Can be used to delete a tree’s contents • Obtains the post-fix expression of an expression tree
How do you use a stack to convert a post-fix expression into an in-fix expression (or evaluate a post-fix expression)? (5 points)
• Traverse the expression from left to right • Push every operand into the stack until you reach an operator. • Pop the last 2 operands pushed into the stack and apply the operator to the 2 operands (operand 2, operator, operand 1). • Put brackets around the expression created/evaluate it and push it into the stack. • Continue steps 2-4 until you reach the end and pop the result.
What are the 3 advantages of Reverse Polish Notation?
Doesn’t need brackets - no need for BODMAS Simpler for a machine to evaluate No need for backtracking in evaluation - operators appear in the order required for computation and can be evaluated from left to right