text: Problem of the Day
  
  1 / 27
  
  # Problem of the Day - PowerPoint PPT Presentation
  
  Problem of the Day. Solve this equation by moving the numbers: 7 6 = 2 4. Problem of the Day. Solve this equation by moving the numbers: 7 6 = 2 4 7 2 = 4 9. CSC 212 – Data Structures. Lecture 34 5 : Implementing Traversals. Traversing Binary Trees.
  
  I am the owner, or an agent authorized to act on behalf of the owner, of the copyrighted work described.
  
  ## PowerPoint Slideshow about 'Problem of the Day' - chase
  
  Download Policy: Content on the Website is provided to you AS IS for your information and personal use and may not be sold / licensed / shared on other websites without getting consent from its author.While downloading, if for some reason you are not able to download a presentation, the publisher may have deleted the file from their server.
  
  - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - -
  Presentation Transcript
  Problem of the Day
  • Solve this equation by moving the numbers:
  
  76 = 24
  
  Problem of the Day
  • Solve this equation by moving the numbers:
  
  76 = 24
  
  72=49
  
  CSC 212 – Data Structures
  
  ### Lecture 345:Implementing Traversals
  
  Traversing Binary Trees
  • Trees are another Collection of data
  • Positions required in the Tree ADT methods
  • ADT uses generic type to specify type of element
  • Want to iterate through tree’s elements
  • This is not optional; Trees are Iterable
  • Could use any traversal algorithm; choose logical one
  • But how do we implement traversals & Iterator?
  Traversal Methods
  • Many traversals, differ in order nodes visited
  • Do parent then do each kid in pre-order traversal
  Traversal Methods
  • Many traversals, differ in order nodes visited
  • Do parent then do each kid in pre-order traversal
  • Post-order traversal does kids before doing parents
  Traversal Methods
  • Many traversals, differ in order nodes visited
  • Do parent then do each kid in pre-order traversal
  • Post-order traversal does kids before doing parents
  • Do left kid, parent, then right kid in in-order traversal
  Traversal Algorithms
  • So, how do we do each one of these?
  Traversal Algorithms
  • So, how do we do each one of these? implement each traversal?
  • Recursion usually answer to questions involving trees
  • The algorithm uses same approach for all three
  • Where Nodes done only difference; rest is identical
  Binary Tree Traversal
  
  Algorithmtraverse(tree, v)
  
  // Do node here for pre-order traversal
  
  traverse(tree, tree.left(v));
  
  // Do node here for in-order traversal
  
  traverse(tree, tree.right(v));
  
  // Do node here for post-order traversal
  
  Important Feature of Any Coder
  • Nearly all of the great coders are inherently lazy
  • Hope for you all -- you have this part completed
  • Unfortunately, true laziness requires lot of work
  • Debugging code wastes time could be websurfing
  • To make small change, more time lost rewriting code
  • Small amount of planning save lots of time later
  Template Method Pattern
  • Common design pattern used to simplify code
  • Implement class of algorithms using an abstract class
  • Class leaves all actual work in abstract methods
  • Subclasses written for each member algorithm
  • To make concrete, each overrides abstract method
  • Method performs specific actions for that algorithm
  • New algorithms are very quick & easy to write
  • Most bugs already found & fixed, so less work here
  • Leaves only actions & actions usually are small
  Binary Tree Traversal Template
  
  public class EulerTour<E, R> {abstract void visit(Position<E> p);Rtour(BinaryTree<E> t, Position<E> p) {TourResult<R> r = new TourResult<R>(); if (t.hasLeft(p)) {r.left = tour(t, t.left(p)); }/*Process p*/ if (t.hasRight(p)) {r.right = tour(t, t.right(p)); } return r.out;}
  
  Oops…
  
  public class EulerTour<E, R> {abstract void visit(Position<E> p);Rtour(BinaryTree<E> t, Position<E> p) {TourResult<R> r = new TourResult<R>(); if (t.hasLeft(p)) {r.left = tour(t, t.left(p)); }/*Process p*/ if (t.hasRight(p)) {r.right = tour(t, t.right(p)); } return r.out;}
  
  Pre-order traversal needsprocessing here
  
  Oops…
  
  public class EulerTour<E, R> {abstract void visit(Position<E> p);Rtour(BinaryTree<E> t, Position<E> p) {TourResult<R> r = new TourResult<R>(); if (t.hasLeft(p)) {r.left = tour(t, t.left(p)); }/*Process p*/ if (t.hasRight(p)) {r.right = tour(t, t.right(p)); } return r.out;}
  
  Post-order traversal needsprocessing here
  
  Better Solution
  
  public class Traversal<E, R> {// Perform actions before kids processedabstract void visitLeft(Position<E> p);// Perform actions after kids processedabstract void visitRight(Position<E> p);// Perform actions between when kids processedabstract void visitBelow(Position<E> p);
  
  Better Solution
  
  public class EulerTour<E, R> {Rtour(BinaryTree<E> t, Position<E> p) {TourResult<R> r = new TourResult<R>();visitLeft(p); if (t.hasLeft(p)) {r.left = tour(t, t.left(p)); }visitBelow(p); if (t.hasRight(p)) {r.right = tour(t, t.right(p)); }visitRight(p); return r.out;}
  
  Better Solution
  
  class InOrder<E> extends EulerTour<E,String>{public String execute(BinaryTree<E> t) { init(t); return eulerTour(t.root());}void visitLeft(TourResult<String> r,Position<E> p){// Do nothing – we are not Woody Allen (pre-order traversal) }void visitRight(TourResult<String> r,Position<E> p){// Do nothing – we are not Michael Jackson (post-order traversal) }void visitBelow(TourResult<String> r,Position<E> v){r.out = r.left + " " + v.element() +}
  
  Better Solution
  
  class InOrder<E> extends EulerTour<E,String>{public String execute(BinaryTree<E> t) { init(t); return eulerTour(t.root());}void visitLeft(TourResult<String> r,Position<E> p){// Do nothing – we are not Woody Allen (pre-order traversal) }void visitRight(TourResult<String> r,Position<E> p){// Do nothing – we are not Michael Jackson (post-order traversal)}void visitBelow(TourResult<String> r,Position<E> v){r.out = r.left + " " + v.element() +...}
  
  Better Solution
  
  class InOrder<E> extends EulerTour<E,String>{public String execute(BinaryTree<E> t) { init(t); return eulerTour(t.root());}void visitLeft(TourResult<String> r,Position<E> p){// Do nothing – we are not Woody Allen (pre-order traversal) }void visitRight(TourResult<String> r,Position<E> p){// Do nothing – we are not … I have no joke (post-order traversal) }void visitBelow(TourResult<String> r,Position<E> p){r.out = r.left + " " + p.element() +...}
  
  Better Solution
  
  class InOrder<E> extends EulerTour<E,String>{// execute from before is here, but not enough space… void visitLeft(TourResult<String> r,Position<E> p) { // Do nothing – its too early }void visitBelow(TourResult<String> r,Position<E> p) { // Do nothing – its too early }
  
  Better Solution
  
  class InOrder<E> extends EulerTour<E,String>{void visitRight(TourResult<String> r,Position<E> v){r.out = ""; if (getTree().hasLeft(v)) {r.out = r.left + " "; }r.out += p.element(); if (getTree().hasRight(v)) {r.out += " " + r.right; }}
  
  Wait A Minute…
  • Lecture began talking about Tree's Iterator
  • Implementing traversals discussed for rest of lecture
  • I may not know much, but traversals != Iterator
  • How to implement next() & hasNext()
  • Recursion can't be used, since calls occur over time
  • How can we reuse these ideas to make an iterator?
  Cheating To Win
  • next() & hasNext() very hard to implement
  • Much easier for Sequences (which are Iterable)
  • In fact, we have already done this for Sequence
  • Use that Iteratorby adding elements to Sequence
  • Define new subclass for this type of traversal
  • Valid to build entire Iterator all at one go
  • Add & combine Sequences in visit* methods
  • executemethod returns a Sequence
  • Get into your groups and complete activity
  For Next Lecture
  • Read parts of GT 7.1 & 7.3 for Monday
  • How do we implement a tree?
  • Binary trees are similar; how do we implement them?
  • I loved CSC111; can’t we use arrays for binary trees?
  • Week #12 posted & due next Tuesday (after break)
  • Programming Assignment #3 available today
metadata: {"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}