Page 1 of 1
tree matching algorithm
Posted: Fri Apr 16, 2004 10:18 am
by coolbila
I meet a tree matching problem.
Does any one know how to compare whether two trees are the same or not ?
Posted: Fri Apr 16, 2004 12:03 pm
by Cosmin.ro
You need to represent the trees as a sequence of paratnhesis, for example:
Code: Select all
1
/ | \ (()()())
2 3 4
1
|
2 ((()))
|
3
1
|
2 ((()()))
/ \
3 4
Basicly what you do is dfs and write a open parantesis when you go down a edge and a closed parantesis when you go up a edge.
Now you have to make the code cannonical, this means that for example the folowing two expressions ((())()) and (()(())) represent two isomorphic trees.
To get a connonical code for a tree you must first get the cannonical codes of the subtrees and sort them lexicographically and concatenate them and put at the beginning a open parantesis and at the end a closed parantesis. (in the example above (()) < () lexicographically so the canonical representation is ((())()).)
Now what I said applies to rooted trees, but if trees have no root and you have to check if they are isomorphic than you could fix a node in the first tree as the root of the first tree and try for the second tree every node as a root, or you can do it faster by knowing the fact that every tree has one or two centers and you first find the centers of the two trees and consider them roots and then get the cannonical code of the trees.
Posted: Fri Apr 16, 2004 3:48 pm
by coolbila
Thank you very much
This answer is very useful for me.
Posted: Thu Jul 29, 2004 9:30 am
by Pavl0
in what problem this algo can be used ??