18
-------------
In a binary tree starting from the root there always exists a path to reach any node.But for any particular node this path is unique.Each of these paths are extendible upto some leaf node.
So if we cover every path once upto the leaf nodes we cover up all the nodes once. So to traverse all the nodes if we traverse each leaf node from the root we will traverse each node the tree. For post order following is the non recursive algorithm.
Algorithm
----------
1>Here the leftmost path is chosen and the leaf node is traversed first. let this node be nl.
2>Then it's immediate parent is traversed if this parent either does not have a right son or nl itself is the right son. This process goes on .
If the parent has a right son which has not yet been traversed, then the 2nd left most path containing the right son is chosen and the leaf is traversed. Again the same process starts.
3>This process is followed until we return to root again but do not find a new next leftmost path. Then root is traversed.
In the attached jpeg leftmost path from root is 9, 8, 1. So the leaf ( i.e. 1 is traversed). As 8 does not have a right son 8 is traversed. As 9 has a right son (i.e. 10) , the second left most path containing the right son (i.e. 9, 10)is chosen. Then the leaf i.e. 10 is traversed. Then at last root i.e. 9 is traversed.
Description
------------
I developed this simple program in C in the year 2004 when started going through the subject data structure. This will give an idea of how to program tree traversals.
The screen shot and C file are self explanatory. Please go through the screenshot.
The exe file may be run in DOS mode in a windows 98 or XP machine to test the result.
But please do not use a non integral input. During that period of time as I was just a novice I did not check for wrong inputs. Extremely sorry for this.
But all other checks like null pointer and all are implemented.
Please find the attachments.
