CSE1729 – Introduction to Programming
March 22, 2020
Problem Set 7
Recall the conventions we have adopted in class for maintaining trees. We represent the empty tree with the empty list (); a nonempty tree is represented as a list of three objects
(value left-subtree right-subtree)
where value is the value stored at the root of the tree, and left-subtree and right-subtree are the two subtrees. We introduced some standardized functions for maintaining and accessing this structure, which we encourage you to use in your solutions below.
1. SICP Exercise 2.31. Define a SCHEME procedure, named tree-map, which takes two parameters, a tree, T, and a function, f, and is analogous to the map function for lists. Namely, it returns a new tree T′ with a topology identical to that of T but where each node n ∈ T ′ contains the image under f of the value stored in the corresponding node in T. For instance, if the input tree is shown in Example 1 and the function f is
f (x) = x2. then the tree returned by tree-map is shown in Example 2. 24
13 19
Figure 1: T, the tree passed to tree-map Figure 2: T ′ , the tree returned by tree-map when passed T and the squaring function as parameters.
2. Define a SCHEME procedure, named tree-equal?, which takes two trees as parameters and returns #t if the trees are identical (same values in the same places with exactly the same structure) and #f otherwise. Use the SCHEME eq? function to test equality for the values of the nodes.
3. Define a SCHEME procedure, named (tree-sort l), which takes a list of numbers and outputs the same list, but in sorted order. Your procedure should sort the list by
(a) inserting the numbers into a binary search tree and, then,
(b) extracting from the binary search tree a list of the elements in sorted order.
To get started, write a procedure called (insert-list L T) which takes a list of numbers L and a binary search tree T , and returns the tree that results by inserting all numbers from L into T . (Place the argument L first, so a call to your function should have the form (insert-list L T), where L is a list and T is a (perhaps empty) binary search tree.)
Then write a function called sort-extract which takes a binary search tree and outputs the elements of the tree in sorted order. (We did this in class!)
Finally, put these two functions together to achieve (tree-sort l). (Note, all three of these functions will be graded, so your solutions must consist of three top-level functions, insert-list, sort-extract, and tree-sort.)
(define (make-tree value left right) (list value left right))
(define (value tree) (car tree))
(define (left tree) (cadr tree))
(define (right tree) (caddr tree))
1
4. DefineaSCHEMEprocedure,named(delete-value T v),thattakesabinarysearchtree,T,andavalue, v, as arguments and returns the binary search tree that results from removing the node containing the value v. (The tree T should be the first argument.) You may assume that the tree contains no more than one node with value v, but your procedure should be well-behaved if called with a tree T that does not contain the value v: in this case, it should return the tree unchanged. Note that the tree your function returns must maintain the binary search tree property. Removing interior (that is, non-leaf) nodes requires a little care. (See Example 3 for an example.) Details are given below.
Deleting nodes from trees The delete-value function must remove the one occurrence of v from the input binary search tree T . Naturally, if T has n nodes, the output tree T ′ has n − 1 nodes; note that T ′ must satisfy the binary search tree property (for every node w, the nodes in the left sub-tree of w hold values smaller than the value held in w and the nodes in the right-subtree of w hold values larger than the value held in w). There are number of cases that need to be handled separately: the node n may have no sub-trees, exactly one subtree, or two subtrees. (See Example 5.) The first two situations can be handled easily; just remove the node and “replace” it with its single subtree. The third case, illustrated below in Example 4, requires that you restructure the tree a bit to reattach the two “orphaned” subtrees of n in an appropriate way. There are two natural choices: either replace the value at the deleted node with the largest value in the left subtree or the smallest value in the right subtree while removing the corresponding leaf node. In your implementation, please adopt the first of these conventions: specifically, in order to remove a node n with two subtrees, replace the value of n with the largest value in the left subtree, and then remove this value from the left subtree. (See the example below.)
55 211 29
1 3 8 15 1 3 8 15 6917 617
Example 3: An example of a binary search Example 4: The same binary search tree after
tree.
the removal of the value 11. Note, we chose to promote the largest value in the left subtree (9) to the node vacated by the value 11.
2222 1313
Example 5: Three possibilities when finding a node to remove. (The middle two cases are treated as one.)
5. This problem concerns ways to represent arithmetic expressions using trees. For this purpose, we will consider 4 arithmetic operations: + and ∗, both of which take two arguments, and − and 1/, both of which take one argument. (As an example of how these one-argument operators work, the result of applying the operator − to the number 5 is the number −5; likewise, the result of applying the 1/ operator to the number 5 is the number 1/5.)
2
An arithmetic parse tree is a special tree in which every node has zero, one, or two children and:
• each leaf contains a numeric value, and
• every internal node with exactly two children contains one of the two arithmetic operators + or ∗, • every internal node with exactly one child contains one of the two arithmetic operators − or 1/.
(You may assume, for this problem and the next, that when a node has a single child, this child appears as the left subtree.)
If T is an arithmetic parse tree, we associate a value with T (which we call value(T)) by the following recursive rule:
• if T has a single (leaf) node, value(T) is equal to the numeric value of the node,
• if T has two subtrees L and R, and its root is the operator +, then value(T) = value(L) + value(R), • if T has two subtrees L and R, and its root is the operator ∗, then value(T) = value(L) ∗ value(R), • if T has one subtree, S, and its root is the operator −, then value(T ) = − value(S),
• if T has one subtree, S, and its root is the operator 1/, then value(T ) = 1/ value(S).
You can see how to associate with any arithmetic expression a natural arithmetic parse tree. Note that since − and 1/ are unary operators (take only one argument), you have to give a little thought to how to represent expressions such as 3 − 5 or 3/5. For example, the arithmetic parse tree for the expression
is shown in Example 6.
2×3+4−5 6
+
××
2 3 + 1/
4−6 5
Example 6: An arithmetic parse tree for the expression 2 × 3 + (4 + (−5)) × (1/6).
Write a SCHEME function (arithvalue T) which, given an arithmetic parse tree T, computes the value associated with the tree. You may assume that the operators +, ×, −, and 1/ appear in the tree as the characters #\+, #\*, #\-, and #\/. (See the comments at the end of the problem set concerning the SCHEME character type.) To test your code, try it out on the parse tree
(define example (list #\+ (list # *
(list 4 ‘() ‘())
(list 5 ‘() ‘())) (list #\+
(list #\/ (list 6 ‘() ‘()) ‘()) (list 7 ‘() ‘()))))
\
3
Strings and characters in SCHEME SCHEME has the facility to work with strings and characters (a string is just a sequence of characters). In particular, SCHEME treats characters as atomic objects that evaluate to themselves. They are denoted: #\a, #\b, . . . . Thus, for example,
> #\a
#\a
> #\A
#\A
> (eq? #\A #\a)
#f
> (eq? #\a #\a)
#t
The “space” character is denoted #\space. A “newline” (or carriage return) is denoted #\newline.
A string in SCHEME is a sequence of characters, but the exact relationship between strings and characters re- quires an explanation. A string is denoted, for example, “Hello!”. You can build a string from characters by using the string command as shown below. An alternate method is to use the list->string com- mand, which constructs a string from a list of characters, also modeled below. Likewise, you can “explode” a string into a list of characters by the command string->list:
> (string #\S #\c #\h #\e #\m #\e)
“Scheme”
> (list->string ‘(#\S #\c #\h #\e #\m #\e)) “Scheme”
> (string->list “Scheme”)
(#\S #\c #\h #\e #\m #\e)
> “Scheme”
“Scheme”
Finally, given two strings, you can append them together using the string-append function (alternatively, you could turn them in to lists, append those, and convert back):
Note that strings, like characters, numbers, and Boolean values, evaluate to themselves.
> (string-append “book” “worm”)
“bookworm”
> (list->string (append (string->list “book”) (string->list “worm”)))
“bookworm”
4