什么是深度优先遍历和广度优先遍历
如题。
参考文章：
https://blog.csdn.net/weixin_42289193/article/details/81741756
https://blog.csdn.net/qq_15020543/article/details/84328609
深度优先遍历和广度优先遍历，既可以应用到树的遍历中，也可以用到图的遍历中。代码实现上，只考虑树的实现，因为比较简单一些。
什么是深度优先遍历？
对一个起始节点进行访问，然后访问该节点的某一个子节点，再继续访问该子节点的子节点，直到没有可访问的节点，再回溯，依次访问其他子节点。
图
图的遍历：默认右手边的元素为优先访问的元素。
访问 1
访问 1的子节点 2. （虽然有其他6和5 子节点，但是优先访问右手边元素，2在右手边）
访问 2的子节点 3. （虽然有6，但是3在右手边）
访问 3的子节点 4.
访问 4的子节点 5
访问 5的子节点 1（但是 1 已经访问过。）
查看 5 是否有其他未被访问的子节点，没有。 进行回溯至 4.
查看 4 是否有其他未被访问的子节点，没有。进行回溯至 3.
查看 3 是否有其他未被访问的子节点，有， 是6.
访问 3的子节点 6.
访问 6的子节点，无。 回溯至 3.
查看 3 是否有其他未被访问的子节点，没有。进行回溯至 2.
查看 2 是否有其他未被访问的子节点，没有。回溯至 1.
查看 1 是否有其他未被访问的子节点，没有。 结束。
树
树的深度优先遍历
1，2，4，5，3，6
什么是广度优先遍历？
图
访问一个节点的所有子节点，然后再依次访问子节点的所有子节点。类似于树的层次遍历。
依然以上图为示例。
访问 1
访问 1 的所有子节点， 2，6.
访问 2 的所有子节点， 3，（6已经被访问过）
访问 6的 所有子节点，无。
访问 3的子节点，4 （6已经被访问过）
访问 4的子节点 5
访问 5的子节点 6 （无）。
没有待访问的子节点，结束。
树
树的广度优先遍历，其实就是层次遍历
1，2，3，4，5，6
代码实现
以二叉树来举例。
public class TreeNode {
int node;
TreeNode leftChild = null;
TreeNode rightChild = null;
public TreeNode(int node){
this.node = node;
}
public int getNode() {
return node;
}
public void setNode(int node) {
this.node = node;
}
public TreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(TreeNode leftChild) {
this.leftChild = leftChild;
}
public TreeNode getRightChild() {
return rightChild;
}
public void setRightChild(TreeNode rightChild) {
this.rightChild = rightChild;
}
}
深度优先遍历
public static void depthFirstSearch(TreeNode root){
if (root == null){
return;
}
Stack<TreeNode> tempNodes = new Stack<>();
tempNodes.push(root);
while (tempNodes.size() > 0){
TreeNode theOne = tempNodes.pop();
System.out.println(theOne.getNode());
if (theOne.getRightChild() != null){
tempNodes.push(theOne.getRightChild());
}
if (theOne.getLeftChild() != null){
tempNodes.push(theOne.getLeftChild());
}
}
}
广度优先遍历
//广度优先遍历，层次遍历
public static void broadFirstSearch(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> tempNodes = new LinkedList<>();
tempNodes.offer(root);
while (tempNodes.size() > 0) {
TreeNode one = tempNodes.poll();
System.out.println(one.getNode());
if (one.getLeftChild() != null) {
tempNodes.offer(one.getLeftChild());
}
if (one.getRightChild() != null) {
tempNodes.offer(one.getRightChild());
}
}
}
