歡迎光臨
每天分享高質量文章

淺談 JavaScript 處理樹形結構的幾個場景與方案

前言

近日,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 處理樹形結構的幾種方法,希望看過後對你有幫助。

來自:工業聚(@工業聚)

鏈接:https://github.com/Lucifier129/Lucifier129.github.io/issues/4


赞(0)

分享創造快樂