|
|||||||||
|
|||||||||
| |||||||||
|
|||||||||
|
|||||||||
| |||||||||
|
|
|
| |||||||||
 |
|
|
«
Previous Thread
|
Next Thread
»
|
Thread Tools | Search this Thread | Rate Thread | Display Modes |
Dev Shed Forums Sponsor:
|
|
|
|
#1
July 3rd, 2003, 11:50 AM
|
||||
|
||||
|
Algorithm to compare two trees
Hello all,
does anyone know a algorithm to compare two trees? I heard something about the Levenshtein algorithm but I can't find anything about it. Can someone help me?
|
|
#3
July 4th, 2003, 02:46 PM
|
|||
|
|||
|
Itīs probably not the most effective way, but you could recursively traverse both trees and compare the value of each single node (assuming they are trees that can be read completely recursively). As soon as one differs, stop and return false.
More details, plz?
__________________
-- Manuel Hirsch - Linux, FreeBSD, programming, administration articles, tutorials and more.
|
|
#4
July 4th, 2003, 06:31 PM
|
||||
|
||||
|
I want to compare two xml files (tree structure).
The problem is that the one tree don't need to have the same structure like the other. The structure can differ in some cases. The rusult of the comparison should be a information about: which nodes of the to trees are equal and at the same position in the trees which nodes are equal but at different positions which nodes are just in the one file and which nodes are just in the other file The node should be compared by the vlalues of their attributes I've no idea how to realize this :-(
|
|
#5
July 5th, 2003, 02:18 AM
|
||||
|
||||
|
Hmm i have no idea.. but pseudocode for checking structure of two trees such as a binary tree would be as follows
Code:
checksame(tree1,tree2)
if(t1 is empty AND t2 is empty)
return true
if(t1 is empty OR t2 is empty)
return false
return true AND checksame(t1.right,t2.left) AND checksame(t2.left,t2.right)
|
|
| Viewing: Dev Shed Forums > Programming Languages - More > Software Design > Algorithm to compare two trees |
| Thread Tools | Search this Thread |
| Display Modes | Rate This Thread |
|
|
 |
|
|
Del.icio.us
Digg
Google
Spurl
Blink
Furl
Simpy
Y! MyWeb
Linear Mode
