An example of nonrecursive sequential traversal algorithm for binary trees

  • 2020-03-30 01:38:47
  • OfStack

In the nonrecursive traversal of preorder, middle order, and post order, it is the most difficult to count the post order. It is not enough to keep the pointer to the node in the stack. 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 the Node structure of binary tree. Rvisited ==1 represents that the right Node of the Node pointed by p has been visited.
lastOrderTraverse(BiTree bt){
  //First, start at the root node, go to the bottom left, go to the end, and push every node in the path.
  p = bt;
  while(bt){
    push(bt, 0); //Push two messages on the stack, one is the node pointer, one is whether its right node has been accessed
    bt = bt.lchild;
  }
  //And then it goes into the loop
  while(!Stack.empty()){ //As long as the stack is not empty
    sn = Stack.getTop(); //Sn is the top of the stack
    //Note that any one node N, as long as he has left children, are in the N into the stack, N the left child must also follow into the stack (the second part of the embodied in the algorithm), so when we get to the top of stack elements, can be sure that this element or have no children left, either the left child has been visited, so at this point we don't care about the children left, we only care about their children right.
    //If the right child has been accessed, or if the element does not have a right child, the node can be visited by the traversal definition.
    if(!sn.p.rchild || sn.rvisited){
      p = pop();
      visit(p);
    }
    else //If its right child exists and rvisited is 0, it indicates that its right child has not been touched before, so it goes to deal with its right child.
    { 
      //So we're going to start at the right child and go all the way down to the left until we get to the end, and we're going to push all the nodes in that path.
      //Of course, set the node's rvisited to 1 before the push, because the push of its right child means that its right child must be accessed before it (which makes sense because we always pull elements from the top of the stack to visit). Thus, the next time the element is at the top of the stack, its right child must have been visited, so you can set rvisited to 1 here.
      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 loop is over, we don't have to worry about the nodes that we just pushed, the next loop will take care of them.
  }
}


Related articles: