#lang racket (require csc151) (require csc151/binary-trees-from-lists) (require racket/match) (require racket/undefined) (require rackunit) ;; CSC-151-01 (Fall 2021) ;; Lab: Binary Trees ;; https://rebelsky.cs.grinnell.edu/Courses/CSC151/2021SpT2/labs/binary-trees ;; Authors: YOUR NAMES HERE ;; Date: THE DATE HERE ;; Acknowledgements: ;; ACKNOWLEDGEMENTS HERE ; +---------------------------------------+-------------------------- ; | Provided code: The hideous shorthands | ; +---------------------------------------+ (define bt/tl (o bt/t bt/l)) (define bt/ll (o bt/l bt/l)) (define bt/rl (o bt/r bt/l)) (define bt/tr (o bt/t bt/r)) (define bt/lr (o bt/l bt/r)) (define bt/rr (o bt/r bt/r)) (define bt/tll (o bt/tl bt/l)) (define bt/lll (o bt/ll bt/l)) (define bt/rll (o bt/rl bt/l)) (define bt/trl (o bt/tr bt/l)) (define bt/lrl (o bt/lr bt/l)) (define bt/rrl (o bt/rr bt/l)) (define bt/tlr (o bt/tl bt/r)) (define bt/llr (o bt/ll bt/r)) (define bt/rlr (o bt/rl bt/r)) (define bt/trr (o bt/tr bt/r)) (define bt/lrr (o bt/lr bt/r)) (define bt/rrr (o bt/rr bt/r)) ; +---------------------------------+-------------------------------- ; | Provided code: Displaying trees | ; +---------------------------------+ ;;; (display-binary-tree t) -> void? ;;; t : tree? ;;; Prints tree t to the console in a well-formatted manner. (define display-binary-tree (lambda (t) (let* (; The different levels of bullets [bullets (vector "* " "+ " "- " ". ")] ; The index of the last bullet [last-bullet (- (vector-length bullets) 1)] ; Choose the appropriate bullet for a level. [bullet (lambda (level) (vector-ref bullets (min level last-bullet)))]) (letrec (; Display a binary tree at the appropriate indentation [helper (lambda (t indent) (when (not (empty-tree? t)) (display (make-string (* indent 2) #\space)) (display (bullet indent)) (display (bt/t t)) (newline) (helper (bt/l t) (+ indent 1)) (helper (bt/r t) (+ indent 1))))]) (helper t 0))))) ; +----------------------------------------------+------------------- ; | Provided code: The legendary management tree | ; +----------------------------------------------+ (define management-tree (binary-tree "Board" (empty-tree) (binary-tree "CEO" (binary-tree "Head of Engineering" (leaf "Software Developer") (leaf "Tester")) (binary-tree "Head of Legal" (empty-tree) (leaf "Lawyer"))))) ; +-----------+------------------------------------------------------ ; | Exercises | ; +-----------+ #| AB |# ; +-------------------------+---------------------------------------- ; | Exercise 0: Preparation | ; +-------------------------+ #| a. Conduct the normal start-of-lab discussion. b. In the space below, describe the normal "start of lab" steps and summarize what you answered for each. [TODO: ENTER YOUR ANSWER HERE] c. Discuss your answers to the self checks. d. Review the code at https://github.com/grinnell-cs/csc151/blob/main/binary-trees-from-lists.rkt You may want to keep that code at hand as you progress through the lab. e. Make sure that you've updated to the latest version of the `csc151` package. |# #| A |# ; +--------------------------+--------------------------------------- ; | Exercise 1: Making trees | ; +--------------------------+ #| a. Consider the following trees of numbers drawn with ASCII art: i. tree-i "b" / \ / \ "a" "c" ii. tree-ii 5 / \ 2 7 / \ \ 1 4 9 / 8 iii. tree-iii 5 / 4 / 3 / 2 / 1 / 0 For each of these trees, use the tree-making functions from the reading to complete the definitions of `tree-i`, `tree-ii`, and `tree-iii` below. Make sure to check that each thing you enter is a binary tree with `binary-tree?` and that it has the right form with `display-binary-tree` > (binary-tree? tree-i) > (display-binary-tree tree-i) > (binary-tree? tree-ii) > (display-binary-tree tree-ii) > (binary-tree? tree-iii) > (display-binary-tree tree-ii) |# (define tree-i undefined) (define tree-ii undefined) (define tree-iii undefined) #| b. Note that tree-iii is a left-leaning tree. That is, all its children are left children. Complete the definition of tree-iv below which is the same as tree-iii except that its leaves grow to the right rather than the left. 5 \ 4 \ 3 \ 2 \ 1 \ 0 |# (define tree-iv undefined) #| c. Finally, in the space below describe in a few sentences the differences and simliarities between tree-iii and tree-iv. Do you consider these trees to be the same tree or different trees? Why? |# ; +--------------------+--------------------------------------------- ; | Exercise 2: Leaves | ; +--------------------+ #| a. As you've seen in the code above, we've used `(leaf val)` to replace the much more verbose `(leaf val (empty-tree) (empty-tree))`. Write your own version of `leaf`. |# (define make-leaf undefined) #| b. As you know, a leaf is a binary tree node with an empty left subtree and an empty right subtree. Write a `(is-leaf? tree)` procedure as described below. |# ;;; (is-leaf? tree) -> boolean? ;;; tree : binary-tree? ;;; Returns #t is tree is a leaf and #f otherwise. (define is-leaf? undefined) #| c. You may have noticed that `leaf` and `leaf?` do not appear in the `binary-trees-as-lists.rkt` file. That's because they are in a separate code file, one that is included in `binary-trees-as-lists.rkt`. Look at the start of the included file, which is available at https://github.com/grinnell-cs/csc151/blob/main/includes/binary-trees-common.inc How do your definitions of `make-leaf` and `is-leaf?` differ from the ones in that file? [TODO: Enter your answer here.] |# #| B |# ; +-------------------------+---------------------------------------- ; | Exercise 3: Unary nodes | ; +-------------------------+ #| As you've seen in the creation of the management tree and the individual trees you've made above, although binary tree nodes always have two children, we might set one child to the empty tree to indicate "it really only has one child". |# #| a. Write a procedure `(unary-bt-node/left val left)` that creates a node with the value `val`, left subtree `left`, and an empty right subtree. |# (define unary-bt-node/left undefined) #| b. Write a procedure `(unary-bt-node/right val right)` that creates a node with the value `val`, an empty left subtree, and a right subtree of `right. |# #| c. Rewrite `tree-i` through `tree-iv` using these new procedures. |# (define tree-i/new undefined) (define tree-ii/new undefined) (define tree-iii/new undefined) (define tree-iv/new undefined) ; +------------------------------+----------------------------------- ; | Exercise 4: Traversing trees | ; +------------------------------+ #| You may have observed a few things about the binary tree procedures we call "the hideous shorthands". Here are some things we think (other than that they are somewha hideous). * They are hard to read. * There are a lot of them. * They feel a bit "backwards". That is, the first thing you do is the last letter in the thing, rather than the first. For example, `bt/trll` means "go left, go left, go right, take the top element". Or at least it would if it were defined. We can't necessarily solve the first problem, but we can probably solve the others. |# #| a. Finish the definition of the procedure, `(traverse path tree)` that takes a string of r's and l's as its first parameter and a tree as its second parameter, and returns the portion of the tree specified by that string in left-to-right order. For example, `(bt "llrl" tree)` means "go left, then left, then right, then left". We're not going to worry about the top element for now. |# ;;; (traverse path tree) -> binary-tree? ;;; path : string? (contains only r's and l's) ;;; bree : binary-tree? ;;; Follow the path given by the path and return the described ;;; value. (define traverse (lambda (path tree) (cond [(equal? path "") tree] [(empty-tree? tree) (error "You've run off the end of the tree")] [(char=? #\l (string-ref path 0)) (traverse undefined ; You need to figure out this parameter. (binary-tree-left tree))] [(char=? #\r (string-ref path 0)) undefined] ; You need to figure out this recursive call. [else (error "Invalid subpath" path)]))) #| b. Try a few examples of `traverse` with the management tree and/or some of the trees you defined earlier. |# #| A |# ; +--------------------------------------+--------------------------- ; | Exercise 5: Changing representations | ; +--------------------------------------+ #| The wonder of data abstraction suggests that because we're using the tree procedures, rather than the underlying structural procedures (e.g., `cons` and `car`), we can change our underlying representation of trees. In this exercise, we attempt to do so. |# #| a. What do you expect the following to produce? (It's okay if you don't give exact Racket output.) > (define sample (binary-tree "a" (unary-bt-node/left "b" (make-leaf "c")) (unary-bt-node/left "d" (binary-tree "e" (make-leaf "f") (make-leaf "g"))))) > (binary-tree? sample) ? > sample ? > (display-binary-tree sample) ? > (traverse "rlr" sample) ? |# #| b. Check your answers expermentally. > (binary-tree? sample) ? > sample ? > (display-binary-tree sample) ? > (traverse "rlr" sample) ? |# #| c. Replace the `(require binary-trees-from-lists)` line at the start of this file with `(require binary-trees-from-structs)`. Do you expect to get the same or different answers for each of the above? > (binary-tree? sample) [SAME or DIFFERENT:How] > sample [SAME or DIFFERENT:How] > (display-binary-tree sample) [SAME or DIFFERENT:How] > (traverse "rlr" sample) [SAME or DIFFERENT:How] |# #| d. Check your answer experimentally. > (binary-tree? sample) ? > sample ? > (display-binary-tree sample) ? > (traverse "rlr" sample) ? |# #| e. If all has gone well, the only difference you will see is how the binary tree is represented when we ask Racket to print it by giving its name. |# #| B |# ; +--------------------------------------------+--------------------- ; | Exercise 6: Changing representations again | ; +--------------------------------------------+ #| Suppose we are switching from lists or structs to vectors. Check off the procedures or values you would expect to have to update if we decided to change our representation of non-empty binary trees from three-element lists or three-element structs to three-element vectors, using a zero-element vector as the empty tree. Tree constructors [ ] `empty-tree` [ ] `binary-tree` [ ] `leaf` [ ] `unary-tree/left` [ ] `unary-tree/right` Tree checkers [ ] `empty-tree?` [ ] `binary-tree?` [ ] `leaf?` Tree traversers [ ] `binary-tree-top` [ ] `binary-tree-left` [ ] `binary-tree-right` [ ] `traverse` Other [ ] `display-binary-tree` [ ] `management-tree (and tree-i through tree-iv)` [ ] |# #| AB |# ; +---------------------------+-------------------------------------- ; | For those with extra time | ; +---------------------------+ #| If you find that you have extra time, you should go through the following exercises in order. We will return to some of the issues raised by these exercises in the next class. |# ; +---------------------------+-------------------------------------- ; | Extra 1: Changing bullets | ; +---------------------------+ #| You may have noticed that the `display-binary-tree` procedure has a helper procedure, `bullet`, that selects an appropriate bullet. Here's a tree with more than four levels. |# (define taller-tree (binary-tree "a" (binary-tree "b" (binary-tree "c" (binary-tree "d" (binary-tree "e" (leaf "f") (leaf "g")) (leaf "h")) (leaf "i")) (leaf "j")) (leaf "k"))) #| a. What bullet do you expect to get if your tree has more than four levels, as in the case of `taller-tree`? Check your answer experimentally. |# #| b. In your own words, explain how `bullet` works. |# #| c. As you might guess, you can change the bullets by changing the value of `bullets`. Create a new version of `bullets` with at least five bullets, using the Unicode bullets, which you can find on Wikipedia. https://en.wikipedia.org/wiki/Bullet_(typography) For example, you can get the triangular bullet with "\u2023 ". |# #| d. In your own words, explain how `display-binary-tree` seems to work. |# ; +------------------------------------+----------------------------- ; | Extra 2 : Exploring tree recursion | ; +------------------------------------+ #| From the reading, we noted that a binary tree is recursively defined like a list. A binary tree is either: + *Empty*, or + *Non-empty* where the tree contains a valueand up to two *children* (*subtrees*) that are, themselves, trees. Like lists, our tree operations mirror this recursive decomposition of the list. As a first example, consider the following function which computes the *size* of the input tree, *i.e.*, the number of values it contains. |# ;;; (binary-tree-size tree) -> integer? ;;; tree : binary-tree? ;;; Determine how many values are in binary tree tree. (define binary-tree-size (lambda (t) (if (empty-tree? t) 0 (+ 1 (binary-tree-size (binary-tree-left t)) (binary-tree-size (binary-tree-right t)))))) #| a. For reference, copy and paste your definitions from tree-i and tree-ii from a previous problem within this comment below: (define tree-i undefined) (define tree-ii undefined) Now, use your mental model of computation to give an evaluation trace of the following expression in the space below: For this derivations, you can evaluate the `cond` expression directly to the branch it evaluates to, immediately evaluate the results of the `car` and `cdr` calls, to the sub-trees they evaluate to, as well as elide the contents of the tree's children during evaluation. You can write the trees as lists or vectors, depending on which is easier for you to think about. (binary-tree-size tree-i) --> (binary-tree-size ...) |# #| b. Do the same for tree-ii (binary-tree-size tree-ii) --> |# #| c. Fill out the following high-level description of `tree-size` in terms of the base and recursive cases of the function above. > The size of a tree is: > * ... in the base case > * ... in the recursive case |# ; +-------------------------------------+---------------------------- ; | Extra 3: Patterns of tree recursion | ; +-------------------------------------+ #| You've now seen or written four procedures that recurse over binary trees: * `binary-tree?`, which checks if something is a binary tree. * `display-binary-tree`, which prints out a binary tree * `traverse`, which traverses a binary tree * `binary-tree-size`, which finds the number of values in the tree Each uses a slightly different form of recursion. As you've likely figured out, it's helpful to generalize the patterns of recursion we see. For example, we've realized that most list recursion stops with null lists or one element lists (that's our base-case test) and that most list recursion requires us to take the cdr of the list. |# #| a. Let's do the same here. `binary-tree-size` uses one of the more common forms of tree recursion, so we'll focus on that. Using `binary-tree-size` as a starting point, sketch a form of recursion over trees. Make sure to make it clear what the base case test is and what the recursive case looks like.> |# #| b. How is binary tree recursion similar to and dissimilar from list recursion? |#