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

Lucifier129 · 2015-06-12T06:19:26Z

作者: 工业聚
日期：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 处理树形结构的几种方法，希望看过后对你有帮助。

The text was updated successfully, but these errors were encountered:

xuexb · 2015-06-12T06:41:08Z

mark下,然后慢慢品尝~

fengchang · 2015-06-12T11:48:25Z

LZ可是在起点写过小说？

Lucifier129 · 2015-06-12T11:59:15Z

@fengchang 哇，被你发现了～～

0704681032 · 2015-06-12T13:21:13Z

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

Lucifier129 · 2015-06-12T14:04:00Z

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

angrilove · 2015-06-13T10:29:59Z

蛮好

tomieric · 2015-06-13T13:33:45Z

mark,多种实现方式，赞

Pentium286 · 2015-06-15T00:39:57Z

mark

fengchang · 2015-06-15T17:25:44Z

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

Lucifier129 · 2015-06-16T01:58:59Z

@fengchang 握手，感谢~

yiakwy · 2015-06-18T15:25:10Z

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

FengZeming · 2016-03-05T04:52:59Z

非常好多谢

dengnan123 · 2018-09-04T04:02:44Z

学习了

qcoke · 2019-04-19T10:51:02Z

mark 一下，数学功底不错。

Bourne115 · 2019-08-15T08:38:40Z

mark了感谢LZ

rcx100 · 2019-12-12T08:04:53Z

mark 感谢

Killea · 2020-10-03T18:50:12Z

写的很好。我之前只写出了方案1：递归模式。之前自己也想写循环，没想出解法。哈哈。
现在我从你这学会了方案2：循环模式，感觉在超大对象用循环更好，因为浏览器的栈有大小限制。

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

Lucifier129 commented Jun 12, 2015

xuexb commented Jun 12, 2015

fengchang commented Jun 12, 2015

Lucifier129 commented Jun 12, 2015

0704681032 commented Jun 12, 2015

Lucifier129 commented Jun 12, 2015

angrilove commented Jun 13, 2015

tomieric commented Jun 13, 2015

Pentium286 commented Jun 15, 2015

fengchang commented Jun 15, 2015

Lucifier129 commented Jun 16, 2015

yiakwy commented Jun 18, 2015

FengZeming commented Mar 5, 2016

dengnan123 commented Sep 4, 2018

qcoke commented Apr 19, 2019

Bourne115 commented Aug 15, 2019

rcx100 commented Dec 12, 2019

Killea commented Oct 3, 2020

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

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

Comments

Lucifier129 commented Jun 12, 2015

前言

场景1：遍历 DOM 树

方案1：递归模式

方案2：循环模式

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

子场景1：同步模式

方案1：递归

方案2：循环

子场景2：异步模式

方案1：过程式 Promise

方案2：ES6-class + ES6-Promise

结语

xuexb commented Jun 12, 2015

fengchang commented Jun 12, 2015

Lucifier129 commented Jun 12, 2015

0704681032 commented Jun 12, 2015

Lucifier129 commented Jun 12, 2015

angrilove commented Jun 13, 2015

tomieric commented Jun 13, 2015

Pentium286 commented Jun 15, 2015

fengchang commented Jun 15, 2015

Lucifier129 commented Jun 16, 2015

yiakwy commented Jun 18, 2015

FengZeming commented Mar 5, 2016

dengnan123 commented Sep 4, 2018

qcoke commented Apr 19, 2019

Bourne115 commented Aug 15, 2019

rcx100 commented Dec 12, 2019

Killea commented Oct 3, 2020