二叉树遍历
所谓遍历是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。
二叉树的遍历分为深度优先和广度优先两种，其中深度优先又包括前序遍历、中序遍历、后序遍历三种，所谓前、中、后是根据根节点与左右子树的遍历顺序决定的。
前序遍历是先访问根节点再访问左子树最后访问右子树；中序遍历是先访问左子树再访问根节点最后访问右子树；后序遍历是先访问左子树再访问右子树最后访问根节点。
广度优先遍历则是从根节点开始由上到下按层访问，每一层从左到右依次访问。
下面分别介绍这几种遍历方式以及它们的代码实现。
二叉树结点定义
python代码定义二叉树结点如下：
图 a(二叉树)
前（先）序遍历
递归思想实现先序遍历较易理解，从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问 。二叉树的前序遍历输出为：ABDHIEJCFG
python代码实现如下：
非递归遍历思路如下：
1）定义一个栈
2）将根节点压入栈中
3）每次从栈中弹出结点记为cur并打印，如果右孩子不为空，将右孩子压入栈中，如果左孩子不为空，将左孩子压入栈中
4）不断重复步骤3，直到栈空结束
python代码实现如下：
中序遍历
递归思想实现中序遍历顺序，先遍历左子树；再访问根结点；最后遍历右子树。二叉树的中序遍历输出为：HDIBJEAFCG
python代码实现如下：
非递归遍历思路如下：
1）申请一个栈stack，申请一个变量cur指向头结点
2）先把头结点压入栈中，对于以cur为头结点的整颗子树来说，依次把整颗树的左边界压入栈中，即不断令cur=cur.left
3）不断重复步骤2，直到cur为空，此时从栈中弹出结点node并打印，然cur=node.right,然后重复步骤2
4）当stack为空并且cur为空时，结束。
python代码实现如下：
后序遍历
递归思想实现后序遍历顺序，先遍历左子树；再遍历右子树；最后访问根结点。二叉树的后序遍历输出为：HIDJEBFGCA
python代码实现如下：
非递归遍历思路如下：
1）申请两个栈s1，s2，然后将头结点压入s1
2）从s1中弹出的结点记为cur,并加入到栈s2中，然后把cur的左孩子压入s1中，然后把cur的右孩子压入s1中
3）不断重复2，直到s1为空
4）从s2弹出结点并打印
python代码实现如下：
广度优先（层序）遍历
广度优先(层序遍历)是用队列来实现的，从二叉树的第一层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问。
按照从根结点至叶结点、从左子树至右子树的次序访问二叉树的结点。
算法：
1、初始化一个队列，并把根结点入列队；
2、当队列为非空时，循环执行步骤3到步骤5，否则执行6；
3、出队列取得一个结点，访问该结点；
4、若该结点的左子树为非空，则将该结点的左子树入队列；
5、若该结点的右子树为非空，则将该结点的右子树入队列；
6、结束。
python代码实现如下：
今日话题
大家对于今天学习的二叉树遍历，有没有更深刻的理解呢？请在评论区留言和作者一起讨论！每日话题就是希望大家多交流，希望你和我一起在这里成长！
