I passed the question on tree metrics over to GRAPHNET, and here are
two replies:
Sender: GRAPHNET - Graph Theory <GRAPHNET at VM1.NoDak.EDU>
From: "Michael J. Hennebry" <hennebry at plains.NoDak.edu>
Subject: Re: Metric on the space of trees?
Here is one for rooted ordered n-ary trees:
The number of nodes which occur in one tree, but whose corresponding nodes
do not occur in the other.
The distance between an empty tree and another would be the number of nodes
in the other.
The distance between two non-empty trees would be the sum of the distances
between corresponding sub-trees.
Computing a similar metric for rootless or unordered trees might
fall prey to super-polynomial complexity while trying to decide the
best alignment of the trees.
From: Paul Kainen <kainen at CS.UMD.EDU>
Subject: Re: Metric on the space of trees?
Your question is a natural one, and I recall hearing it previously
(perhaps at a Gordon Conference). If you restrict the question to
binary trees with a fixed root and with n given "leaves" (non-root
vertices with degree 1), then I am pretty sure that the minimum
number of "associations" defines a metric between two such trees.
By an association I mean the operation which replaces the tree that
represents a(bc) by the tree that represents (ab)c. Each of these
is a rooted binary tree with 3 leaves. Now more complicated trees
can be transformed by finding a subtree of either of the above two
types and replacing it with the other one. Just as theorems about
associative properties can be proved first for the case of three
and then extended by induction, I am sure that the same argument
applies to give a metric. Since phylogenetic trees would usually
be modeled as rooted binary trees, this would do as a metric for
those trees with the same number of vertices.