Dojo是目前最为强大的j s框架，它在自己的Wiki上给自己下了一个定义，dojo是一个用JavaScript编写的开源的DHTML工具箱。dojo很想做一个“大一统”的 工具箱，不仅仅是浏览器层面的，野心还是很大的。Dojo包括ajax, browser, event, widget等跨浏览器API，包括了JS本身的语言扩展，以及各个方面的工具类库，和比较完善的UI组件库，也被广泛 应用在很多项目中，他的UI组件的特点是通过给html标签增加tag的方式进行扩展，而不是通过写JS来生成，dojo的API模仿Java类库的组织 方式。 用dojo写Web OS可谓非常方便。dojo现在已经4.0了，dojo强大的地方在于界面和特效的封装，可以让开发者快速构建一些兼容标准的界面。优点：库相当完善，发展时间也比较长，功能强大，据说利用dojo的io.bind()可以实现comet，看见其功能强大非一般，得到IBM和SUN的支持缺点：文件体积比较大，200多KB，初次下载相当慢，此外，dojo的类库使用显得不是那么易用，j s语法增强方面不如prototype。Prototype （JS OO library）：是一个非常优雅的JS库，定义了JS的面向对象扩展，DOM操作API，事件等等，以prototype为核心，形成了一个外围的各种各样 的JS扩展库，是相当有前途的JS底层框架，值得推荐，感觉也是现实中应用最广的库类（RoR集成的AJAX JS库），之上还有 Scriptaculous 实现一些JS组件功能和效果。优点：基本底层，易学易用，甚至是其他一些js特效开发包的底层，体积算是最小的了。缺点：如果说缺点，可能就是功能是他的弱项Scriptaculous （JS UI component based on prototype）：Scriptaculous是基于prototype.js框架的JS效果。包含了6个js文件，不同的文件对应不同的js效果，所以说，如果底层用 prototype的话，做js效果用Scriptaculous那是再合适不过的了，连大名鼎鼎的digg都在用他，可见不一般优点：基于prototype是最大的优点，由于使用prototype的广泛性，无疑对用户书锦上添花，并且在《ajax in action》中就拿Scriptaculous来讲述js效果缺点：刚刚兴起，需要时间的磨练yui-ext (JS UI component)：基于Yahoo UI的扩展包yui-ext是具有CS风格的Web用户界面组件 能实现复杂的Layout布局，界面效果可以和backbase媲美，而且使用纯javascript代码开发。真正的可编辑的表格Edit Grid，支持XML和Json数据类型，直接可以迁入grid。许多组件实现了对数据源的支持，例如动态的布局，可编辑的表格控件，动态加载的Tree 控件、动态拖拽效果等等。1.0 beta版开始同Jquery合作，推出基于jQuery的Ext 1.0，提供了更多有趣的功能。优点：结构化，类似于java的结构，清晰明了，底层用到了Jquery的一些函数，使整合使用有了选择，最重要的一点是界面太让让人震撼了。缺点：太过复杂，整个界面的构造过于复杂。Jquery ：jQuery是一款同prototype一样优秀js开发库类，特别是对css和XPath的支持，使我们写js变得更加方便！如果你不是个js高手又想写出优 秀的js效果，jQuery可以帮你达到目的！并且简介的语法和高的效率一直是jQuery追求的目标，优点：注重简介和高效，js效果有yui-ext的选择，因为yui-ext 重用了很多jQuery的函数缺点：据说太嫩，历史不悠久。Mochikit ：MochiKit自称为一个轻量级的js框架。MochiKit 主要受到 Python 和 Python 标准库提供的很多便利之处的启发，另外还缓解了浏览器版本之间的不一致性。其中的 MochiKit.DOM 尤其方便，能够以比原始 JavaScript 更友好的方式处理 DOM 对象。MochiKit.DOM 大部分都是针对 XHTML 文档定制的，如果与 MochiKit 和 Ajax 结合在一起，使用 XHTML 包装的微格式尤其方便。Mochikit可以直接对字符串或者数字格式化输出，比较实用和方便。它还有自己的 js 代码解释器优点：MochiKit.DOM这部分很实用，简介也是很突出的缺点：轻量级的缺点mootools ：MooTools是一个简洁，模块化，面向对象的JavaScript框架。它能够帮助你更快，更简单地编写可扩展和兼容性强的JavaScript代码。Mootools跟prototypejs相类似，语法几乎一样。但它提供的功能要比prototypejs多，而且更强大。比如增加了动画特效、拖放操作等等。优点：可以定制自己所需要的功能，可以说是prototypejs的增强版。缺点：不大不小，具体应用具体分析moo.fx ：moo.fx是一个超级轻量级的javascript特效库（7k）,能够与prototype.js或mootools框架一起使用。它非常快、易于使用、跨浏览器、符合标准，提供控制和修改任何HTML元素的CSS属性，包括颜色。它内置检查器能够防止用户通过多次或疯狂点击来破坏效果。moo.fx整体采用模块化设计，所以可以在它的基础上开发你需要的任何特效。优点：小块头有大能耐缺点：这么小了，已经不错了
在实际的工作和业务需求中，我们经常会碰到树形数据结构，比如公司组织架构、组织层级、省市县或者事物的分类等等数据。那么在JavaScript中如何将数组转为树形结构和树形结构转为数组，本文就详细的来探究一下。
先来看看给出了一组怎样的数据，转换为怎样的树形结构。
后台接口返回或者面试官给你的数据：
期望的处理后的数据：
如果后台给了一个这样的数据说让前端自己去转换为树形结构或者面试官给你一组这样的数据让你手写一个转换方法，你会怎么处理？
1、递归实现
2、Map对象实现
3、filter实现
这种方法很有意思，可能大多数人想不到，也是从大佬处学到的(读书人的是怎么能叫抄呢，应该叫“窃”）。
1、reduce取树行数据的所有子集
2、递归实现
3、广度优先遍历法
title: JS树结构数据的遍历
date: 2022-04-14
description: 针对项目中出现树形结构数据的时候，我们怎样去操作他
项目中我们会经常出现对树形结构的遍历、查找和转换的场景，比如说DOM树、族谱、社会机构、组织架构、权限、菜单、省市区、路由、标签等等。那针对这些场景和数据，我们又如何去遍历和操作，有什么方式或者技巧可以简化我们的实现思路。下面我们将针对常规出现的场景去总结一下我们的遍历方式
树的特点
1、每个节点都只有有限个子节点或无子节点；
2、没有父节点的节点称为根节点；
3、每一个非根节点有且只有一个父节点；
4、除了根节点外，每个子节点可以分为多个不相交的子树；
5、树里面没有环路
下面的图片表示一颗树
在下面的JS中我们由多棵树组成我们的数据
在这数据中我们如何评判数据是否为叶节点（也就是最后一级），我们每个节点都会存在children属性，如果不存在children属性或者children不是一个数组或者children为数组且长度为0我们则认为他是一个叶节点
我们针对树结构的操作离不开遍历，遍历的话又分为广度优先遍历、深度优先遍历。其中深度优先遍历可以通过递归和循环的方式实现，而广度优先遍历的话是非递归的
从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。即访问树结构的第n+1层前必须先访问完第n层。
简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。
所以我们的实现思路是，维护一个队列，队列的初始值为树结构根节点组成的列表，重复执行以下步骤直到队列为空：
取出队列中的第一个元素，进行访问相关操作，然后将其后代元素（如果有）全部追加到队列最后。
深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止
1、先序遍历
访问子树的时候，先访问根再访问根的子树
2、后序遍历
访问子树的时候，先访问子树再访问根
1、先序遍历
先序遍历与广度优先循环实现类似，要维护一个队列，不同的是子节点不追加到队列最后，而是加到队列最前面
2、后序遍历
后序遍历就略微复杂一点，我们需要不断将子树扩展到根节点前面去，执行列表遍历，并且通过一个临时对象维护一个id列表，当遍历到某个节点如果它没有子节点或者它本身已经存在于我们的临时id列表，则执行访问操作，否则继续扩展子节点到当前节点前面
对于树结构的遍历操作，其实递归是最基础，也是最容易理解的。递归本身就是循环的思想，所以可以用循环来改写递归,以上的方式在项目中已经廊括了大部分的场景了，我们在日常开发中可以根据场景或者需要去选择我们的遍历方式，或者基于此对他进行调整和优化，至于每种方式的空间复杂度和时间复杂度我们在这个地方就不去尝试了，各位感兴趣可以自己去验证。
广度优先搜索
树的遍历
深度优先搜索
图文详解两种算法：深度优先遍历（DFS）和广度优先遍历（BFS）
二叉树遍历（前序，后序，中序，层次）递归与迭代实现JavaScript
JS树结构操作:查找、遍历、筛选、树和列表相互转换
