Fuzzy matching a tree structure

I'm looking for a good way to do fuzzy matching of a tree against a family of trees.

I know how to look for an exact match between two trees. Just do simultaneous traversals down both of them and see if they're the same.

Now, I would like to (1) quickly match against multiple trees, perhaps on the order of thousands of trees; and (2) do a fuzzy match (for example, severals leaf nodes may be mismatched, but that's ok).

For an exact match against multiple trees, I could hash each tree. But the fuzzy match against multiple trees seems difficult. Any ideas?

>>5
increment a counter for each node that matches at least one of the leaves, and sort by score.
Yeah, and this is obviously an extremely complex algorithm that will be able to match very well right? Jesus christ.