浅谈 JavaScript 处理树形结构的几个场景与方案

514 查看

前言

近日，Mac 下著名软件 Homebrew 的作者，因为没解出来二叉树翻转的白板算法题，惨遭 Google 拒绝，继而引发推特热议。

在 JavaScript 中也有很多树形结构。比如 DOM 树，省市区地址联动，文件目录等； JSON 本身就是树形结构。

很多前端面试题也跟树形结构的有关，比如在浏览器端写遍历 DOM 树的函数，比如在 nodejs 运行时遍历文件目录等。

这里演示用 JavaScript 遍历树形结构的几种策略。

场景1：遍历 DOM 树

方案1：递归模式

function walkDom(node, callback) {

if (node === null) { //判断node是否为null

return

}

callback(node) //将node自身传入callback

node = node.firstElementChild //改变node为其子元素节点

while (node) {

walkDom(node, callback) //如果存在子元素，则递归调用walkDom

node = node.nextElementSibling //从头到尾遍历元素节点

}

walkDom(document, function(node) {console.count()}) //包含document节点

document.querySelectorAll('*').length //数量比上面输出的少1，因为不包含document节点

将上述代码黏贴到任意页面的控制台 console 中执行。

方案2：循环模式

function walkDom(node, callback) {

if (node === null) {

return

}

var stack = [node] //存入数组

var target

while(stack.length) { //数组长度不为0，继续循环

target = stack.shift() //取出元素

callback(target) //传入callback

Array.prototype.push.apply(stack, target.children) //将其子元素一股脑推入stack，增加长度

}

walkDom(document, function(node) {console.count()}) //包含document节点

document.querySelectorAll('*').length //数量比上面输出的少1，因为不包含document节点

在循环模式中，shift方法可以换成pop，从尾部取出元素；push方法可以换成unshift从头部添加元素。不同的顺序，影响了是「广度优先」还是「深度优先」。

场景2：在 nodejs 运行时里遍历文件目录

子场景1：同步模式

方案1：递归

var fs = require('fs')

var Path = require('path')

function readdirs(path) {

var result = { //构造文件夹数据

path: path,

name: Path.basename(path),

type: 'directory'

}

var files = fs.readdirSync(path) //拿到文件目录下的所有文件名

result.children = files.map(function(file) {

var subPath = Path.resolve(path, file) //拼接为绝对路径

var stats = fs.statSync(subPath) //拿到文件信息对象

if (stats.isDirectory()) { //判断是否为文件夹类型

return readdirs(subPath) //递归读取文件夹

}

return { //构造文件数据

path: subPath,

name: file,

type: 'file'

}

})

return result //返回数据

}

var cwd = process.cwd()

var