CODEWITHSUNDEEP
javatreebinary-treetree-traversalpostorder
Mjall2
Mjall2

Reputation: 263

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

Upvotes: 1

Views: 6977

Answers (2)

candied_orange
candied_orange

Reputation: 7308

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.

Upvotes: 5

murali kurapati
murali kurapati

Reputation: 1586

Postorder printing can be done using recursion. you can visualize yourself from the recursion function below . The node is getting printed after the both functions above the print() function are returned. Try to analyze your tree on the code below manually on paper and you can find the result is correct. Initially visualizing a recursion function like this would be difficult, but you should be able to visualize to be good programmer, anyway have a try.

void postorder(node)
{
   if(node=NULL)
      return;
   postorder(node.left);
   postorder(node.right);
   print(node);
}

Upvotes: 0

Related Questions