先序遍历:对于每一棵子树，都是先打印头节点，再打印左子节点，再打印右子节点。
中序遍历:对于每一棵子树，都是先打印左子节点，再打印头节点，再打印右子节点。
后序遍历:对于每一棵子树，都是先打印左子节点，再打印右子节点，再打印头节点。
举例：在如下图所示二叉树中
递归方法打印整棵树:1，2，4，4，4，2，5，5，5，2，1，3，6，6，6，3，7，7，7，3，1
先序遍历:在递归打印整棵树中，只在每个节点出现的第一次时打印：1,2,4,5,3,6,7
中序遍历:在递归打印整棵树中，只在每个节点出现的第二次时打印：4,2,5,1,6,3,7
后序遍历:在递归打印整棵树中，只在每个节点出现的第三次时打印：4,5,2,6,7,3,1
宽度优先遍历:在以上二叉树中，第一层只有一个节点1，所以第一层的宽度是1；第二层有节点2和3，所以第二层宽度是2；第三层节点有4，5，6，7，所以宽度为4，依此类推；在上图的二叉树中宽度优先遍历就是从上到下顺序遍历。
以下为各个方法的代码实现，注释已写：
public class PreInPosTraversal {
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
//递归方法打印整棵二叉树,每次到执行到的节点都打印
public static void f(Node head) { //传入头节点
if(head == null) {
return;
}
//1
f(head.left); //左边递归遍历
//2
f(head.right); //右边递归遍历
//3
}
//递归方法实现先序遍历，只在第一次来到自己的时候打印head.value
public static void preOrderRecur(Node head) {
if(head == null) {
return;
}
System.out.println(head.value + " ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
//递归方法实现中序遍历，只在第二次来到自己的时候打印head.value
public static void inOrderRecur(Node head) {
if(head == null) {
return;
}
inOrderRecur(head.left);
System.out.println(head.value + " ");
inOrderRecur(head.right);
}
//递归方法实现后序遍历，只在最后一次来到自己的时候打印
public static void posOrderRecur(Node head) {
if(head == null) {
return;
}
posOrderRecur(head.left);
posOrderRecur(head.right);
System.out.println(head.value + " ");
}
//非递归序实现先序遍历
//1.每次先从栈中弹出一个节点cur
//2.打印弹出的cur
//3.先把右节点压入栈中，再将左节点压入栈中(如果有的话)
//4.周而复始
//例如在我的树中为:1,2,3,4,5,6,7,栈中有1这个节点,将1弹出打印,此时先压右再压左(相当于一个瓶子,先把右边的节点放进去,再把左边的放进去,弹出的话先弹后放进瓶子的),
//将3和2压入栈中,将2弹出,再将2的子节点的先右后左放进瓶子(此时瓶子从上到下依次是4,5,3),再将4弹出,此时4无子节点则什么也不做,再将5弹出,先压右再压左,但是5没有子节点
//则什么也不做,再将3弹出,先压右再压左,将7和6放进瓶子,弹出6,但是6没有子节点则什么都不做,再弹出7,7没有子节点也什么都不做
//结果:1,2,4,5,3,6,7
public static void posOrderUnRecur(Node head) {
System.out.println("pre-order: ");
if(head != null) {
Stack stack = new Stack();
stack.add(head); //先将头节点压入栈中
while(!stack.isEmpty()) { //只要栈不是空的
head = stack.pop(); //从栈中弹出一个节点
System.out.println(head.value + " ");
if(head.right != null) { //右如果不是空
stack.push(head.right); //将右节点压入栈中
}
if(head.left != null) { //左如果不等于空
stack.push(head.left); //再将左压入栈中
}
}
}
System.out.println();
}
//非递归实现后序遍历
//1.弹出当前节点
//2.把当前节点放到收集栈
//3.先压左再压右
//4.周而复始
//正常是先将头节点弹出,再将右节点弹出,再将左节点弹出,而按照此顺序放到收集栈再打印,相当于收集栈的逆序,先左,再右,再头打印
//例如在我的树中为:1,2,3,4,5,6,7,栈中有1这个节点,将1弹出放到收集栈,此时先压左再压右,瓶子中从上到下是3,2,将3放入收集栈,先压左再压右,将6,7放入瓶子,此时
//瓶子从上到下7,6,2,将7弹出到收集栈,7先压左再压右,没有就什么都不做,再将6弹出到收集栈,先压左再压右,没有子节点就什么都不做,再将2弹出到收集栈,县衙左再压右,将4,5
//放进瓶子,两个都没子节点,将两个节点放到收集栈,，先放5再放4
//最后收集栈的值为:4,5,2,6,7,3,1
public static void posOrderUnRecur1(Node head) {
System.out.println("pos-order: ");
if(head!=null) {
Stack s1 = new Stack();
Stack s2 = new Stack();
s1.push(head); //先将头节点压到s1栈中
while(!s1.isEmpty()) {
head = s1.pop(); //弹出当前节点
s2.push(head); //放在s2里面
if(head.left != null) {
s1.push(head.left); //先压左
}
if(head.right != null) {
s1.push(head.right); //再压右
}
}
while(!s2.isEmpty()) {
System.out.println(s2.pop().value + " "); //收集完后再将收集栈里面一个一个打印
}
}
System.out.println();
}
//非递归实现中序遍历
//先左再右再头
//每棵子树,整棵树左边界进栈,依次弹出的过程中,对弹出节点打印,对弹出节点的右树再执行前面的操作(如果有右树的话),周而复始
public static void inOrderUnRecur(Node head) {
System.out.println("in-order");
if(head != null) {
Stack stack = new Stack();
while(!stack.isEmpty() || head != null) { //栈不是空或者头节点不为空周而复始
if(head != null) { //第一个分支在不停的将左边界进栈
stack.push(head);
head = head.left; //head不为空就一直左移
}else { //左边界都进栈了就会来到第二个分支(就是第一个节点到了null的时候)
head = stack.pop(); //弹出的节点被头结点抓住
System.out.println(head.value + " "); //弹出就打印
head = head.right; //然后来到右节点(如果有右树的话继续走逻辑分支一,就是if里面的代码)
}
}
}
System.out.println();
}
//宽度优先遍历
public static void findWidth(Node head) {
if(head == null) {
return;
}
Queue queue = new LinkedList<>(); //双向链表，可做队列
queue.add(head);
while(!queue.isEmpty()) {
Node cur = queue.poll();
System.out.println(cur.value);
if(cur.left != null) {
queue.add(cur.left);
}
if(cur.right != null) {
queue.add(cur.right);
}
}
}
public static void main(String[] args) {
Node head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.left.right = new Node(5);
head.right.left = new Node(6);
head.right.right = new Node(7);
//recursive
System.out.println("=============recursive=============");
System.out.println("pre-order: ");
preOrderRecur(head);
System.out.println();
System.out.println("in-order: ");
inOrderRecur(head);
System.out.println();
System.out.println("pos-order: ");
posOrderRecur(head);
System.out.println();
//unrecursive
System.out.println("=========unrecursive==========");
posOrderUnRecur(head);
inOrderUnRecur(head);
posOrderUnRecur1(head);
System.out.println("=============WidthFirst===============");
findWidth(head);
}
}
以上便是代码实现，如有不明白的小伙伴可以私信留言，或写的不对的地方欢迎大佬指出。
