二叉树的遍历的三种方式
1.前序遍历；
先访问根结点，然后再访问左子树，最后访问右子树
2.中序遍历；
先访问左子树，中间访问根节点，最后访问右子树
3.后序遍历；
先访问左子树，再访问右子树，最后访问根节点
如果我们分别对下面的树使用三种遍历方式进行遍历，得到的结果如下：
前序遍历
前序遍历的API：
public Queue preErgodic()：使用前序遍历，获取整个树中的所有键
private void preErgodic(Node x,Queue keys)：使用前序遍历，把指定树x中的所有键放入到keys队列中
实现步骤：
1.把当前结点的key放入到队列中;
2.找到当前结点的左子树，如果不为空，递归遍历左子树
3.找到当前结点的右子树，如果不为空，递归遍历右子树
代码实现：
//使用前序遍历，获取整个树中的所有键
public Queue<Key> preErgodic(){Queue<Key> keys = new Queue<>();preErgodic(root,keys);return keys;
}
//使用前序遍历，把指定树x中的所有键放入到keys队列中
private void preErgodic(Node x,Queue<Key> keys){if (x==null){return;
}//1.把当前结点的key放入到队列中;keys.enqueue(x.key);//2.找到当前结点的左子树，如果不为空，递归遍历左子树if (x.left!=null){preErgodic(x.left,keys);}//3.找到当前结点的右子树，如果不为空，递归遍历右子树if (x.right!=null){preErgodic(x.right,keys);}
}//测试代码public class Test {public static void main(String[] args) throws Exception {BinaryTree<String, String> bt = new BinaryTree<>();bt.put("E", "5");bt.put("B", "2");bt.put("G", "7");bt.put("A", "1");bt.put("D", "4");bt.put("F", "6");bt.put("H", "8");bt.put("C", "3");Queue<String> queue = bt.preErgodic();for (String key : queue) {System.out.println(key+"="+bt.get(key));}}
}
运行结果：
5=E
2=B
1=A
4=D
3=C
7=G
6=F
8=H
中序遍历
前序遍历的API：
public Queue midErgodic()：使用中序遍历，获取整个树中的所有键
private void midErgodic(Node x,Queue keys)：使用中序遍历，把指定树x中的所有键放入到keys队列中
实现步骤：
1.找到当前结点的左子树，如果不为空，递归遍历左子树
2.把当前结点的key放入到队列中;
3.找到当前结点的右子树，如果不为空，递归遍历右子树
代码实现：
//使用中序遍历，获取整个树中的所有键public Queue<Key> midErgodic(){Queue<Key> keys = new Queue<>();midErgodic(root,keys);return keys;}//使用中序遍历，把指定树x中的所有键放入到keys队列中private void midErgodic(Node x,Queue<Key> keys){if (x==null){return;}//1.找到当前结点的左子树，如果不为空，递归遍历左子树if (x.left!=null){midErgodic(x.left,keys);}//2.把当前结点的key放入到队列中;keys.enqueue(x.key);//3.找到当前结点的右子树，如果不为空，递归遍历右子树if (x.right!=null){midErgodic(x.right,keys);}
}
//测试代码
public class Test {public static void main(String[] args) throws Exception {BinaryTree<String, String> bt = new BinaryTree<>();bt.put("E", "5");bt.put("B", "2");bt.put("G", "7");bt.put("A", "1");bt.put("D", "4");bt.put("F", "6");bt.put("H", "8");bt.put("C", "3");Queue<String> queue = bt.midErgodic();for (String key : queue) {System.out.println(key+"="+bt.get(key));}}
}
运行结果：
1=A
2=B
3=C
4=D
5=E
6=F
7=G
8=H
后序遍历
后序遍历的API：
public Queue afterErgodic()：使用后序遍历，获取整个树中的所有键
private void afterErgodic(Node x,Queue keys)：使用后序遍历，把指定树x中的所有键放入到keys队列中
实现步骤：
1.找到当前结点的左子树，如果不为空，递归遍历左子树
2.找到当前结点的右子树，如果不为空，递归遍历右子树
3.把当前结点的key放入到队列中;
代码实现：
//使用后序遍历，获取整个树中的所有键
public Queue<Key> afterErgodic(){Queue<Key> keys = new Queue<>();afterErgodic(root,keys);return keys;
}
//使用后序遍历，把指定树x中的所有键放入到keys队列中
private void afterErgodic(Node x,Queue<Key> keys){if (x==null){return;
}
//1.找到当前结点的左子树，如果不为空，递归遍历左子树
if (x.left!=null){afterErgodic(x.left,keys);
}
//2.找到当前结点的右子树，如果不为空，递归遍历右子树
if (x.right!=null){afterErgodic(x.right,keys);
}
//3.把当前结点的key放入到队列中;
keys.enqueue(x.key);
}
//测试代码
public class Test {
public static void main(String[] args) throws Exception {BinaryTree<String, String> bt = new BinaryTree<>();bt.put("E", "5");bt.put("B", "2");bt.put("G", "7");bt.put("A", "1");bt.put("D", "4");bt.put("F", "6");bt.put("H", "8");bt.put("C", "3");Queue<String> queue = bt.afterErgodic();for (String key : queue) {System.out.println(key+"="+bt.get(key));}
}
}
运行结果：
1=A
3=C
4=D
2=B
6=F
8=H
7=G
5=E
二叉树的层序遍历
所谓的层序遍历，就是从根节点（第一层）开始，依次向下，获取每一层所有结点的值，有二叉树如下：
那么层序遍历的结果是：EBGADFHC
层序遍历的API：
public Queue layerErgodic()：使用层序遍历，获取整个树中的所有键
实现步骤：
1.创建队列，存储每一层的结点；
2.使用循环从队列中弹出一个结点：
2.1获取当前结点的key；
2.2如果当前结点的左子结点不为空，则把左子结点放入到队列中
2.3如果当前结点的右子结点不为空，则把右子结点放入到队列中
代码：
//使用层序遍历得到树中所有的键
public Queue<Key> layerErgodic(){Queue<Key> keys = new Queue<>();Queue<Node> nodes = new Queue<>();nodes.enqueue(root);while(!nodes.isEmpty()){Node x = nodes.dequeue();keys.enqueue(x.key);if (x.left!=null){nodes.enqueue(x.left);}if (x.right!=null){nodes.enqueue(x.right);}}
}
//测试代码
public class Test {
public static void main(String[] args) throws Exception {BinaryTree<String, String> bt = new BinaryTree<>();bt.put("E", "5");bt.put("B", "2");bt.put("G", "7");bt.put("A", "1");bt.put("D", "4");bt.put("F", "6");bt.put("H", "8");bt.put("C", "3");Queue<String> queue = bt.layerErgodic();for (String key : queue) {System.out.println(key+"="+bt.get(key));}
}
}
结果：
5=E
2=B
7=G
1=A
4=D
6=F
8=H
3=C参考：黑马程序员Java数据结构与java算法全套教程
