一、二叉树的遍历

1、先序遍历

遍历过程为：
1）访问根结点
2）先序遍历其左子树
3）先序遍历其右子树
这样的一种遍历过程，其实也是一种递归的思想。

A（BDFE）（CGHI），先序遍历=> ABDFECGHI

2、中序遍历

遍历过程为：
1）中序遍历其左子树
2）访问根结点
3）中序遍历其右子树

对根结点A来讲，BDFE是左边，CGIH是右边，所以中序遍历的整个过程是先要把左边的给print出来，然后再print根结点A，最后print右边。而print左边的时候，也是同样的规则，先print左边的，再print右边的
（DBEF）A（GHCI）中序遍历=> DBEF A GHCI

3、后序遍历

遍历过程为：
1）中序遍历其左子树
2）中序遍历其右子树
3）访问根结点

对根结点A来讲，BDFE是左子树，CGIH是右子树，所以先把左子树遍历完，然后遍历右子树，最后输出根结点。B的左边遍历完了，然后遍历B的右边，又继续，最后输出左子树的根结点B
（DEFB）（HGIC）A，后序遍历=>DEFBHGICA

总结

1）先序、中序和后序遍历过程：遍历过程中经过结点的路线一样，只是访问各个结点的时机不同
2）图中在从入口到出口的曲线上用×，※和△三种符号分别标记出了先序、中序和后序遍历访问各结点的时刻，每个结点都有三次碰到它的机会，第一次碰到的时候就叫先序，第二次碰到并输出就叫中序，第三次碰到就叫后序遍历。

二、二叉树的非递归遍历

递归的根本方法其实用的是递归。

1、中序遍历的非递归遍历算法

基本思路：使用堆栈
1）遇到一个结点，就把它压栈，并去遍历它的左子树
2）当左子树遍历结束后，从栈顶弹出这个结点并访问它
3）然后按其右指针再去中序遍历该结点的右子树

2、先序遍历的非递归遍历算法

3、后序遍历的非递归遍历算法

https://www.cnblogs.com/SHERO-Vae/p/5800363.html
总结的很好。其实二叉树遍历的核心问题，就是二维结构的线性化，即产生一个序列，而这个序列是一维的线性结构

4、层序遍历

队列实现

遍历从根结点开始，首先将根结点入队，然后开始执行循环：结点出队、访问该结点、其左右儿子入队

得到的序列有这样的特征：**它是一层一层访问的，先是A，然后是BC，然后再到下一层

步骤

1）从队列中取出一个元素
2）访问该元素所指结点
3）若该元素所指结点的左右孩子结点非空，则将其左右孩子的指针顺序入队

三、遍历二叉树的应用

1、输出二叉树中的叶子结点

可以在二叉树的遍历算法中增加检测结点的“左右子树是否都为空”这一条件

2、求二叉树的高度

思路：求左右子树的最大高度，然后加1

3、二元运算表达式树及其遍历

表达式树：叶结点代表运算数，非叶结点是运算符号。如下面的是想把A的左子树和右子树加起来

三种遍历可以得到三种不同的访问结果：

先序遍历：++a*bc*+*defg
中序遍历：a+b*c+d*e+f*g
后序遍历：abc*+de*f+g*+

先序遍历对应前缀表达式，
中序遍历对应中缀表达式（会受到运算符优先级的影响），那怎么解决呢？答案是当你输出左子树的时候，先输出一个左括号，左子树结束的时候，加一个右括号。
后缀遍历对应后缀表达式。

4、由两种遍历序列确定二叉树

特殊地：由前序和后序遍历 ，不能唯一地确定一棵二叉树，一定要有中序遍历才可以。举例：

先序和中序遍历序列确定一棵二叉树

1）根据先序遍历序列第一个结点确定**根结点

2）根据根结点在中序遍历序列中分割出左右两个子序列

3）对左子树和右子树分别递归使用相同的方法继续分解

四、树的同构

给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。现给定两棵树，判断它们是否同构。