javatreebinary-treetree-traversalpostorder

Post order traversal for a general tree

I am currently a student who's assignment involves dealing with adapting Binary Tree methods in to General Tree methods. My only question is, Is my post order traversal for the following general tree correct? If so then I know my algorithm is working, I am just not able to get the hang of post order traversal correctly I feel and thought the website could help.

                     B
--------------------|------------------
|                   |                 |
A             ------D-----         ---I---
             |      |    |        |       |
             C      E    G        H       L
                         |
                         F

My result is: A C E F G D H L I B

Solution

  • Your answer looks correct to me.

    This trick works for generalized tree's, not only binary ones.

    Follow the dotted line and visit the node when you find the black dot.

    Post order traversal

    Reusing this graph for pre-order traversal is just a matter of rotating all the black dots 180 degrees. In-order traversal would be 90 degrees but is ambiguous if this isn't a binary tree.

    see http://en.wikipedia.org/wiki/Tree_traversal

    From http://www.brpreiss.com/books/opus4/html/page259.html

    postorder traversal visits the root last. To do a postorder traversal of a general tree:

    Do a postorder traversal each of the subtrees of the root one-by-one in the order given; and then visit the root.