Postorder traversal requires the L, R, and V tasks to be applied to each node of the binary tree. Here, L means visiting the left child, R means visiting the right child, and V means visiting the node that is displaying its content.
The question is, how will we know which tasks have already been performed on a node and which tasks are left to be performed? To do so, we will use two arrays, nodeArray and valueArray. nodeArray contains the node that the tasks are to be performed one, while valueArray is used to indicate what task has been left on the corresponding node. valueArray can have one of the following two values:
- Value 0: This indicates that the left link of the node has been traversed and that two tasks are pending: traversing the node being pointed to by its right pointer and visiting the node.
- Value 1: This indicates that the node being pointed to by its right pointer has been traversed. Only the task of visiting the node is pending.
Once the binary search tree has been created, the nontravpost function is invoked for postorder traversal of the binary tree and the root node is passed to the function as an argument. The nontravpost function is a non-recursive function.
A temporary pointer, temp, is set to point at the root node. A while loop is set to execute until temp is not NULL. Within the while loop, the pushNode function is called and the node being pointed to by temp is passed to it, along with a value of 0.
In the pushNode function, the value of top that was initialized to -1 is incremented to 0 and the node, 40, and the value 0 are pushed into the nodeArray and valueArray arrays at index location being pointed to by top (the index location, 0):
The pushNode function ends and control jumps back to the nontravpost function, where the temp pointer is set to point at its left node. The left pointer of temp is pointing at node 20, so temp will now point at node 20. The while loop will keep executing until the temp pointer reaches the NULL pointer. Again, within the while loop, the pushNode function is called and node 20 and value 0 are passed to it. In the pushNode function, the value of the top pointer is incremented to 1 and node 20 and the value 0 are pushed to the nodeArray[1] and valueArray[1] array index locations, as follows:
This process is repeated for the next node that's on the left of the temp node. On the left of node 20 is node 10. Upon pushing node 10, the nodeArray and valueArray arrays will look as follows:
Because temp has reached the NULL pointer, the first while loop will terminate and the next while loop will execute while the value of top is greater than or equal to 0. The popNode function is invoked, which returns the node in the nodeArray array that's being pointed at by the top index. The value of the top index is currently 2, so the node at the index location of nodeArray[2], that is, 10, is accessed and returned to the nontravpost function. In the nontravpost function, node 10 will be assigned to the temp pointer. Next, the popVal function is invoked, which returns the value in the valueArray array that's being pointed to by the top index. This happens at the valueArray[2] index location. That is, the value 0 at the valueArray[2] index location is returned by the popVal function and is assigned to the val variable. The value of top is now decremented to 1. Because the value in the val variable is 0, an if block is executed in the nontravpost function. The if block checks whether the right child of the node being pointed at by the temp pointer isn't NULL; if so, the pushNode function is called and the node being pointed to by temp, that is, 10 and integer value 1, is passed to it as an argument.
In the pushNode function, the value of top is incremented to 2 and node 10 and the value 1 are pushed to the nodeArray[2] and valueArray[2] index locations, respectively:
After executing the pushNode function, control jumps back to the nontravpost function, where the temp pointer is set to point to where its right pointer is pointing. But because the right pointer of temp is NULL, the while loop will break and the data member of the node being pointed to by temp (that is, 10) is displayed on the screen.
Again, the while loop will execute and the popNode and popVal functions will execute to pop node 20 and value 0, respectively. Node 20 will be pointed to by the temp pointer. Because the value that's being popped is 0, the right pointer of the node being pointed to by temp is searched. If the right pointer of node 20 is pointing at node 30, the pushNode function is invoked and node 20 is pushed, along with the value 1:
Next, the temp pointer is set to point to where its right pointer is pointing, that is, node 30. The pushNode function is invoked and node 30 and an integer value of 0 are pushed to the nodeArray and valueArray arrays, respectively:
This procedure is repeated until the stacks are empty.
The program is compiled with GCC using the following statement:
D:\CAdvBook>GCC postordernonrec.c - postordernonrec
If no error appears upon compilation, then the postordernonrec.c program has successfully compiled into the postordernonrec.exe file. Let's run this file and enter some new elements that will build a binary tree and get its postorder traversal using a non-recursive approach. By doing this, we will get the following output:
