-
介绍
1.什么叫做二叉树的遍历？
指沿着某条搜索路线，依次对树中每个结点均做一次且做一次访问。
2.遍历的目的:通过一次完整的遍历，可使二叉树中结点信息由非线性排列变为某种意义上的线性序列
-
遍历方式
前序遍历
访问根结点
先序遍历根的左子树
先序遍历根的右子树
中序遍历
中序遍历根的左子树
访问根结点
中序遍历根的右子树
后序遍历
后序遍历根的左子树
后序遍历根的右子树
访问根结点
层序遍历
按层从上到下，每层从左到右的遍历逻辑
对于如图所示二叉树
前序遍历节点顺序为：ABDGHIKLJCEF
中序遍历节点顺序为：GDKILHJBAECF
后序遍历节点顺序为：GKLIJHDBEFCA
-
源码解析
三种遍历方式皆采用递归
递归需要一个出口跳出（条件判断），不然会一直开辟栈空间执行最终会stack overflow
关键思想：
若节点为空则退出
前序遍历：
private void preorder(Node<E> node, Visitor<E> visitor) {
if (node == null ) return;
System.out.println(node.element);
preorder(node.left);
preorder(node.right);
}
遍历顺序：
根节点，前序遍历左子树，前序遍历右子树
中序遍历：
private void inorder(Node<E> node) {
if (node == null) return;
inorder(node.left);
System.out.println(node.element);
inorder(node.right);
}
遍历顺序：
中序遍历左子树，根节点，中序遍历右子树
后序遍历：
private void postOrder(Node<E> node) {
if (node == null) return;
inorder(node.left);
inorder(node.right);
System.out.println(node.element);
}
遍历顺序：
后序遍历左子树，后序遍历右子树，根节点
层序遍历：
public void levelOrder() {
if (root == null) return;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
if (visitor.visit(node.element)) return;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
每当弹出一个元素时就执行了一次while，队列为空时循环结束，此时所有元素已经按照从上到下，从左至右的顺序 遍历完成
层序遍历也被称为广度优先搜索（BFS）。在层序遍历中，我们从树的根节点开始，逐层地从上到下、从左到右依次访问树的节点。
假设有如下的二叉树结构：
1
/ \
2 3
/ \ \
4 5 6
对于这棵树，层序遍历的结果就是 1 -> 2 -> 3 -> 4 -> 5 -> 6。具体来说，按层序遍历的顺序，首先访问根节点 1，然后按照从左到右的顺序访问第二层的节点 2 和 3，接着按照从左到右的顺序访问第三层的节点 4、5 和 6。
-
个性化需求定制
在对二叉树进行遍历的时候，我们可能会根据情况定制想要的遍历结果
提供一个额外的接口visitor，调用时实现自定义的遍历逻辑
//内部静态接口
public static interface Visitor<E>{
boolean visit(E element);
}
public void preOrder(Node<Integer> node,Visitor<E> visitor){
if(node==null||visitor==true)return;
visitor.visite(node.element);
preOrder(node.left，visitor);
preOrder(node.right,visitor);
}
遍历到的节点值为10时即停止
//外部调用：
public static void main(String[] args){
BST<Integer> bt=new BST<>();
bt.preOrder(new visitor<Integer>(){
public boolean visit(Integer element){
System.out.println(element+"");
return element==10?true:false;
});
}
