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

作者: 工业聚 日期：2015-06-12

前言

近日，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 tree = readdirs(cwd)
fs.writeFileSync(Path.join(cwd, 'tree.json'), JSON.stringify(tree)) //保存在tree.json中，去查看吧

将上面的代码保存在 tree.js 中，然后在当前文件夹打开命令行，输入node tree.js，目录信息保存在生成tree.json文件中。

方案2：循环

var fs = require('fs')
var Path = require('path')

function readdirs(path) {
    var result = { //构造文件夹数据
        path: path,
        name: Path.basename(path),
        type: 'directory'
    }
    var stack = [result] //生成一个栈数组
    while (stack.length) { //如果数组不为空，读取children
        var target = stack.pop() //取出文件夹对象
        var files = fs.readdirSync(target.path) //拿到文件名数组
        target.children = files.map(function(file) {
            var subPath = Path.resolve(target.path, file) //转化为绝对路径
            var stats = fs.statSync(subPath) //拿到文件信息对象
            var model = { //构造文件数据结构
                path: subPath,
                name: file,
                type: stats.isDirectory() ? 'directory' : 'file'
            }
            if (model.type === 'directory') {
                stack.push(model) //如果是文件夹，推入栈
            }
            return model //返回数据模型
        })
    }
    return result //返回整个数据结果
}

var cwd = process.cwd()
var tree = readdirs(cwd)
fs.writeFileSync(Path.join(cwd, 'tree.json'), JSON.stringify(tree)) //保存在tree.json中，去查看吧

循环策略中的pop跟shift，push跟unshift也可以互换以调整优先级，甚至用可以用splice方法更精细的控制stack数组。循环模式比递归模式更可控。

子场景2：异步模式

方案1：过程式 Promise

var fs = require('fs')
var Path = require('path')
//promise包装的fs.stat方法
var stat = function(path) {
    return new Promise(function(resolve, reject) {
        fs.stat(path, function(err, stats) {
            err ? reject(err) : resolve(stats)
        })
    })
}
//promise包装的fs.readdir方法
var readdir = function(path) {
    return new Promise(function(resolve, reject) {
        fs.readdir(path, function(err, files) {
            err ? reject(err) : resolve(files)
        })
    })
}
//promise包装的fs.writeFile
var writeFile = function(path, data) {
    return new Promise(function(resolve, reject) {
        fs.writeFile(path, JSON.stringify(data || ''), function(err) {
            err ? reject(err) : resolve
        })
    })
}

function readdirs(path) {
    return readdir(path) //异步读取文件夹
    .then(function(files) { //拿到文件名列表
        var promiseList = files.map(function(file) { //遍历列表
            var subPath = Path.resolve(path, file) //拼接为绝对路径
            return stat(subPath) //异步读取文件信息
            .then(function(stats) { //拿到文件信息
                //是文件夹类型的，继续读取目录，否则返回数据
                return stats.isDirectory() ?
                readdirs(subPath) : {
                    path: subPath,
                    name: file,
                    type: 'file'
                }
            })
        })
        return Promise.all(promiseList) //等待所有promise完成
    })
    .then(function(children) { //拿到包含所有数据的children数组
        return { //返回结果
            path: path,
            name: Path.basename(path),
            type: 'directory',
            children: children
        }
    })
}

var cwd = process.cwd()

readdirs(cwd)
.then(writeFile.bind(null, Path.join(cwd, 'tree.json'))) //保存在tree.json中，去查看吧
.catch(console.error.bind(console)) //出错了就输出错误日志查看原因

上面的函数都能工作，但都是一个个function的调用，显得太「过程式」；

能不能用面向对象的方式来写呢？

当然可以。

其实面向对象的写法，更清晰。

为了更加语义化，以及增显逼格。

我们用 ES6 的 class 来写这个树形结构类。

方案2：ES6-class + ES6-Promise

import fs from 'fs'
import {join, resolve, isAbsolute, basename, extname, dirname, sep} from 'path'

/**
 * 获取目录下的所有文件
 * @param {string} path
 * @return {promise} resolve files || reject error
 */
let readdir = (path) => {
    return new Promise((resolve, reject) => {
        fs.readdir(path, (err, files) => {
            err ? reject(err) : resolve(files)
        })
    })
}

/**
* 将data写入文件
* @param {string} path 路径
* @param {data} data
* @return {promise} resolve path || reject error
*/
let writeFile = (path, data) => {
    return new Promise((resolve, reject) => {
        fs.writeFile(path, data, (err) => {
            err ? reject(err) : resolve(path)
        })
    })
}

/**
* 获取文件属性
* @param {string} path
* @return {promise} resolve stats || reject error
*/
let stat = (path) => {
    return new Promise((resolve, reject) => {
        fs.stat(path, (err, stats) => {
            err ? reject(err) : resolve(stats)
        })
    })
}

/**
* 判断path是否存在
* @param {string} path 路径
* @return {promise} resolve exists
*/
let exists = (path) => {
    return new Promise((resolve) => fs.exists(path, resolve))
}


//文档类
class Document {
    constructor(path) {
        this.path = path
        this.name = basename(path)
    }
    //存在性判断
    exists() {
        return exists(this.path)
    }
    //异步获取文件信息
    stat() {
        return stat(this.path)
    }
    //输出基本数据
    json() {
        return JSON.stringify(this)
    }
    //将基本数据保存在path路径的文件中
    saveTo(path) {
        if (isAbsolute(path)) {
            return writeFile(path, this.json())
        }
        return writeFile(resolve(this.path, path), this.json())
    }
}

//文件类，继承自文档类
class File extends Document {
    constructor(path) {
        super(path) //必须先调用超类构造方法
        this.type = 'file' //type 为 file
        this.extname = extname(path) //新增扩展名
    }
    //写入数据
    write(data = '') {
        return writeFile(this.path, data)
    }
    //其他文件特有方法如 read unlink 等
}


//文件夹类，继承自文档类
class Directory extends Document {
    constructor(path) {
        super(path) //必须先调用超类构造方法
        this.type = 'directory'
    }
    //读取当前文件夹
    readdir() {
        return readdir(this.path) //读取目录
        .then((files) => { //拿到文件名列表
            let promiseList = files.map((file) => {
                let subPath = resolve(this.path, file) //拼接为绝对路径
                return stat(subPath) //获取文件信息
                .then((stats) => {
                    //根据文件信息，归类为Directory或File类型
                    return stats.isDirectory() ?
                    new Directory(subPath) :
                    new File(subPath)
                })
            })
            return Promise.all(promiseList)
        })
        .then((children) => { //拿到children数组
            this.children = children //保存children属性
            return children //返回children
        })
    }
    //深度读取文件目录
    readdirs() {
        return this.readdir() //读取当前文件夹
        .then((children) => { //拿到children
            let promiseList = []
            children.map((child) => {
                if (child instanceof Directory) { //是文件夹实例，继续深度读取文件目录
                    promiseList.push(child.readdirs())
                }
            })
            return Promise.all(promiseList) //等待所有子元素深度读取目录完毕
        })
        .then(() => this) //返回this
    }
    //其他文件夹特有方法如 addFile removeFile addDir remveDir 等
}

let cwd = process.cwd()

new Directory(cwd)
.readdirs()
.then((tree) => {
    tree.saveTo('tree.json') //让它自己保存在tree.json里
})
.catch(console.error.bind(console)) //输出错误日志

因为当前 JavaScript 引擎对 ES6 的支持度还不够，所以上述代码不能直接运行。可以通过以下两种方式来验证代码能不能跑起来。

第一种，先 npm install -g bable 全局安装 babel 工具，再以 babel-node tree.js的方式取代 node tree.js 来运行上述代码。

第二种，将上述代码黏贴到 https://babeljs.io/repl/，拿到编译为 ES5 的代码，将代码保存在 tree.js 文件中，以 ES5 的形式执行。

结语

以上就是我知道的一些用 JavaScript 处理树形结构的几种方法，希望看过后对你有帮助。

Jun 12 '15 06:06 Lucifier129

mark下,然后慢慢品尝~

Jun 12 '15 06:06 xuexb

LZ可是在起点写过小说？

Jun 12 '15 11:06 fengchang

@fengchang 哇，被你发现了～～

Jun 12 '15 11:06 Lucifier129

我x。。在起点写过小说。。

Jun 12 '15 13:06 0704681032

无人问津的太监文，不足挂齿。

Jun 12 '15 14:06 Lucifier129

蛮好

Jun 13 '15 10:06 angrilove

mark,多种实现方式，赞

Jun 13 '15 13:06 tomieric

mark

Jun 15 '15 00:06 Pentium286

我猜也不会有别人用这个网名...当年看了你的小说简介还挺看好的，记得给你投了你的第二张推荐票，还给你留了条评论鼓励。可惜....没想到啊，世界真是小

Jun 15 '15 17:06 fengchang

@fengchang 握手，感谢~

Jun 16 '15 01:06 Lucifier129

喜欢的楼主对于ES6的分析，其实主要是用栈，和队列构造深度搜索，和广度搜索。DOM已经将树转化为了完全二叉树，所以用silibingElement搜索蛮方便。我之前写的一个PyMatrix框架，也是大量用到这个技巧。比较赞赏的是，楼主应用了Promise语法，不过现在更先进的 Asyncro ... wait 语法也很好。卤煮在这个demo中展示了良好的抽象能力，赞一个