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?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

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

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
DJ_AM_JuiceboxAuthor Commented:
Ah ok that makes sense then, thanks.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.