前端算法之与数据结构-广度遍历和深度遍历与二叉树遍历
- 2019 年 10 月 3 日
- 筆記
一、（图的遍历）深度优先和广度优先
广度优先搜索（BFS）队列实现
–类似二叉树的先序遍历
越是接近根结点的结点将越早地遍历。
找到从起始结点到目标结点的路径，特别是最短路径。
广度优先遍历 BFS 从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。 如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。
/* 广度遍历dom */ //非递归版本 //新建队列和nodes列表 //队列不为空，取出第一个元素，push进nodes，循环添加children进队列 //返回nodes let breadthTraversal = (node) =>{ let nodes = [] let queue = [] if(node){ queue.push(node) while(queue.length){ let item = queue.shift() let children = item.children nodes.push(item) // 队列，先进先出 // nodes = [] queue= [parent] // nodes = [parent] queue= [child1,child2,child3] // nodes = [parent, child1] queue= [child2,child3,child1-1,child1-2] for(let i = 0;i<children.length;i++){ queue.push(children[i]) } } } return nodes }
深度优先搜索（DFS）栈实现
–类似二叉树的层次遍历
更早访问的结点可能不是更靠近根结点的结点。
因此，你在DFS 中找到的第一条路径可能不是最短路径。
假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
/* 深度遍历dom */ //非递归版本 let deepTraversal = (node) => { let stack = [] let nodes = [] if (node) { // 推入当前处理的node stack.push(node) while (stack.length) { let item = stack.pop() let children = item.children nodes.push(item) // node = [] stack = [parent] // node = [parent] stack = [child3,child2,child1] // node = [parent, child1] stack = [child3,child2,child1-2,child1-1] // node = [parent, child1-1] stack = [child3,child2,child1-2] for (let i = children.length - 1; i >= 0; i--) { stack.push(children[i]) } } } return nodes } //递归版本 let deepTraversal1 = (node) => { let nodes =[] if(node!== null) { nodes.push(node) let children = node.children; for(let i = 0;i<children.length;i++){ nodes = nodes.concat(deepTraversal(children[i])) } } return nodes; } let parent = document.querySelector('.parent'); let joe = deepTraversal(parent); console.log(joe);
应用：搜索某个结点的路径，添加path属性（bfs使用shift(队列)，dfs使用pop(栈)）
· bfs利用队列实现，循环中做的是push => shift => push => shift
· dfs利用栈实现，循环中做的是push => pop => push => pop
/* 查找对应name路径 广度遍历 队列实现 bfs */ function bfs(target, name) { const queue = [...target] do { const current = queue.shift() if (current.children) { queue.push(...current.children.map(x => ({ ...x, path: (current.path || current.name) + '-' + x.name }))) } if (current.name === name) { return current//返回整个目标对象 } } while(queue.length) return undefined }
/* 查找对应name路径 深度遍历 栈实现 dfs */ function dfs(target,name){ const stack = [...target] do{ const current = stack.pop() if(current.children){ stack.push(...current.children.map(x => ({...x,path:(current.path || current.name) + '-' + x.name}))) } if(current.name === name){ return current.path//返回整个目标对象的path属性 } }while(stack.length) return undefined }
/* 公共的搜索方法，mode默认bfs */ function commonSearch(target, name, mode) { const stackOrQueue = [...target] do { const current = stackOrQueue[mode === 'dfs' ? 'pop' : 'shift']() if (current.children) { stackOrQueue.push(...current.children.map(x => ({ ...x, path: (current.path || current.name) + '-' + x.name }))) } if (current.name === name) { return current } } while(stackOrQueue.length) return undefined }
/* 搜索地区测试用例 */ const data = [{ id: '1', name: '广东省', children: [ { id: '12', name: '广州市', children: [ { id:'121', name: '天河区' }, { id:'122', name: '荔湾区' } ] } ] }] console.log(dfs(data,'天河区'))
· 结果1：返回对象
· 结果2：返回对象的path属性
二、（二叉树的遍历）前序中序后序
重点中的重点，最好同时掌握递归和非递归版本。
递归版本很容易书写，但是真正考察基本功的是非递归版本。
· 二叉树的前序遍历（根节点N在左右子树前）NLR – ABDECF
· 二叉树的中序遍历（根节点N在左右子树中）LNR – DBEAFC
· 二叉树的后序遍历（根节点N在左右子树后）LRN – DEBFCA
/* 递归写法 */ /* 前序 */ const preorderTraversal = function (root, array=[]) { if(root) { array.push(root.val); preorderTraversal(root.left, array); preorderTraversal(root.right, array); } return array; } /* 中序 */ const inorderTraversal = function(root, array= []) { if(root) { inorderTraversal(root.left, array); array.push(root.val); inorderTraversal(root.right, array); } return array; } /* 后序 */ const postorderTraversal = function(root, array = []) { if(root){ postorderTraversal(root.left, array); postorderTraversal(root.right, array); array.push(root.val); } return array; } /* 非递归写法 */ /* 前序 */ const preorderTraversal1 = function (root) { const result = []; const stack = []; let current = root; while(current||stack.length > 0){ while(current){ //取根节点值，左节点入栈，循环到左节点为空 result.push(current.val); stack.push(current); current = current.left; } //节点出栈，再遍历右节点 current = stack.pop(); current = current.right; } return result; } /* 中序 */ const inorderTraversal1 = function (root) { const result = []; const stack = []; let current = root; while(current||stack.length > 0){ while(current){ //左节点入栈，循环到左节点为空 stack.push(current); current = current.left; } //节点出栈，取节点值，再遍历右节点 current = stack.pop(); result.push(current.val); current = current.right; } return result; } /* 后序 */ const postorderTraversal1 = function (root) { const result = []; const stack = []; let last = null; let current = root; while(current || stack.length > 0) { while(current) { //左节点入栈，循环到左节点为空 stack.push(current); current = current.left; } //取栈内最后一个节点，判断是为空或者已遍历过，则将节点值传入 current = stack[stack.length-1]; if(!current.right || current.right == last){ //节点出栈 current = stack.pop(); result.push(current.val); last = current; current = null; //继续循环弹栈 } else { //取右节点做遍历操作 current = current.right } } return result; } /* 测试用例 */ const data = { val:1, left:{ val:2, left:{ val:4, }, right:{ val:5 } }, right:{ val:3, left:{ val:6 }, right:{ val:7 } } } console.log('递归计算结果') console.log(preorderTraversal(data)) console.log(inorderTraversal(data)) console.log(postorderTraversal(data)) console.log('非递归计算结果') console.log(preorderTraversal1(data)) console.log(inorderTraversal1(data)) console.log(postorderTraversal1(data)) //递归计算结果 [ 1, 2, 4, 5, 3, 6, 7 ] [ 4, 2, 5, 1, 6, 3, 7 ] [ 4, 5, 2, 6, 7, 3, 1 ] //非递归计算结果 [ 1, 2, 4, 5, 3, 6, 7 ] [ 4, 2, 5, 1, 6, 3, 7 ] [ 4, 5, 2, 6, 7, 3, 1 ]
