中序遍历的思想是在第二次经过结点的时候才去访问结点数据，要一直去寻找结点的左子树，访问完左子树在返回结点并获取结点数据，然后访问右子树，重复这个过程，也就是说如果当前结点有左子树就要转去左子树，访问完左子树才访问当前结点，这个场景刚好可以使用栈来实现，有左子树则把当前结点入栈，访问完左子树，再出栈并访问结点数据。非递归遍历算法的思想如下：
- 步骤一：
- 定义一个当前指针，并指向根结点，当前指针指向的结点称为当前结点；
- 步骤二：
- 如果当前结点有左子树，那么当前结点入栈，当前指针指向当前结点的左子树；
- 如果当前结点没有左子树，访问当前结点数据；
- 步骤三：
- 当前结点右子树非空，当前指针指向当前结点右子树，转步骤二；
- 当前结点右子树为空且栈非空，返回并弹出栈顶元素给当前指针，访问当前结点，当前指针指向当前结点右子树，转步骤二；
- 当前结点右子树为空，且栈为空，遍历结束。
根据这个步骤，非递归中序遍历的C++代码实现如下：
1. void nonrecursive_traversal(MyTreeNode* tree) 2. { 3. stack<MyTreeNode*> s; 4. MyTreeNode* pStart = tree; 5. while (pStart->left != NULL) 6. { 7. //有左子树 8. s.push(pStart); //根结点入栈 9. pStart = pStart->left; //指针下移，指向左子树 10. } 11. while (pStart != NULL) 12. { 13. cout << pStart->data << " "; //没有左子树则访问 14. if (pStart->right != NULL) 15. { 16. //右子树非空 17. pStart = pStart->right; 18. while (pStart->left != NULL) 19. { 20. //有左子树 21. s.push(pStart); //根结点入栈 22. pStart = pStart->left; //指针下移，指向左子树 23. } 24. } 25. else if ((pStart->right == NULL) && (!s.empty())) 26. { 27. //右子树为空，且栈非空 28. pStart = s.top(); 29. s.pop(); 30. } 31. else 32. { 33. //右子树为空，且栈为空 34. pStart = NULL; 35. } 36. } 37. }
下面创建一棵树来测试一下算法，二叉树如下
