Non recursive sequential traversal of binary trees in C language data structures

Non - recursive sequential traversal of 2 - fork trees for C language data structures

Preface:

In the non-recursive traversal of preorder, middle order and postorder, it is the most troublesome to count the postorder. If only the pointer pointing to the node is kept in the stack, it is not enough. Some additional information must be stored in the stack.

There are many ways to do this, but just one is to define the data structure of the stack node

typedef struct{Node * p; int rvisited;}SNode //Node  is 2 The node structure of the fork tree, rvisited==1 On behalf of p The right node of the node pointed to has been accessed. 

lastOrderTraverse(BiTree bt){
　　// First of all, starting at the root node, going down to the left, 1 Go straight to the end and turn every step of the way 1 One node pushed. 
　　p = bt;
　　while(bt){
　　　　push(bt, 0); //push To the two messages in the stack, 1 It's a pointer to a node, 1 Is whether its right node has been accessed 
　　　　bt = bt.lchild;
　　}

　　// And then it goes into the body of the loop 
　　while(!Stack.empty()){ // As long as the stack is not empty 
　　　　sn = Stack.getTop(); // sn It's the top of the stack 

　　　　// Notice that arbitrary 1 A node N , as long as he has left children N When I push it, N The left child must have followed ( This is reflected in the second half of the algorithm ) , so when we get to the top of the stack, we can be sure that this element either has no left child, or its left child has already been accessed, so at this point we don't care about its left child, we only care about its right child. 

　　　　// If the right child has already been accessed, or if the element has no right child, then the definition is traversed by the back order, and can be visit This node right here. 
　　　　if(!sn.p.rchild || sn.rvisited){
　　　　　　p = pop();
　　　　　　visit(p);
　　　　}
　　　　else // If its right child exists and rvisited for 0 ", indicating that he had not touched his right child before, so he went to deal with it 1 Lower its right child. 
　　　　{ 
　　　　　　// So we're going to start at the right child node 1 Go straight down to the bottom left, to the end, and push all the nodes in the path. 

　　　　　　// Of course, you have to push the node before you do that rvisited set 1 , because its right child's push means its right child must be accessed before it ( This makes sense because we're always pulling elements from the top of the stack visit) . So we know, down 1 The next time the element is at the top of the stack, its right child must have been visit I passed it, so I can put it here rvisited Set to 1 . 
　　　　　　sn.rvisited = 1;

　　　　　　// Go to the bottom left to the end and push all the elements in the path 
　　　　　　p = sn.p.rchild;
　　　　　　while(p != 0){
　　　　　　　　push(p, 0);
　　　　　　　　p = p.lchild;
　　　　　　}
　　　　}// this 1 The wheel loop is over, so we don't have to worry about the nodes that we just pushed. Down 1 The wheel cycle will take good care of these nodes. 
　　}
}

If you have any questions, please leave a message or come to the site community to exchange discussion, thank you for reading, hope to help you, thank you for your support of the site!