마지막 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!!!
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), …)
t2 = Pair(Leaf(19), …)
same_leaves should be able to return false without looking at the right subtrees.