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.javaIf 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: TreesGraph: 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 graphA maze can be represented by a graph. Adjacent spaces have an edge between them.Tree: an acyclic graph.Breadth First Search vs. Depth First SearchDepth-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 SearchBFS 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)Maze example:# 0 1 2 3 40 S _ _ _ _1 _ # # # _2 _ _ _ # _3 _ # _ # _4 _ _ _ # ELets label the spaces we want to go to make our lives easier!# 0 1 2 3 40 S a b c d1 e # # # f2 g h i # j3 k # l # m4 n o p # qBFS:checka,e on the 1st passb,g on the 2nd passc,h,k on the 3rd passd,i,n on the 4th passf,l,o on the 5thp,j on the 6thm on the 7thq on the 8th.or: 0 1 2 3 4 1 # # # 5 2 3 4 # 6 3 # 5 # 7 4 5 6 # 8