Detailed explanation of non-recursive post-order traversal algorithm for binary trees

Detailed explanation of non-recursive post-order traversal algorithm for binary trees_javascript skills

WBOY

Release： 2016-05-16 17:01:15

Original

1719 people have browsed it

Among the non-recursive traversals of pre-order, mid-order and post-order, post-order is the most troublesome. If you only keep pointers to nodes on the stack, it is not enough. Some additional information must be stored on the stack. middle.
There are many methods, here is just one, first define the data structure of the stack node

Copy code The code is as follows:

typedef struct{Node * p; int rvisited;}SNode //Node is the node structure of the binary tree. rvisited==1 means that the right node of the node pointed by p has been visited.

lastOrderTraverse(BiTree bt){
　 //First, start from the root node, go to the lower left, go all the way to the end, and push every node on the path onto the stack.
p = bt; Pass
　bt = bt.lchild;
　}

//Then enter the loop

while(!Stack.empty()){ //As long as the stack is not empty

sn = Stack.getTop(); // sn is the top node of the stack

　 //Note that as long as any node N has a left child, after N is pushed onto the stack, N's left child must also be pushed onto the stack (this is reflected in the second half of the algorithm), so when we When we get the element at the top of the stack, we can be sure that this element either has no left child, or its left child has been visited, so we don't care about its left child at this time, we only care about its right child.

　　 //If its right child has been visited, or the element has no right child, then according to the definition of post-order traversal, you can visit this node at this time.

　if(!sn.p.rchild || sn.rvisited){

　　p = pop();
　　visit(p);
　　}
　　else //If its right child It exists and rvisited is 0, which means that its right child has not been touched before, so we will deal with its right child.
　　{
　　　 //At this time we need to start from its right child node and go all the way to the lower left until we reach the end, and push all the nodes on this path onto the stack.

　　　 //Of course, the rvisited of the node must be set to 1 before pushing it onto the stack, because pushing its right child onto the stack means that its right child will be visited before it (this is easy to understand, because we Always take the element from the top of the stack for visit). It can be seen that the next time the element is on the top of the stack, its right child must have been visited, so rvisited can be set to 1 here.

sn.rvisited = 1;

// Go to the bottom left and push all elements on the path onto the stack

p = sn.p.rchild;

while(p != 0){
push(p, 0) ;
　　　　p = p.lchild;
　　　}
　　}//This round of loop has ended. We don’t have to worry about the nodes just pushed onto the stack. The next round of loop will take care of these nodes. Very good.
　}
}