二叉树先序遍历的非递归算法具体实现(2)

while ( !IsStackEmpty(S) || pBiNode)  //主要修改的就是这句
 {
  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); //如果此时栈已空，就有问题
  }
  pBiNode = pBiNode->rchild;
 }
 return 0;
}

在第一个while循环加入这个之后，就可以了，测试用例与二叉树先序遍历类似。如下测试上节的二叉树例子：

此时输入的数据仍然还是 12 34 0 0 78 0 0，测试结果如下：

--- 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

这个还不足以测试，再看如下的二叉树

此时输入数据应该为：12 34 24 0 0 50 0 0 78 37 0 0 0，测试结果如下：

--- 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

由先序遍历可知，正好是正确的，另外这些算法不光是对先序遍历的，如果想变为中序或者后序，只需将上面算法中的visit之类的先去掉，然后将它加入合适的位置，就可以了

您可能感兴趣的文章: