[Haskell-cafe] pls help about subtree
lrpalmer at gmail.com
Mon Apr 28 17:59:28 EDT 2008
2008/4/28 cetin tozkoparan <cetintozkoparan at yahoo.com>:
> Assume a tree is a subtree of the other if all elements of the first tree
> is included in the second with the exact structure; all parent-child
> relations are preserved with their order.
> data Tree = Empty | Leaf Int | Node (Int,Tree,Tree)
Bit of a nitpick: Haskell folks would usually leave off the tuple on
the Node constructor, since constructors tuple for you already. So
Tree would become:
data Tree = Empty | Leaf Int | Node Int Tree Tree
But it's (almost) equivalent either way.
> subtree:: Tree -> Tree -> Bool
> How can i start to write this code with this data structure?
The way most tree algorithms are done is by recursion. Maybe it would
help if you saw the problem in a more explicit form:
A tree t is a subtree of a tree u if:
t = u, u is a Node and t is a subtree of the left child, or u is
a Node and t is a subtree of the right child.
That definition should roughly translate into an inefficient
implementation. There's probably a more efficient one somewhere, but
it's somewhere other than the top of my head.
More information about the Haskell-Cafe