#1
  1. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Posts
    206
    Rep Power
    11

    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?
  2. #2
  3. Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Posts
    3
    Rep Power
    0
    Depends what sort of tree you're referring to
    And what exactly do u wanna compare?
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Oct 2000
    Location
    Back in the real world.
    Posts
    5,966
    Rep Power
    190
    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?
  6. #4
  7. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Posts
    206
    Rep Power
    11
    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 :-(
  8. #5
  9. Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Posts
    3
    Rep 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)

IMN logo majestic logo threadwatch logo seochat tools logo