public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
上图的用链式存储为：
二叉树遍历
二叉树的遍历是指从二叉树的根节点出发，按照某种次序依次访问二叉树中的所有接节点，使得每个节点被访问依次，且仅被访问依次。
二叉树的访问次序可以分为四种：
前序遍历
中序遍历
后续遍历
层序遍历
前序遍历
通俗的说就是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左再向右的方向访问。
从根结点出发，则第一次到达结点A，故输出A;
继续向左访问，第一次访问结点B，故输出B；
按照同样规则，输出D，输出H；
当到达叶子结点H，返回到D，此时已经是第二次到达D，故不在输出D，进而向D右子树访问，D右子树不为空，则访问至I，第一次到达I，则输出I；
I为叶子结点，则返回到D，D左右子树已经访问完毕，则返回到B，进而到B右子树，第一次到达E，故输出E；
向E左子树，故输出J；
按照同样的访问规则，继续输出C、F、G；
二叉树的前序遍历输出为：
ABDHIEJCFG
中序遍历
中序遍历就是从二叉树的根结点出发，先访问左节点，再访问父节点，最后访问右节点。
从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出B；继续到达D，H；
到达H，H左子树为空，则返回到H，此时第二次访问H，故输出H；
H右子树为空，则返回至D，此时第二次到达D，故输出D；
由D返回至B，第二次到达B，故输出B；
按照同样规则继续访问，输出J、E、A、F、C、G；
二叉树的中序遍历输出为：
HDIBJEAFCG
后序遍历
后序遍历就是从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左在向右的方向访问。
二叉树后序访问如下：
从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出B；继续到达D，H；
到达H，H左子树为空，则返回到H，此时第二次访问H，不输出H；
H右子树为空，则返回至H，此时第三次到达H，故输出H；
由H返回至D，第二次到达D，不输出D；
继续访问至I，I左右子树均为空，故第三次访问I时，输出I；
返回至D，此时第三次到达D，故输出D；
按照同样规则继续访问，输出J、E、B、F、G、C，A；
二叉树的后序遍历输出为：
HIDJEBFGCA
虽然二叉树的遍
《一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》
【docs.qq.com/doc/DSmxTbFJ1cmN1R2dB】 完整内容开源分享
历过程看似繁琐，但是由于二叉树是一种递归定义的结构，故采用递归方式遍历二叉树的代码十分简单。
递归实现代码如下：
package huawei.tree;
public class OrderTraverse {
/二叉树的前序遍历递归算法/
public void preOrderTraverse(TreeNode root) {
if(root == null) {
return;
}
System.out.println(root.val);
preOrderTraverse(root.left); /再先序遍历左子树/
preOrderTraverse(root.right); /最后先序遍历右子树/
}
/二叉树的中序遍历递归算法/
public void inOrderTraverse(TreeNode root) {
if(root == null) {
return;
}
inOrderTraverse(root.left); /中序遍历左子树/
System.out.println(root.val);
inOrderTraverse(root.right); /最后中序遍历右子树/
}
/二叉树的后序遍历递归算法/
public void postOrderTraverse(TreeNode root) {
if(root == null) {
return;
}
postOrderTraverse(root.left); /先后序遍历左子树/
postOrderTraverse(root.right); /再后续遍历右子树/
System.out.println(root.val); /显示结点数据，可以更改为其他对结点操作/
}
}
层次遍历
层序遍历也就是广度优先遍历
import huawei.tree.TreeNode;
import java.util.ArrayList;
import java.util.Deque;
import java.util.linkedList;
import java.util.List;
public class BinaryTreeBfs {
static List res = new ArrayList<>();
public static void main(String[] args) {
TreeNode head = new TreeNode(1);
TreeNode second = new TreeNode(2);
TreeNode three = new TreeNode(3);
TreeNode four = new TreeNode(4);
TreeNode five = new TreeNode(5);
TreeNode six = new TreeNode(6);
TreeNode seven = new TreeNode(7);
head.right = three;
head.left = second;
second.right = five;
second.left = four;
three.right = seven;
three.left = six;
System.out.print(“广度优先遍历结果：”);
new BinaryTreeBfs().boardFirstSearch(head);
for (TreeNode node : res) {
System.out.print(node.val + " ");
}
}
//广度优先使用Queue
public void boardFirstSearch(TreeNode root) {
if (root == null) {
return;
}
Deque deque = new linkedList<>();
deque.offer(root);
while (!deque.isEmpty()) {
TreeNode node = deque.poll();
res.add(node);
if (node.left != null) {
