知識星球
前言
近日，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