五、二叉树的基础遍历
很多情况下，我们可能需要像遍历数组数组一样，遍历树，从而拿出树中存储的每一个元素，由于树状结构和线性结构不一样，它没有办法从头开始依次向后遍历，所以存在如何遍历，也就是按照什么样的搜索路径进行遍历的问题
我们把树简单的画作上图中的样子，由一个根节点、一个左子树、一个右子树组成，那么按照根节点什么时候被访
问，我们可以把二叉树的遍历分为以下三种方式：
1.前序遍历；
先访问根结点，然后再访问左子树，最后访问右子树
2.中序遍历；
先访问左子树，中间访问根节点，最后访问右子树
3.后序遍历；
先访问左子树，再访问右子树，最后访问根节点
如果我们分别对下面的树使用三种遍历方式进行遍历，得到的结果如下：
5.1.前序遍历
我们在4.4中创建的树上，添加前序遍历的API：
public Queue<Key> preErgodic() ：使用前序遍历，获取整个树中的所有键
private void preErgodic(Node x,Queue<Key> 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.2.中序遍历
我们在4.4中创建的树上，添加前序遍历的API：
public Queue<Key> midErgodic() ：使用中序遍历，获取整个树中的所有键
private void midErgodic(Node x,Queue<Key> 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)); } } }
5.3.后序遍历
我们在4.4中创建的树上，添加前序遍历的API：
public Queue<Key> afterErgodic() ：使用后序遍历，获取整个树中的所有键
private void afterErgodic(Node x,Queue<Key> 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)); } } }
六、二叉树的层序遍历
所谓的层序遍历，就是从根节点（第一层）开始，依次向下，获取每一层所有结点的值，有二叉树如下：
那么层序遍历的结果是： EBGADFHC
我们在4.4中创建的树上，添加层序遍历的API：
public Queue<Key> 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); } } return 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.layerErgodic(); for (String key : queue) { System.out.println(key+"="+bt.get(key)); } } }
