Algorithm to compare two trees

Dev Shed Forums Sponsor:

July 3rd, 2003, 10:50 AM

Wizard2003

Contributing User

Join Date: Jul 2003

Posts: 206

Time spent in forums: 19 h 29 m 24 sec
Reputation Power: 10

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?

July 4th, 2003, 01:49 AM

majesty

Junior Member

Join Date: Jul 2003

Posts: 3

Time spent in forums: < 1 sec
Reputation Power: 0

Depends what sort of tree you're referring to

And what exactly do u wanna compare?

July 4th, 2003, 01:46 PM

M.Hirsch

Contributing User

Dev Shed God 1st Plane (5500 - 5999 posts)

Join Date: Oct 2000

Location: Back in the real world.

Posts: 5,966

Time spent in forums: 1 Month 2 Days 52 m 24 sec
Reputation Power: 189

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.

July 4th, 2003, 05:31 PM

Wizard2003

Contributing User

Join Date: Jul 2003

Posts: 206

Time spent in forums: 19 h 29 m 24 sec
Reputation Power: 10

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 :-(

July 5th, 2003, 01:18 AM

majesty

Junior Member

Join Date: Jul 2003

Posts: 3

Time spent in forums: < 1 sec
Reputation Power: 0

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

« Previous Thread | Next Thread »

Developer Shed Advertisers and Affiliates

Thread Tools	Search this Thread
Email this Page	Search this Thread: Advanced Search
Display Modes	Rate This Thread
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode	Rate This Thread:

Posting Rules
You may not post new threads You may not post replies You may not post attachments You may not edit your posts vB code is On Smilies are On [IMG] code is On HTML code is Off

View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox

Forum Jump