Courses‎ > ‎AP Computer Science 2‎ > ‎Konstantinovich‎ > ‎

2017-04-24 Trees + HW11

posted Apr 24, 2017, 5:09 AM by Samuel Konstantinovich   [ updated Apr 26, 2017, 6:21 AM ]
Please make sure you put your stack calculation homework in the correct folder with the proper class name:
11StackCalculations/StackCalc.java

If you make a driver file with the following main, it should work:
public static void main(String[] args)
{
    System.out.println(StackCalc.eval("10 2 +"));//12.0
    System.out.println(StackCalc.eval("10 2 -"));//8.0
    System.out.println(StackCalc.eval("10 2.0 +"));//12.0
    System.out.println(StackCalc.eval("11 3 - 4 + 2.5 *"));//30.0
    System.out.println(StackCalc.eval("8 2 + 99 9 - * 2 + 9 -"));//893.0
    System.out.println(StackCalc.eval("10 2 + 10 * 1 + 1 1 1 + + + 10 10 + -"));//104.0
}


Goal: Trees

Graph: a relational data structure that stores points of interest and the relationships between them (nodes and edges)
The edges are pairs of nodes.
-Some graphs the edges are one way (directed graph) 
-Some graphs the edges have an additional value or weight (weighted graph)
-Directed graphs can have different weights in each direction.

A linked list is a graph
A maze can be represented by a graph. Adjacent spaces have an edge between them.

Tree: an acyclic graph.

Breadth First Search vs. Depth First Search

Depth-First Search

-Tests all possibilities in one path until it needs to backtrack. This is the recursively backtrack you have written for your previous assignments (until now!)

-Does not guarantee shortest path / closest value.

(Visually DFS goes to bottom of a tree, then backtracks, etc.)


Breadth-First Search

BFS checks the first node, then its direct children, then the children of those. Tests all possibilities in order from the closest possibility to the furthest.

This will find the closest matching value or shortest path to a goal.

(Visually BFS will check the next level of the tree, then the next level... etc)

687474703a2f2f7777772e6373652e756e73772e6564752e61752f7e62696c6c772f4a757374736561726368312e676966.gif






Maze example:


# 0 1 2 3 4

0 S _ _ _ _

1 _ # # # _

2 _ _ _ # _

3 _ # _ # _

4 _ _ _ # E

Lets label the spaces we want to go to make our lives easier!

# 0 1 2 3 4

0 S a b c d

1 e # # # f

2 g h i # j

3 k # l # m

4 n o p # q


BFS:
check
a,e on the 1st pass
b,g on the 2nd pass
c,h,k on the 3rd pass
d,i,n on the 4th pass
f,l,o on the 5th
p,j on the 6th
m on the 7th
q on the 8th.


or:

0 1 2 3 4

1 # # # 5

2 3 4 # 6

3 # 5 # 7

4 5 6 # 8

Comments