weixin_39972768
2021-01-01 00:32 阅读 6

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

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

前言

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

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

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

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

场景1:遍历 DOM 树

方案1:递归模式

 javascript
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:循环模式

 javascript
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:递归

 javascript
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:循环

 javascript
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中,去查看吧

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

子场景2:异步模式

方案1:过程式 Promise

 javascript
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

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

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

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

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

/**
* 判断path是否存在
*  {string} path 路径
*  {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 处理树形结构的几种方法,希望看过后对你有帮助。

该提问来源于开源项目:Lucifier129/Lucifier129.github.io

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

17条回答 默认 最新

  • weixin_39598308 weixin_39598308 2021-01-01 00:32

    mark下,然后慢慢品尝~

    点赞 评论 复制链接分享
  • weixin_39682560 weixin_39682560 2021-01-01 00:32

    LZ可是在起点写过小说?

    点赞 评论 复制链接分享
  • weixin_39972768 weixin_39972768 2021-01-01 00:32

    哇,被你发现了~~

    点赞 评论 复制链接分享
  • weixin_39539588 weixin_39539588 2021-01-01 00:32

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

    点赞 评论 复制链接分享
  • weixin_39972768 weixin_39972768 2021-01-01 00:32

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

    点赞 评论 复制链接分享
  • weixin_40003512 weixin_40003512 2021-01-01 00:32

    蛮好

    点赞 评论 复制链接分享
  • weixin_39919089 weixin_39919089 2021-01-01 00:32

    mark,多种实现方式,赞

    点赞 评论 复制链接分享
  • weixin_39595008 weixin_39595008 2021-01-01 00:32

    mark

    点赞 评论 复制链接分享
  • weixin_39682560 weixin_39682560 2021-01-01 00:32

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

    点赞 评论 复制链接分享
  • weixin_39972768 weixin_39972768 2021-01-01 00:32

    握手,感谢~

    点赞 评论 复制链接分享
  • weixin_39612332 weixin_39612332 2021-01-01 00:32

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

    点赞 评论 复制链接分享
  • weixin_39816062 weixin_39816062 2021-01-01 00:32

    非常好多谢

    点赞 评论 复制链接分享
  • weixin_39932458 weixin_39932458 2021-01-01 00:32

    学习了

    点赞 评论 复制链接分享
  • weixin_39995943 weixin_39995943 2021-01-01 00:32

    mark 一下,数学功底不错。

    点赞 评论 复制链接分享
  • weixin_39945445 weixin_39945445 2021-01-01 00:32

    mark了 感谢LZ

    点赞 评论 复制链接分享
  • weixin_39623620 weixin_39623620 2021-01-01 00:32

    mark 感谢

    点赞 评论 复制链接分享
  • weixin_39703982 weixin_39703982 2021-01-01 00:32

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

    点赞 评论 复制链接分享

相关推荐