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?

Serialize the trees and then use some form of string matching on them. If you really wanted to be an obnoxious OPTIMIZATION faggot, even when the bottle neck in this scenario will be absolutely nowhere near serializing the tree; then you could avoid serializing and just somewhat modify/reimplement other fuzzy algorithms to work on the fly across your tree. If you actually wanted extremely advanced matching; like perhaps a tree and its post-order equivalent to be considered nearly identical then you would probably need to come up with your own algorithm; and be a Ph.D student with extensive experience in the related field.

See: http://en.wikipedia.org/wiki/Fuzzy_string_searching