아, SML 어렵다. – So difficult!!!

마지막 SML 숙제. 도대체 어떻게 하라는 건지 감이 안 잡힌다.

기대도 안 하지만 혹시 아시면 댓글 부탁. ㄳ

The last SML assignment…. I don’t know how to do that.

I don’t expect but if there is somebody who knows it, tell me!!!

Consider the following tree datatype:

datatype tree = Empty | Leaf of int | Pair of tree * tree

If you have implemented an inorder traversal for a tree datatype, it is of course very easy to determine whether two trees have the same inorder traversal: Simply evaluate inorder t1 = inorder t2

However, this will be wasteful if the two trees differs in the first leaf. In that case, all leaves of both trees will have to be examined, even though we could tell from looking at the first two leaves that the two trees would have different traversals.

Your task is to write a function

same_leaves tree*tree -> bool

that returns true if the two trees have the same inorder traversal, and false if they don’t. The function should examine the leaves in the two trees, from left to right (as usual).

However, the function should not traverse more of the trees than is necessary to determine the answer.

For example, if these two trees are compared:

t1 = Pair(Leaf(17), …)

and

t2 = Pair(Leaf(19), …)

same_leaves should be able to return false without looking at the right subtrees.

5 thoughts on “아, SML 어렵다. – So difficult!!!”

Leave a Reply

Your email address will not be published. Required fields are marked *