Sentences vs. ListsTrees from Last LectureMapping over TreesExercise: Generalize!Mutual RecursionBinary TreesTree TraversalDepth-First TraversalBreadth-First TraversalPath FindingHIERARCHICAL DATA 8GEORGE [email protected] of Electrical Engineering and Computer SciencesUniversity of California, BerkeleyJuly 1, 20101 Sentences vs. ListsMy TA’s have strongly objected to the characterization I gave yesterday and so here’s the final word onthat. Lists are NOT sentences, and sentences are NOT lists. We should think about sentences as somethingcompletely different from lists. Specifically, we should think about sentences as being an ADT (abstractdata type) that is implemented using lists, but doesn’t have to be. We should always respect the abstractionbarrier between sentences and lists, by using the sentence constructs (sentence, every, keep, first,butfirst, etc) only on sentences, and using the list constructs (list, car, cdr, cons, append, etc) onlyon lists.2 Trees from Last Lecture2.1 Mapping over TreesOne thing we might want to do with a tree is create another tree, with the same shape as the original, butwith each datum replaced by some function of the original.2.1.1 Exercise: Generalize!Here’s two examples. Generalize this into a pattern!(define (square-tree tree)(make-tree (square (datum tree))(map (lambda (tr) (square-tree tr))(children tree) )))1(define (cube-tree tree)(make-tree (cube (datum tree))(map (lambda (tr) (cube-tree tr))(children tree) )))(define (treemap fn tree)(make-tree (fn (datum tree))(map (lambda (tr) (treemap fn tr))(children tree))))Every tree node consists of a datum and some children. In the new tree, the datum corresponding to thisnode should be the result of applying fn to the datum of this node in the original tree. What about thechildren of the new node? There should be the same number of children as there are in the original node,and each new child should be the result of calling treemap on an original child. Since a forest is just a list,we can use map (not treemap!) to generate the new children.This is a remarkably simple and elegant procedure, especially considering the versatility of the data struc-tures it can handle (trees of many different sizes and shapes).3 Mutual RecursionPay attention to the strange sort of recursion in this procedure. Treemap does not actually call itself!Treemap calls map, giving it a function that in turn calls treemap. The result is that each call to treemapmay give rise to any number of recursive calls, via map: one call for every child of this node.This pattern (procedure A invokes procedure B, which invokes procedure A) is called mutual recursion.We can rewrite treemap without using map, to make the mutual recursion more visible:;;;;; In file cs61a/lectures/2.2/tree11.scm(define (treemap fn tree)(make-tree (fn (datum tree))(forest-map fn (children tree))))(define (forest-map fn forest)(if (null? forest)’()(cons (treemap fn (car forest))(forest-map fn (cdr forest)))))Forest-map is a helper function that takes a forest, not a tree, as argument. Treemap calls forest-map,which calls treemap.Mutual recursion is what makes it possible to explore the two-dimensional tree data structure fully. Inparticular, note that reaching the base case in forest-map does not mean that the entire tree has beenvisited! It means merely that one group of sibling nodes has been visited (a “horizontal” base case), or thata node has no children (a “vertical” base case). The entire tree has been seen when every child of the rootnode has been completed.Note that we use cons, car, and cdr when manipulating a forest, but we use make-tree, datum, andchildren when manipulating a tree. Some students make the mistake of thinking that data abstractionmeans “always say datum instead of car”! But that defeats the purpose of using different selectors andconstructors for different data types.24 Binary TreesBinary trees are particularly powerful ways of organizing information. You will study them extensively inCS61B, but for now, we want to introduce the data abstraction:(make-binary-tree DATUM LEFT-BRANCH RIGHT-BRANCH)(datum BINARY-TREE)(left-branch BINARY-TREE)(right-branch BINARY-TREE)One particular special case of binary trees are binary search trees, which allow for rapid data lookup. Theydo so by forcing a property on every node. This property is that everything in the tree rooted at the rightbranch must be greater than the datum and everything in the tree rooted at the left branch must be less thanthe datum. To see that in action:101518125786231We’ll deal only with a lookup operation and an insertion operation. Both these operations are detailed inthe book, so I’ll omit time in lecture going over them in excessive detail, but they’re reproduced here.(define (lookup number bst)(if (null? bst)#f ;Can’t be in the tree!(cond ((= (datum bst) number) #t) ;found it!((> (datum bst) number) (lookup number (left-branch bst)))((< (datum bst) number) (lookup number (right-branch bst)) ))))(define (insert number bst)(if (null? bst)(make-binary-tree number ’() ’())(cond ((= (datum bst) number) bst) ;number already in tree!((> (datum bst) number)(make-binary-tree (datum bst)(insert number (left-branch bst))(right-branch bst)))((< (datum bst) number)(make-binary-tree (datum bst)(left-branch bst)(insert number (right-branch bst)))))))35 Tree TraversalMany problems involve visiting each node of a tree to look for or otherwise process some information there.Maybe we’re looking for a particular node, maybe we’re adding up all the values at all the nodes, etc. Thereis one obvious order in which to traverse a sequence (left to right), but many ways in which we can traversea tree. In the following examples, we look at a given node’s children before its siblings.5.1 Depth-First Traversal;;;;; In file cs61a/lectures/2.2/search.scm(define (depth-first-search tree)(print (datum tree))(for-each depth-first-search (children tree)))This is the easiest way, because the program’s structure follows the data structure; each child is traversedin its entirety (that is, including grandchildren, etc.) before looking at the next child.For binary trees, within the general category of depth-first traversals, there are three possible variants:Preorder: Look at a node before its children.;;;;; In file cs61a/lectures/2.2/print.scm(define (pre-order tree)(cond ((null? tree) ’())(else (print (entry tree))(pre-order (left-branch
View Full Document
Unlocking...