数据结构入门（三）栈的应用 (2)

  关于二叉树的介绍与实现，可以参考笔者的文章：二叉树的Python实现。二叉树的深度优先遍历，也就是先序、中序、后续遍历，在文章二叉树的Python实现中，我们已经用递归的方法实现了，这是因为二叉树天然就具有良好的递归性质，就连它的定义也可用递归来实现。在本文中，笔者将要用栈来实现二叉树的深度优先遍历。
  以先序遍历为例，先访问根结点，然后遍历左子树接着是遍历右子树，因此我们可以利用堆栈的先进后出的特点，先将右子树压栈，再将左子树压栈，这样左子树就位于栈顶，可以保证结点的左子树先与右子树被遍历。
  二叉树的实现代码不再给出，读者可参考二叉树的Python实现，用栈实现前序遍历的函数如下：

# 使用栈结构实现前序遍历 def preStack(self): if self.data is not None: s = Stack() s.push(self) while not s.is_empty(): currentNode = s.pop() print(currentNode.data, end=' ') if currentNode.right is not None: s.push(currentNode.right) if currentNode.left is not None: s.push(currentNode.left)

构建的示例二叉树如下：

输出的结果如下：

先序遍历（递归）为: 18 7 3 4 11 5 1 3 6 2 4 先序遍历（非递归）为: 18 7 3 4 11 5 1 3 6 2 4 总结

  堆栈（Stack）最早由 Alan M. Turing（艾伦·图灵）于 1946 年提出，当时是为了解决子程序的调用和返回。在本文及前面的文章中，介绍了一些关于栈的应用，当然，还有许多话题未涉及，比如：解决迷宫问题，HTML标签匹配，子程序的调用和返回等。另外，栈还常常与递归方法一起使用，能轻松地解决很多问题~
  关于栈在其它问题中的应用，可以参考网址: https://www.geeksforgeeks.org/stack-data-structure/ 。

参考文献

《啊哈！算法》啊哈磊著 人民邮电出版社 p32-35

《数据结构(C语言版)》 严蔚敏 吴伟民 著 清华大学出版社 p48-50

Data Structures & Algorithms in Python, M.T.Goodrich, R.Tamassia, M.H.Goldwasser著, p229-237

二叉树深度遍历的非递归算法分析及Java实现: https://my.oschina.net/husthang/blog/852982