前言数据结构与算法系列（完成篇）：时间复杂度与空间复杂度分析数组的基本实现以及特征链表与跳表与特征栈的基本实现,队列、优先级队列、双端队列的实现及特点哈希表、映射、集合及特征树、二叉树、二叉查找树的实现及特征堆及二叉堆的实现及特征图的实现及特征递归分治法的实现、特点和思考点，回溯的实现和深度优先搜索的实现，广度优先搜索的实现和特征贪心算法的实现，特征二分查找的实现和特征的实现动态程序amming和关键点的基本实现Tiretreeunionsearchandset的基本实现，特征剪枝的实现，特征双向BFS的实现，特征启发式搜索的实现，特征AVL树和红黑树的实现,以及特征位操作Bloomfilter的基础和实践要点LRUCache的实现和应用以及初级排序和高级排序和特征串算法的应用PS：大部分已经在公众号或者GitHub上完成了，以后会补上在标题中（不允许外部链接）。本文讨论深度优先搜索和广度优先搜索。关于搜索&遍历对于搜索，大多数情况下我们处理的是“所谓的暴力搜索”，或者说是比较简单的搜索，也就是说你在搜索的时候没有任何所谓的智能情况在里面考虑。很多时候，它做的一件事就是遍历所有节点一次，然后找到你想要的结果。基于这样的数据结构，如果数据结构本身没有特征，也就是说，它是一个很普通的树或者很普通的图。那么我们要做的一件事就是遍历所有的节点。同时保证每个点都访问一次且只访问一次，最后找到结果。那么我们先从整体上简化搜索，缩小到树的情况下搜索。如果我们想找到一个我们需要的值，我们在这棵树中做什么呢？那么毫无疑问就是从根开始，先搜索左子树，然后一个一个的去下一个点，走完之后再去右子树，直到找到我们的点，这就是我们使用的方式.回到我们的数据结构定义，它只有一个左子树和一个右子树。如果我们要实现这样的遍历或者查找，毫无疑问，我们要保证的是每个节点都必须被访问一次，每个节点只需要被访问一次。节点访问的顺序不受限制。DepthFirst:深度优先搜索BreadthPriority:BreadthFirstSearchonlyvisitsonce就是我们在搜索，我们不想做太多无用的访问，否则我们访问的效率会很慢。当然还可以有其他的搜索，剩下的搜索不再是深度优先或者广度优先，而是按照优先级排序。当然你也可以随意定义，比如从中间优先考虑其他的东西，但是定义的话，必须要有逼真的场景。所以你可以把它理解为深度优先、广度优先或优先级优先。按优先级搜索其实更适用于现实中的很多业务场景，而这样的算法一般被称为启发式搜索，在深度学习领域应用较多。而这种优先级，例如，已经在很多情况下应用到各种推荐算法和高级搜索算法中，让你找出自己最感兴趣的内容，每天打开抖音、快手我会推荐你??最感兴趣的内容，其实就是这个道理。深度优先搜索（DFS）递归写法递归写法一开始就是递归的终止条件，然后处理当前层，然后往下走。那么处理当前层就相当于访问了node节点，然后把这个node节点加入到访问过的节点中；那么终止条件就是如果之前访问过该节点，则无所谓；然后，如果你拒绝，你会去它的子节点。对于二叉树来说，就是左孩子和右孩子。如果是图，就是相邻节点在一起。如果是多叉树，这个就是一个孩子，然后把所有孩子的话都遍历一次。1.二叉树模型版Java版本//C/C++//递归写法：mapvisited;voiddfs(Node*root){//terminatorif(!root)return;if(visited.count(root->val)){//alreadyvisitedreturn;}visited[root->val]=1;//processcurrentnodehere.//...for(inti=0;ichildren.size();++i){dfs(root->children[i]);}return;}Python版本#Pythonvisited=set()defdfs(node,visited):ifnodeinvisited:#terminator#alreadyvisitedreturnvisited.add(node)#processcurrentnodehere....fornext_nodeinnode.children():ifnext_nodenotinvisited:dfs(next_node,visited)C/C++版本//C/C++//递归写法：mapvisited;voiddfs(Node*root){//terminatorif(!root)return;if(visited.count(root->val)){//alreadyvisitedreturn;}visited[root->val]=1;//processcurrentnodehere.//...for(inti=0;ichildren.size();++i){dfs(root->children[i]);}return;}JavaScript版本visited=set()defdfs(node,visited):ifnodeinvisited:#terminator#alreadyvisitedreturnvisited.add(node)#processcurrentnodehere。...fornext_nodeinnode.children():ifnext_nodenotinvisited:dfs(next_node,visited)2.多叉树模板visited=set()defdfs(node,visited):ifnodeinvisited:#terminator#alreadyvisitedreturnvisited.add(node)#processcurrentnodehere....fornext_nodeinnode。children():ifnext_nodenotinvisited:dfs(next_node,visited)非递归写Python版#PythondefDFS(self,tree):iftree.rootisNone:return[]visited,stack=[],[tree.root]whilestack:node=stack.pop()visited.add(node)process(node)nodes=generate_related_nodes(node)stack.push(nodes)#otherprocessingwork...C/C++版本//C/C++//非递归写法：voiddfs(Node*root){mapvisited;if(!root)return;stackstackNode;stackNode.push(root);while(!stackNode.empty()){Node*node=stackNode.top();stackNode.pop();if(visited.count(node->val))continue;visited[node->val]=1;for(inti=node->children.size()-1;i>=0;--i){stackNode.push(node->children[i]);}}return;}遍历顺序如果我们看深度优先搜索或者深度优先遍历，它的整个遍历顺序无疑是根节点1是总是从第一个开始，到那个分支的下一步其实是一样的。为了简单起见，我们从最左边开始，如果是深度优先，就走到最后。参考多叉树模板，我们可以在脑海中递归或者画图，画出递归状态树，就是这样一个结构。比如一开始进来的，如果是root，那么root会放在visitedfirst，说明root已经被访问过，访问完之后会从root.childern中找到next_node，以及它的所有next_nodes没有被访问过。它已经过去了，所以它会先访问最左边的节点。这里注意，先取出最左边的节点时，判断为未访问过，因为除了root以外的其他节点都没有访问过。如果没有就直接调整dfs，next_node就是把最左边的节点放进去，然后把visited放在一起。递归调用的一个特点，它不会等待循环结束，直接进入下一层，也就是在当前的梦境中，这里写了一个循环，但是循环在第一层的时候，我将开始Drilldowntoanewlevelofdreamland。图的遍历顺序是breadth-firstsearch(BFS)广度优先遍历，不再使用递归或栈，而是使用所谓的队列。你可以把它想象成一滴水，它滴到1的位置，然后它的水波纹一层层散开。两种BFS代码模板对比//JavapublicclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(intx){val=x;}}publicList>levelOrder(TreeNoderoot){List>allResults=newArrayList<>();if(root==null){returnallResults;}Queuenodes=newLinkedList<>();nodes.add(root);while(!nodes.isEmpty()){intsize=nodes.size();Listresults=newArrayList<>();for(inti=0;i已访问；if(!root)return;queuequeueNode;queueNode.push(root);while(!queueNode.empty()){Node*node=queueNode.top();queueNode.pop();if(visited.count(node->val))continue;visited[node->val]=1;for(inti=0;ichildren.size();++i){queueNode.push(node->children[i]);}}return;}//JavaScriptconstbfs=(root)=>{letresult=[],queue=[root]while(queue.length>0){letlevel=[],n=queue.lengthfor(leti=0;i
