You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('') and can be up to 35 characters long.
31 lines
1.5 KiB
31 lines
1.5 KiB
(load "displaylib.scm")


(title "Exercise 2.63")


(print "


Each of the following two procedures converts a binary tree to a list.




(define (tree>list1 tree)


(if (null? tree)


'()


(append (tree>list1 (leftbranch tree))


(cons (entry tree)


(tree>list1 (rightbranch tree))))))


(define (tree>list2 tree)


(define (copytolist tree resultlist)


(if (null? tree)


resultlist


(copytolist (leftbranch tree)


(cons (entry tree)


(copytolist (rightbranch tree)


resultlist)))))


(copytolist tree '()))




a. Do the two procedures produce the same result for every tree? If not, how do the results differ? What lists do the two procedures produce for the trees in figure 2.16?




b. Do the two procedures have the same order of growth in the number of steps required to convert a balanced tree with n elements to a list? If not, which one grows more slowly?


")




; a  Yes, they both return the tree in the right order


; more precisely ( 1 3 5 7 9 )




; b  the first method append at each step which is linear. Therefore for a balanced tree of n elements, we need to make n/2 steps to append to the rest. Therefore the number of steps is about nlog n


;  the second make only one operation for each element. Therefore, only n.


