目录
1. 广度优先遍历
1.1 原理
1.2 代码示例
2. 深度优先遍历
2.1 原理
1.2 代码示例
【写在前面】
今天对广度优先遍历和深度优先遍历做了一些了解和汇总，这里做个学习笔记，便于后续深入学习。知识点和思路，参考文章如链接，可直接看原博文：树的广度优先遍历和深度优先遍历，Java实现二叉树的深度优先遍历和广度优先遍历算法示例
1. 广度优先遍历
1.1 原理
英文缩写为BFS，即Breadth FirstSearch。
是以广度为优先的，一层一层搜索下去的，就像病毒感染，扩散性的传播下去。其过程检验来说是对每一层节点依次访问，访问完一层进入下一层，而且每个节点只能访问一次。
广度优先遍历树，需要用到队列（Queue）来存储节点对象, 队列的特点就是先进先出。
先往队列中插入左节点，再插右节点，这样出队就是先左节点后右节点了。
1.2 代码示例
（1）树节点：TreeNode
//树节点
package MySearchMethod;
public class TreeNode{
Integer val;
TreeNode left;
TreeNode right;
public TreeNode(Integer val){
this.val = val;
left = null;
right = null;
}
}
（2）二叉树：BinaryTree
//构建二叉树 package MySearchMethod; public class BinaryTree{ private TreeNode root; BinaryTree(){ root = null; } public void insertTreeNode(Integer val){ if(root == null){ root = new TreeNode(val); return; } TreeNode currentNode = root; while(true){ if(val.compareTo(currentNode.val) > 0){ if(currentNode.right == null){ currentNode.right = new TreeNode(val); break; } currentNode = currentNode.right; }else { if(currentNode.left == null){ currentNode.left = new TreeNode(val); break; } currentNode = currentNode.left; } } } public TreeNode getRoot(){ return root; } }
（3）广度优先遍历：
注：下方遍历方法应该也适用于其他树，不只二叉树。待研究。
package MySearchMethod;
import java.util.linkedList;
import java.util.Queue;
public class BreadthFirstSearch {
public static void main(String[] args){
BinaryTree tree = new BinaryTree<>();
tree.insertTreeNode(35);
tree.insertTreeNode(20);
tree.insertTreeNode(15);
tree.insertTreeNode(16);
tree.insertTreeNode(29);
tree.insertTreeNode(28);
tree.insertTreeNode(30);
tree.insertTreeNode(40);
tree.insertTreeNode(50);
tree.insertTreeNode(45);
tree.insertTreeNode(55);
System.out.println("深度优先算法（非递归）：");
breadthSearch(tree.getRoot());
}
public static void breadthSearch(TreeNode root){
Queue queue = new linkedList();
queue.offer(root);
TreeNode currentNode;
while(!queue.isEmpty()){
currentNode = queue.poll();
System.out.print(currentNode.val + " ");
if(currentNode.left != null){
queue.offer(currentNode.left);
}
if(currentNode.right != queue){
queue.offer(currentNode.right);
}
}
}
}
遍历结果：
有一个空指针异常的报错，还没找到原因。待补。
深度优先算法（非递归）： 35 20 40 15 29 50 16 28 30 45 55 Exception in thread "main" java.lang.NullPointerException at MySearchMethod.BreadthFirstSearch.breadthSearch(BreadthFirstSearch.java:37) at MySearchMethod.BreadthFirstSearch.main(BreadthFirstSearch.java:27) Process finished with exit code 1
2. 深度优先遍历
2.1 原理
英文缩写为DFS，即Depth First Search。
其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
深度优先遍历各个节点，需要使用到栈（Stack）这种数据结构。stack的特点是是先进后出。整个遍历过程如下：先往栈中压入右节点，再压左节点，这样出栈就是先左节点后右节点了。
对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。要特别注意的是，二叉树的深度优先遍历比较特殊，可以细分为先序遍历、中序遍历、后序遍历。
这里先演示先序遍历的情况。
1.2 代码示例（1）树节点：TreeNode。 如上，略。
（2）二叉树：BinaryTree。如上，略。
（3）深度优先遍历：
注：这里先演示先序遍历的情况。其他情况待补。
package MySearchMethod;
import java.util.Stack;
public class DepthFirstSearch {
public static void main(String[] args){
BinaryTree tree = new BinaryTree<>();
tree.insertTreeNode(35);
tree.insertTreeNode(20);
tree.insertTreeNode(15);
tree.insertTreeNode(16);
tree.insertTreeNode(29);
tree.insertTreeNode(28);
tree.insertTreeNode(30);
tree.insertTreeNode(40);
tree.insertTreeNode(50);
tree.insertTreeNode(45);
tree.insertTreeNode(55);
System.out.println("深度优先算法之先序遍历（非递归）：");
depthSearch(tree.getRoot());
}
public static void depthSearch(TreeNode root){
Stack stack = new Stack();
stack.push(root);
TreeNode currentNode;
while (!stack.isEmpty()){
currentNode = stack.pop();
System.out.print(currentNode.val + " ");
if(currentNode.right != null){
stack.push(currentNode.right);
}
if(currentNode.left != null){
stack.push(currentNode.left);
}
}
}
}
遍历结果：
深度优先算法之先序遍历（非递归）： 35 20 15 16 29 28 30 40 50 45 55 Process finished with exit code 0
