Graphs and Expression Trees

Objectives

  • Work with Graphs.

    • DFS
    • BFS
    • Topological sort

  • Work with Expression Trees.

    • Create an expression tree from an infix expression.
    • Traverse a tree to generate prefix, infix, and postfix expressions.
    • Evaluate an expression using post-order tree traversal.
Graphs

Question 1: For the following graph of cities, answer the questions that follow. For all problems, remember to use the lowest numbered city as the highest priority.

City Graph

  • DFS from Denver.

  • BFS from Denver.

  • DFS from Dallas.

  • BFS from Dallas.

Question 2: For the following directed graph, answer the questions that follow.

Nodes = {a, b, c, d, e, f, g, h, i, j, k, l, m, n}

Edges: {(a, b), (b, c), (b, d), (c, f), (c, g), (c, h), (c, e), (c, j), (c, k), (d, e), (d, j), (d, k), (e, h), (e, l), (e, m), (e, n), (e, i), (e, j), (f, l)}

  • DFS from a.

  • BFS from a.

  • Topological order.

Expression Trees

Question 1. Given the following expression tree, answer the questions that follow.

Expression Tree 1

  • Show the infix expression represented by the tree, with spaces between each token, and no leading or trailing spaces.

  • Show the prefix expression represented by the tree, with spaces between each token, and no leading or trailing spaces.

  • Show the postfix expression represented by the tree, with spaces between each token, and no leading or trailing spaces.

  • What does the expression evaluate to, assuming integer math and the normal Java order of operations, which are of course reflected in the prefix and postfix forms and the tree?

Question 2. Given the following infix expression, answer the questions that follow.

  • Draw an expression tree that represents the infix expression given below.

    13 % 7 * ( 4 + (5 - 3) * (19 / 8))

  • Show the prefix expression represented by the tree, with spaces between each token, and no leading or trailing spaces.

  • Show the postfix expression represented by the tree, with spaces between each token, and no leading or trailing spaces.

  • What does the expression evaluate to, assuming integer math and the normal Java order of operations, which are of course reflected in the prefix and postfix forms and the tree?