X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=assignment10.mdwn;h=8e5bf2da11c1c5af46b6cfbcb81962865e65a95f;hp=d7e0e235f23cfc93de7d77fa366ccacb57366127;hb=78c9730055042764247f961889f380cbe8ab5f42;hpb=372c2fd214b65657211aa550fc1dccfb6e3cbfda diff --git a/assignment10.mdwn b/assignment10.mdwn index d7e0e235..8e5bf2da 100644 --- a/assignment10.mdwn +++ b/assignment10.mdwn @@ -39,15 +39,16 @@ Of course, if you need help or want us to review your efforts, we'll be glad to 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: