The non recursive algorithm of binary tree first order traversal is implemented

In the previous article, we talked about the recursive traversal algorithm of binary trees (link: #). This article mainly focuses on the non-recursive algorithm of binary trees, using the stack structure

The idea of the non-recursive algorithm obtained by root traversal is summarized as follows:

1) push, mainly the first node is pushed, and then visit this node

2) while, loop through the current node until the left child has no node

3) if the right child of the node is true, turn to 1) continue traversing, otherwise exit the current node and turn to parent node and turn to 1)

Let's first look at the algorithm that conforms to this idea:

int PreOrderTraverseNonRecursiveEx(const BiTree &T, int (*VisitNode)(TElemType data))
{
 if (T == NULL)
 {
  return -1;
 }
 BiTNode *pBiNode = T;
 SqStack S;
 InitStack(&S);
 Push(&S, (SElemType)T);
 while (!IsStackEmpty(S))
 {
  while (pBiNode)
  {
   VisitNode(pBiNode->data);
   if (pBiNode != T)
   {
    Push(&S, (SElemType)pBiNode);
   }   
   pBiNode = pBiNode->lchild;
  }
  if(pBiNode == NULL)
  {
   Pop(&S, (SElemType*)&pBiNode); 
  }  
  if ( pBiNode->rchild == NULL)
  {
   Pop(&S, (SElemType*)&pBiNode); //If the stack is empty at this point, there is a problem
  }
  pBiNode = pBiNode->rchild;
 }
 return 0;
}

Note: 1) the stack structure is used here, see above (link: #)

                      2) here, when saving the node, I saved the pointer, which is the address of the node, and changed it into int storage. When using the pointer in pop, I took &pBiNode instead of pBiNode. Change the definition to BiTree pBiNode to make sense.

The algorithm above is actually wrong! Why? So here I'm going to check for a long time, and there's been an infinite loop, there's been an infinite loop, there's been an exit from the left subtree and the right subtree doesn't show up, and then finally I change the first while condition, why? Because if after pop, the stack is empty but the right subtree is still there, it can not continue, this is written after I did not do much verification, I will explain later, here is not pressed null pointer, see the example of pressing null pointer, mainly is pressed when the left subtree is empty, as follows:

int PreOrderTraverseNonRecursive(const BiTree &T, int (*VisitNode)(TElemType data))
{
 if (T == NULL)
 {
  return -1;
 }
 BiTNode *pBiNode = T;
 SqStack S;
 InitStack(&S);
 Push(&S, (SElemType)T);
 while (!IsStackEmpty(S))
 {
  GetTop(S, (SElemType*)&pBiNode);
  while (pBiNode)
  {
   VisitNode(pBiNode->data);  
   pBiNode = pBiNode->lchild;
   Push(&S, (SElemType)pBiNode);
  }
  if(pBiNode == NULL)
  { 
   Pop(&S, (SElemType*)&pBiNode);
  }  
  if ( !IsStackEmpty(S))
  {
   Pop(&S, (SElemType*)&pBiNode);
   pBiNode = pBiNode->rchild;
   Push(&S, (SElemType)pBiNode);
  }
 }
 return 0;
}

Here is that the first pressure into the root node, and then determine whether the left subtree is empty, not empty into the stack, or exit after the while loop will be NULL node stack, to judge whether the current stack is empty, if not empty out of the stack and get the parent node and children right judgment, push the right child node, to determine whether the right subtree of the left child is empty, continue to cycle.

There are two areas of waste: one is to push an empty child into the stack, and the other is to use GetTop frequently to get the top element

Here to return to come and look at the beginning of the design algorithm, there is no pressure in the NULL pointer or an empty child node, but does not output complete, here we can think of in the judgment of the stack when joining, whether the current node is NULL, so as not to appear not show out the left subtree nodes can't show right subtree of embarrassment, as follows:

//Nonrecursive sequential traversal of the binary tree
int PreOrderTraverseNonRecursiveEx(const BiTree &T, 
           int (*VisitNode)(TElemType data))
{
 if (T == NULL)
 {
  return -1;
 }
 BiTNode *pBiNode = T;
 SqStack S;
 InitStack(&S);
 Push(&S, (SElemType)T);
 while ( !IsStackEmpty(S) || pBiNode)  //The main modification is this sentence
 {
  while (pBiNode)
  {
   VisitNode(pBiNode->data);
   if (pBiNode != T)
   {
    Push(&S, (SElemType)pBiNode);
   }   
   pBiNode = pBiNode->lchild;
  }
  if(pBiNode == NULL)
  {
   Pop(&S, (SElemType*)&pBiNode); 
  }  
  if ( pBiNode->rchild == NULL)
  {
   Pop(&S, (SElemType*)&pBiNode); //If the stack is empty at this point, there is a problem
  }
  pBiNode = pBiNode->rchild;
 }
 return 0;
}

After this is added to the first while loop, the test case is similar to the binary tree order traversal. The binary tree example in the previous test section is as follows:

< img border = 0 SRC = "/ / files.jb51.net/file_images/article/201401/201419150258198.jpg" >

At this time, the input data is still 12, 34, 0, 0, 78, 0, and the test results are as follows:

BiTree - - -
Please Enter BiTree Node data:
12
Please Enter BiTree Node data:
34
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
78
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
12, 34, 78

That's not enough to test, but let's look at the binary tree

< img border = 0 SRC = "/ / files.jb51.net/file_images/article/201401/201419150415306.jpg" >

At this time, the input data should be: 12, 34, 24, 0, 0, 50, 0, 0, 78, 37, 0, 0, 0, and the test results are as follows:

BiTree - - -
Please Enter BiTree Node data:
12
Please Enter BiTree Node data:
34
Please Enter BiTree Node data:
24
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
50
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
78
Please Enter BiTree Node data:
37
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
12, 34, 24, 50, 78, 37

In addition, these algorithms are not only for the first order traversal, if you want to become the middle order or after the order, just remove the above algorithm such as visit, and then add it to the appropriate location, it is ok