二叉树的遍历方式有很多，如果我们按照从左到右的习惯进行限制，则主要分为4种：
- 前序遍历
- 中序遍历
- 后序遍历
- 层序遍历
下面以Java语言描述几种遍历方式。
-
树形结构
树形结构 - 树形结构代码
/**
* 树结构，包括节点值，左子树节点指针，右子树节点指针
*/
public class TreeNode {
private String value;
private TreeNode left;
private TreeNode right;
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
}
- 初始化树
/**
* 初始化树的节点信息
*/
public class InitTree {
public static TreeNode[] initTree() {
TreeNode[] treeNode = new TreeNode[11];
createInstance(treeNode);
initNodeValue(treeNode);
buildTree(treeNode);
return treeNode;
}
// 创建节点对象
private static void createInstance(TreeNode[] treeNode) {
if (null != treeNode) {
for (int i = 0; i < treeNode.length; i++) {
treeNode[i] = new TreeNode();
}
}
}
// 初始化节点值
private static void initNodeValue(TreeNode[] treeNode) {
// 设置节点0-10的值
treeNode[0].setValue("A");
treeNode[1].setValue("B");
treeNode[2].setValue("C");
treeNode[3].setValue("D");
treeNode[4].setValue("E");
treeNode[5].setValue("F");
treeNode[6].setValue("G");
treeNode[7].setValue("H");
treeNode[8].setValue("I");
treeNode[9].setValue("J");
treeNode[10].setValue("K");
}
// 构建树
private static void buildTree(TreeNode[] treeNode) {
// 初始化节点0的左子树和右子树
treeNode[0].setLeft(treeNode[1]);
treeNode[0].setRight(treeNode[2]);
// 初始化节点1的左子树和右子树
treeNode[1].setLeft(treeNode[3]);
treeNode[1].setRight(treeNode[4]);
// 初始化节点2的左子树和右子树
treeNode[2].setLeft(treeNode[5]);
treeNode[2].setRight(treeNode[6]);
// 初始化节点3的左子树和右子树
treeNode[3].setLeft(treeNode[7]);
// 初始化节点4的左子树和右子树
// 初始化节点5的左子树和右子树
treeNode[5].setLeft(treeNode[8]);
// 初始化节点6的左子树和右子树
treeNode[6].setRight(treeNode[9]);
// 初始化节点7的左子树和右子树
treeNode[7].setRight(treeNode[10]);
// 初始化节点8的左子树和右子树
// 初始化节点9的左子树和右子树
// 初始化节点10的左子树和右子树
}
}
1.前序遍历算法
先来看代码
/**
* 二叉树的前序遍历算法
* 1.判断节点为空，返回空；
* 2.打印节点数据；
* 3.判断是否存在左子树，如果存在，递归，回到步骤1；
* 4.判断是否存在右子树，如果存在，递归，回到步骤1；
*/
public class PreOrder {
public void preOrder(TreeNode treeNode) {
if (null == treeNode) {
return;
}
System.out.print(treeNode.getValue());
TreeNode leftNode = treeNode.getLeft();
preOrder(leftNode);
TreeNode rightNode = treeNode.getRight();
preOrder(rightNode);
}
}
测试代码
public class Test {
public static void main(String[] args) {
TreeNode[] treeNode = InitTree.initTree();
PreOrder preOrder = new PreOrder();
preOrder.preOrder(treeNode[0]);
}
}
运行结果：ABDHKECFIGJ
程序是如何运行的？
（1）调用preOrder方法，传入的根节点A不为null，打印A节点的值A；
前序遍历1
（2）获取到A的左子树B，调用preOrder方法，B不为null，打印B节点的值B，结果AB；
前序遍历2
（3）获取到B的左子树D，调用preOrder方法，D不为null，打印D节点的值D，结果ABD；
前序遍历3
（4）获取到D的左子树H，调用preOrder方法，H不为null，打印H节点的值H，结果ABDH；
前序遍历4
（5）获取H的左子树，调用preOrder方法，H的左子树为null，方法返回null；继续执行H的逻辑，获取到H的右子树K，调用preOrder方法，K不为null，打印K节点的值K，结果ABDHK；
前序遍历5
（6）获取K的左子树，调用preOrder方法，K的左子树为null，方法返回null；继续执行K的逻辑，获取K的右子树，调用preOrder方法，K的右子树为null，方法返回null；（不要懵，方法中我们无非只有3个动作，打印、获取左子树递归、获取右子树递归，运行至此，K、H节点均已判断完毕）继续执行D的逻辑，获取D的右子树，调用preOrder方法，D的右子树为null，方法返回null；继续执行B的逻辑，获取到B的右子树E，调用preOrder方法，E不为null，打印E节点的值E，结果ABDHKE；
前序遍历6
（7）获取E的左子树，调用preOrder方法，E的左子树为null，方法返回null；继续执行E的逻辑，获取E的右子树，调用preOrder方法，E的右子树为null，方法返回null；继续执行A的逻辑，获取到A的右子树C，调用preOrder方法，C不为null，打印C节点的值C，结果ABDHKEC；
前序遍历7
（8）获取到C的左子树F，调用preOrder方法，F不为null，打印F节点的值F，结果ABDHKECF；
前序遍历8
（9）获取到F的左子树I，调用preOrder方法，I不为null，打印I节点的值I，结果ABDHKECFI；
前序遍历9
（10）获取I的左子树，调用preOrder方法，I的左子树为null，方法返回null；继续执行I的逻辑，获取I的右子树，调用preOrder方法，I的右子树为null，方法返回null；继续执行F的逻辑，获取F的右子树，调用preOrder方法，F的右子树为null，方法返回null；继续执行C的逻辑，获取到C的右子树G，调用preOrder方法，G不为null，打印G节点的值G，结果ABDHKECFIG；
前序遍历10
（11）获取G的左子树，调用preOrder方法，G的左子树为null，方法返回null；继续执行G的逻辑，获取到G的右子树J，调用preOrder方法，J不为null，打印J节点的值J，结果ABDHKECFIGJ；
前序遍历11
（12）获取J的左子树，调用preOrder方法，J的左子树为null，方法返回null；继续执行J的逻辑，获取J的右子树，调用preOrder方法，J的右子树为null，方法返回null；至此所有的节点都已判断完成，前序遍历算法的最终结果为：ABDHKECFIGJ。
前序遍历12
2.中序遍历算法
先来看代码
/**
* 二叉树的中序遍历算法
* 1.判断节点为空，返回空；
* 2.判断是否存在左子树，如果存在，递归，回到步骤1；
* 3.打印节点数据；
* 4.判断是否存在右子树，如果存在，递归，回到步骤1；
*/
public class InOrder {
public void inOrder(TreeNode treeNode) {
if (null == treeNode) {
return;
}
TreeNode leftNode = treeNode.getLeft();
inOrder(leftNode);
System.out.print(treeNode.getValue());
TreeNode rightNode = treeNode.getRight();
inOrder(rightNode);
}
}
测试代码
public class Test {
public static void main(String[] args) {
TreeNode[] treeNode = InitTree.initTree();
InOrder inOrder = new InOrder();
inOrder.inOrder(treeNode[0]);
}
}
运行结果：HKDBEAIFCGJ
程序是如何运行的？
（1）调用inOrder方法，传入的根节点A不为null，获取到A的左子树B；调用inOrder方法，B不为null，获取到B的左子树D；调用inOrder方法，D不为null，获取到D的左子树H；调用inOrder方法，H不为null，获取H的左子树；调用inOrder方法，H的左子树为null，方法返回null；打印H节点的值H，结果H；
中序遍历1
（2）继续执行H的逻辑，获取到H的右子树K，调用inOrder方法，K不为null，获取K的左子树；调用inOrder方法，K的左子树为null，方法返回null；打印K节点的值K，结果HK；
中序遍历2
（3）继续执行K的逻辑，获取K的右子树，调用inOrder方法，K的右子树为null，方法返回null；至此，H、K节点均已判断完成；继续执行D的逻辑，打印D节点的值D，结果HKD；
中序遍历3
（4）继续执行D的逻辑，获取D的右子树，调用inOrder方法，D的右子树为null，方法返回null；继续执行B的逻辑，打印B节点的值B，结果HKDB；
中序遍历4
（5）继续执行B的逻辑，获取到B的右子树E，调用inOrder方法，E不为null，获取E的左子树；调用inOrder方法，E的左子树为null，方法返回null；打印E节点的值E，结果HKDBE；
中序遍历5
（6）继续执行E的逻辑，获取E的右子树，调用inOrder方法，E的右子树为null，方法返回null；继续执行A的逻辑，打印A节点的值A，结果HKDBEA；
中序遍历6
（7）继续执行A的逻辑，获取到A的右子树C，调用inOrder方法，C不为null，获取到C的左子树F；调用inOrder方法，F不为null，获取到F的左子树I；调用inOrder方法，I不为null，获取I的左子树；调用inOrder方法，I的左子树为null，方法返回null；打印I节点的值I，结果HKDBEAI；
中序遍历7
（8）继续执行I的逻辑，获取I的右子树，调用inOrder方法，I的右子树为null，方法返回null；继续执行F的逻辑，打印F节点的值F，结果HKDBEAIF；
中序遍历8
（9）继续执行F的逻辑，获取F的右子树，调用inOrder方法，F的右子树为null，方法返回null；继续执行C的逻辑，打印C节点的值C，结果HKDBEAIFC；
中序遍历9
（10）继续执行C的逻辑，获取到C的右子树G，调用inOrder方法，G不为null，获取G的左子树；调用inOrder方法，G的左子树为null，方法返回null；打印G节点的值G，结果HKDBEAIFCG；
中序遍历10
（11）继续执行G的逻辑，获取到G的右子树J，调用inOrder方法，J不为null，获取J的左子树；调用inOrder方法，J的左子树为null，方法返回null；打印J节点的值J，结果HKDBEAIFCGJ；
中序遍历11
（12）继续执行J的逻辑，获取J的右子树，调用inOrder方法，J的右子树为null，方法返回null；至此所有的节点都已判断完成，中序遍历算法的最终结果为：HKDBEAIFCGJ。
中序遍历12
3.后序遍历算法
先来看代码
/**
* 二叉树的后续遍历算法
* 1.判断节点为空，返回空；
* 2.判断是否存在左子树，如果存在，递归，回到步骤1；
* 3.判断是否存在右子树，如果存在，递归，回到步骤1；
* 4.打印节点数据；
*/
public class PostOrder {
public void postOrder(TreeNode treeNode) {
if (null == treeNode) {
return;
}
TreeNode leftNode = treeNode.getLeft();
postOrder(leftNode);
TreeNode rightNode = treeNode.getRight();
postOrder(rightNode);
System.out.print(treeNode.getValue());
}
}
测试代码
public class Test {
public static void main(String[] args) {
TreeNode[] treeNode = InitTree.initTree();
PostOrder postOrder = new PostOrder();
postOrder.postOrder(treeNode[0]);
}
}
运行结果：KHDEBIFJGCA
程序是如何运行的？
（1）调用postOrder方法，传入的根节点A不为null，获取到A的左子树B；调用postOrder方法，B不为null，获取到B的左子树D；调用postOrder方法，D不为null，获取到D的左子树H；调用postOrder方法，H不为null，获取H的左子树；调用postOrder方法，H的左子树为null，方法返回null；继续执行H的逻辑，获取到H的右子树K；调用postOrder方法，K不为null，获取K的左子树；调用postOrder方法，K的左子树为null，方法返回null；继续执行K的逻辑，获取K的右子树，K的右子树为null，方法返回null；打印K节点的值K，结果K；
后序遍历1
（2）继续执行H的逻辑，打印H节点的值H，结果KH；
后序遍历2
（3）继续执行D的逻辑，获取D的右子树，D的右子树为null，方法返回null；打印D节点的值D，结果KHD；
后序遍历3
（4）继续执行B的逻辑，获取到B的右子树E；调用postOrder方法，E不为null，获取E的左子树；调用postOrder方法，E的左子树为null，方法返回null；继续执行E的逻辑，获取E的右子树，E的右子树为null，方法返回null；打印E节点的值E，结果KHDE；
后序遍历4
（5）继续执行B的逻辑，打印B节点的值B，结果KHDEB；
后序遍历5
（6）继续执行A的逻辑，获取到A的右子树C；调用postOrder方法，C不为null，获取到C的左子树F；调用postOrder方法，F不为null，获取到F的左子树I；调用postOrder方法，I不为null，获取I的左子树；调用postOrder方法，I的左子树为null，方法返回null；继续执行I的逻辑，获取I的右子树，I的右子树为null，方法返回null；打印I节点的值I，结果KHDEBI；
后序遍历6
（7）继续执行F的逻辑，获取F的右子树，F的右子树为null，方法返回null；打印F节点的值F，结果KHDEBIF；
后序遍历7
（8）继续执行C的逻辑，获取到C的右子树G；调用postOrder方法，G不为null，获取G的左子树；调用postOrder方法，G的左子树为null，方法返回null；继续执行G的逻辑，获取到G的右子树J；调用postOrder方法，J不为null，获取J的左子树；调用postOrder方法，J的左子树为null，方法返回null；继续执行J的逻辑，获取J的右子树，J的右子树为null，方法返回null；打印J节点的值J，结果KHDEBIFJ；
后序遍历8
（9）继续执行G的逻辑，打印G节点的值G，结果KHDEBIFJG；
后序遍历9
（10）继续执行C的逻辑，打印C节点的值C，结果KHDEBIFJGC；
后序遍历10
（11）继续执行A的逻辑，打印A节点的值A，结果KHDEBIFJGCA；
后序遍历11
（12）至此所有的节点都已判断完成，后序遍历算法的最终结果为：KHDEBIFJGCA。
后序遍历12
4.层序遍历算法
先来看代码
/**
* 二叉树的层序遍历算法
* 1.判断节点为空，返回空；
* 2.否则按照节点从上到下，从左到右的顺序遍历节点信息；
*/
public class FloorOrder {
public void floorOrder(TreeNode treeNode) {
if (null == treeNode) {
return;
}
LinkedList<TreeNode> list = new LinkedList<TreeNode>();
list.add(treeNode);
TreeNode pollTree;
while (!list.isEmpty()) {
pollTree = list.poll();
System.out.print(pollTree.getValue());
TreeNode left = pollTree.getLeft();
if (null != left) {
list.add(left);
}
TreeNode right = pollTree.getRight();
if (null != right) {
list.add(right);
}
}
}
}
测试代码
public class Test {
public static void main(String[] args) {
TreeNode[] treeNode = InitTree.initTree();
FloorOrder floorOrder = new FloorOrder();
floorOrder.floorOrder(treeNode[0]);
}
}
运行结果：ABCDEFGHIJK
层序遍历算法其实就是从树的根节点开始，按照从上到下，从左到右的顺序遍历所有节点信息。
