CS2360 Summer 1998 Homework Assignment 3 Due no later than 8:00 a.m., Tuesday, July 21, 1998 Read and follow all instructions for the individual problems below. As for predefined functions, use only the following: <, >, =, +, null, cond, list, cons, append, rest, first, mapcar, apply, funcall, defun, quote, function. If there are any functions that you need that are not listed above, you MUST write your own versions (DO NOT USE any predefined functions not listed above). The first set of questions all refer to BINARY TREEs. A binary tree is another example of an abstract datatype. For our purposes, all we need to know right now about them are they consist of a node (the root) and a left and right subtree (see, two subtrees == binary). So, 12 / \ / \ 10 16 /\ / \ 1 11 is a binary tree. Notice that the definition can be applied recursively. Each subtree of the binary tree is also a binary tree. In particular, we are going to be interested in binary _search_ trees. In a binary search tree, all the elements in the left subtree are less than the root; all the elements in the right one are greater than the root (The above was a binary search tree). How is this going to be represented in a LISP data structure? Consider the simplest BST, a single node. 3 It has no children. You can store this as a list triplet, where the head of the list is the node, the second thing in the list is the left subtree and the third thing is the right subtree. But, you say, this BST doesn't have any subtrees. So, we'll store nil to let us know that. The above tree, then, looks like this as a LISP data structure (3 nil nil) Looking at the original tree, the 10 and its children can be represented as: (10 (1 nil nil) (11 nil nil)) The 16 is just (16 nil nil) And, the entire tree can be represented as (12 (10 (1 nil nil) (11 nil nil)) (16 nil nil)) NIL is a valid BST and represents the empty tree. PLEASE NOTE THAT FOR ALL FUNCTIONS DEALING WITH TREES, IT IS ASSUMED THAT THERE ARE NO DUPLICATE VALUES IN THE TREE. EACH NODE CONTAINS A UNIQUE VALUE TO THE TREE. One small hint: Be sure to use good abstraction for these problems. It will help... a lot. And now onto the first set of questions: #1) Write a LISP function called ADD-TO-TREE that, given a number and a BST, adds the number to the correct place in the tree. For example: > (ADD-TO-TREE 3 '(2 (1 NIL NIL) NIL))) (2 (1 NIL NIL) (3 NIL NIL)) In the nice, pretty picture format this would be: input: '3 2 output: 2 / \ / \ 1 NIL / \ / \ 1 3 NIL NIL / \ / \ NIL NIL NIL NIL Or how about: > (ADD-TO-TREE 10 '(16 (8 (4 NIL NIL) NIL) (20 NIL (25 NIL NIL)))) (16 (8 (4 NIL NIL) (10 NIL NIL)) (20 NIL (25 NIL NIL)))) #2) Write a LISP function called MAKE-TREE which takes in a list of numbers and returns a lists of lists which represents a BST. For example: > (MAKE-TREE '(50)) (50 NIL NIL) A slightly more complex example is: > (MAKE-TREE '(50 3 10)) (50 (3 NIL (10 NIL NIL)) NIL) 50 / \ 3 NIL / \ NIL 10 / \ NIL NIL #3) Now write a function called GET-HEIGHT which takes in a binary tree. This function will return the height of the tree. > (get-height '()) 0 > (get-height '(10 nil nil)) 1 > (get-height '(10 (3 (1 nil nil) (5 (4 nil nil) nil)) (13 nil (15 nil nil)))) 4 #4) We've spent some time building things up, so now let's have some fun taking things down. This time, you're going to write a function DELETE-FROM-TREE, which will take in a target number and a BST, and delete that node from the tree. For this function, you will be using the Left-Right rule for deleting nodes from trees. You start at the node which you want to delete and visit it's left child. You then proceed to traverse down the right from that point as far as you can. Once you hit a node who's right subtree is NIL, you have found your replacement value. You then need to re-arrange your tree to place that replacement value in the place of the value you want to delete. Be sure to handle any data that might be to the left of the replacement value. Before: 12 <---value we're deleting / \ / \ / \ 9 15 / \ / \ / \ NIL NIL 3 11 <--- our replacement value / \ / \ NIL NIL 10 NIL / \ NIL NIL After: 11 <---new value / \ / \ / \ 9 15 / \ / \ / \ NIL NIL 3 10 <--- the old left subtree / \ / \ NIL NIL NIL NIL If the node you want to delete does not have any values to its left, just move the right subtree up to its position. Examples: > (DELETE-FROM-TREE 3 NIL) NIL > (DELETE-FROM-TREE 3 '(3 NIL NIL)) NIL > (DELETE-FROM-TREE 5 '(5 (3 NIL NIL) NIL)) (3 NIL NIL) > (DELETE-FROM-TREE 8 '(8 (5 NIL (6 NIL NIL)) (10 NIL NIL))) (6 (5 NIL NIL) (10 NIL NIL)) > (DELETE-FROM-TREE 9 '(12 (9 (5 NIL (8 NIL NIL)) (11 (10 NIL NIL) nil)) (15 NIL NIL))) (12 (8 (5 NIL NIL) (11 (10 NIL NIL) NIL)) (15 NIL NIL)) #5) We've had some fun creating and deleting from our trees, now lets handle some good old-fashioned traversal. You will now write 3 traversals: > (TRAVERSE-TREE-INORDER '(3 (1 NIL NIL) (4 NIL NIL))) (1 3 4) > (TRAVERSE-TREE-PREORDER '(3 (1 NIL NIL) (4 NIL NIL))) (3 1 4) > (TRAVERSE-TREE-POSTORDER '(3 (1 NIL NIL) (4 NIL NIL))) (1 4 3) Each of these will take in a tree and return a list of all the elements in that particular order. Note: Preorder means to consider the root, then the left subtree, then the right. Inorder means to consider the left subtree, then the root, then the right subtree. Postorder means to consider the left subtree, then the right, then the root. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - #6) Use applicative programming to write a function called SHUFFLE, which takes two lists of equal length as input and interleaves or shuffles the elements of those two lists to produce a single list which is returned (like shuffling two halves of a deck of cards one time). For example: ? (shuffle '(1 2 3) '(4 5 6)) (1 4 2 5 3 6) ? (shuffle nil nil) NIL ? (shuffle '(a b c d e) '(a b c d e)) (A A B B C C D D E E)