Euler tour order

Hi,

I have a few questions on euler tour order with trees - I'll just lay them out here:

    1) Can a euler tour order work on non-binary trees?
    2) Given the following tree, is this how a 'tour' of the tree should look:

             A
          /      \
        B        C
      /   \
   50   100

    Visit history output:
    A    B   50   B   100   B   A   C

Alright, to answer my own questions:

    1) I think it works fine on non-binary trees. I ask because I have seen a few different definitions of euler tour where only binary trees are used - no mention in the definition of non-binary trees. But in my implementation where a node can have any # of children, it seems to work fine and still fits with my idea of the visit order of a Euler tour (although the # of visits to a parent node increases if you have more child nodes obviously).

    2) I think my output is right, but I'm reading definitions like 'a euler tour is a tour where each node is visited exactly one time'. But that doesn't make sense to me, because in this online java data structures book http://books.google.com/books?id=bmldwIpasiQC&pg=PA517&lpg=PA517&dq=%22euler+tour%22+order+printing+java&source=web&ots=I6aaVC1Al5&sig=nY7741M_EkYcqzaFCj7-8tvFSNQ#PPA517,M1 each node is visited THREE times (well for a non binary tree I guess it could be more of course!). Does the output of my little sample app fit the conventional definition of a Euler tour?

Thanks
DJ_AM_JuiceboxAsked:
Who is Participating?

[Webinar] Streamline your web hosting managementRegister Today

x
 
Infinity08Connect With a Mentor Commented:
Ah, I see. I just read up a bit on this. The tree is converted to an undirected graph (by basically doubling all edges), and then the Euler tour algorithm is used to find a path. depth-first, in-order, etc. traversals of a tree are simply special cases of this Euler tour traversal.

So, to answer your questions :

1. It works fine on non-binary trees. As long as you can do a depth-first traversal (which is true for all trees), the Euler tour method can be used.

2. Yes, that's indeed the correct way to traverse the tree for the Euler tour. Note that that still fits the Euler tour definition (a path that visits each edge in a graph exactly once), since we doubled every edge in the tree.
0
 
Infinity08Commented:
Am I missing something ? An Euler tour is a path that traverses all edges in an undirected graph exactly once. How does that apply to tree traversal ?

>>     Visit history output:
>>     A    B   50   B   100   B   A   C

That's pretty much a depth-first traversal :

        A B 50 100 C
0
 
DJ_AM_JuiceboxAuthor Commented:
Ah ok that makes sense then, thanks.
0
All Courses

From novice to tech pro — start learning today.