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

前言

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

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

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

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

场景1:遍历 DOM 树

方案1:递归模式

将上述代码黏贴到任意页面的控制台 console 中执行。

方案2:循环模式

在循环模式中,shift方法可以换成pop,从尾部取出元素;push方法可以换成unshift从头部添加元素。不同的顺序,影响了是「广度优先」还是「深度优先」。

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

子场景1:同步模式

方案1:递归

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

方案2:循环

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

子场景2:异步模式

方案1:过程式 Promise

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

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

当然可以。

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

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

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

方案2:ES6-class + ES6-Promise

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

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

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

结语

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

1 4 收藏 评论

可能感兴趣的话题



直接登录
跳到底部
返回顶部