BFS和DFS的JS实现数据结构与算法

1.深度优先遍历深度优先遍历主要思路是从图中?个未访问的顶点 V 开始，沿着?条路?直?到底，然后从这条路尽头的节点回退到上?个节点，再从另?条路开始?到底…，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先?完?条路，再换?条路继续?。
树是图的?种特例（连通?环的图就是树），接下来我们来看看树?深度优先遍历该怎么遍历。

文章图片

遍历的顺序如下：

文章图片

不难发现这就是树的前序遍历,实际上不管是前序遍历，还是中序遍历，亦或是后序遍历，都属于深度优先遍历。

function Node(value) { this.value = https://www.it610.com/article/value; this.left = null; //左分支指向 this.right = null; //有分支指向 } var a = new Node("A"); var b = new Node("B"); var c = new Node("C"); var d = new Node("D"); var e = new Node("E"); a.left=b; a.right=c; b.left=d; b.right=e; // 递归的方式实现 function deepTravel(tree) { if(!tree){ return; } console.log(tree.value); deepTravel(tree.left); deepTravel(tree.right); } console.log(deepTravel(a)); //递归的表达性很好，也很容易理解，不过如果层级过深，很容易导致栈溢出。 //非递归实现DFS的思路：使?栈来将要遍历的节点压栈，然后出栈后检查此节点是否还有未遍历的节点，有的话压栈，没有的话就出栈。对于每个节点来说，先遍历当前节点，然后把右节点压栈，再压左节点（这样弹栈的时候会先拿到左节点遍历，符合深度优先遍历要求）function deepTravel(tree) { if(!tree){ return; } var stack=[]; stack.push(tree); while(stack.length){ var temp=stack.pop(); console.log(temp); if(temp.right){ stack.push(temp.right); } if(temp.left){ stack.push(temp.left); } } }

【BFS和DFS的JS实现】leetcode习题： leetcode 104: 求树的最?深度、 leetcode 111: 求树的最?深度
2.?度优先遍历 ?度优先遍历，指的是从图的?个未遍历的节点出发，先遍历这个节点的相邻节点，再依遍次历每个相邻节点的相邻节点。?度优先遍历也叫层序
遍历，先遍历第?层（节点 1），再遍历第?层（节点 2，3，4），第三层（5，6，7，8），第四层（9，10）。

文章图片

图中每个节点的值即为它们的遍历顺序。

function Node(value) { this.value = https://www.it610.com/article/value; this.left = null; //左分支指向 this.right = null; //有分支指向 } var a = new Node("A"); var b = new Node("B"); var c = new Node("C"); var d = new Node("D"); var e = new Node("E"); a.left=b; a.right=c; b.left=d; b.right=e; function deepTravel(tree) { if(!tree){ return; } var stack=[]; stack.push(tree); while(stack.length){ var temp=stack.shift(); console.log(temp.value); if(temp.left){ stack.push(temp.left); } if(temp.right){ stack.push(temp.right); }} } console.log(deepTravel(a)); //在?度优先遍历的过程中，把每?层的节点都添加到同?个数组中即可，问题的关键在于遍历同?层节点前，必须先算出同?层的节点有多少，不然由于 BFS ?的是队列来实现的，遍历过程中会不断把左右?节点?队，不事先算出同?层节点的话，会把同?层的左右节点也加到同?层的节点去 var levelOrder = function(root) { var res=[]; var queue =[]; if (root != null) { queue.push(root); } while (queue.length) { var n = queue.length; var level = []; for (var i = 0; i < n; i++) { var node = queue.shift(); level.push(node.val); if (node.left != null) { queue.push(node.left); } if (node.right != null) { queue.push(node.right); } } res.push(level); } return res; }; console.log(levelOrder(a));