solution that traverses the tree exactly once, replacing each
leaf as soon as you see it?
- Consider a variation in which you must replace each leaf with
- its number of occurrences in the tree. Is there any way to do
- that with a single traversal?
-
You can assume that the tree is binary, leaf-labeled (no
labels on the internal nodes), and that the leafs are, say,
chars.
- Here is [a hint](/hints/assignment_10_hint).
+ Here is [a hint](/hints/assignment_10_hint_1).
+
+ Consider a variation in which you must replace each leaf with
+ its number of occurrences in the tree. Is there any way to do
+ that with a single traversal? (Here is [a hint](/hints/assignment_10_hint_2).)
+
2. Armed with your solution to problem 1, try this: you have as input a leaf-labeled, binary tree whose labels are strings. You also have as input an interpretation function from strings to meanings. Let the meanings of your strings be primitive elements, for instance:
((eq? (car lst) before)
(insert-co new before after (cdr lst) (lambda (new-lst lefts rights) (k (cons new (cons before new-lst)) (succ lefts) rights))))
((eq? (car lst) after)
- (insert-co new before after (cdr lst) (lambda (new-lst lefts rights) (k (cons (after (cons new new-lst))) lefts (succ rights)))))
+ (insert-co new before after (cdr lst) (lambda (new-lst lefts rights) (k (cons after (cons new new-lst)) lefts (succ rights)))))
(else
(insert-co new before after (cdr lst) (lambda (new-lst lefts rights) (k (cons (car lst) new-lst) lefts rights)))))))
-->