以下定义摘自互联网。
在计算机科学中，树是非常有用的抽象概念。我们形象的去描述一棵树，一个家族的老祖可能有两个儿子，这两个儿子一个有一个儿子，一个有三个儿子，像这样发展下去的一个族谱，就是一个树，如图所示。
就像一棵真正的树一样，我们把老祖称为树根,两个字儿是分叉开的两个树枝，这两棵树枝可以继续向下分成N个树枝，循环下去，一直到长出叶子为止。
我们把老祖或者树根称为根（root）节点，老祖的儿子称为子节点，每个儿子作为根节点又可以形成一棵树，我们把这样的树称为根节点的子树。
树的标准定义：
树（tree）是包含n（n>0）个节点的有穷集合，其中：
- 每个元素称为节点（node）；
- 有一个特定的节点被称为根节点或树根（root）。
- 除根节点之外的其余数据元素被分为m（m≥0）个互不相交的结合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。
树具有以下特点：
- 每个节点有零个或多个子节点。
- 每个子节点只有一个父节点。
- 没有父节点的节点称为根节点。
树形数据结构通常用来描述目录结构、菜单结构、组织机构树、级联选择器等等。
树形结构是n维的数据结构，但是树形数据结构在关系型数据库中通常的存储形态为二维形式，数据库中使用单表存储，必有列id和列parentId，比如如下的表结构：
id parentId title
1 0 地球
2 1 亚洲
3 1 欧洲
4 2 中国
5 2 韩国
6 3 英国
7 3 法国
ps：如果是层数固定的树，还可以使用多表存储，处理起来会简单很多，本篇中主要讨论不定层数的树。
那么返回到前端的数据，以json为例，一般是如下格式：
{
treeData: [
{id: 1, parentId: 0, title: 地球},
{id: 2, parentId: 1, title: 亚洲},
{id: 3, parentId: 1, title: 欧洲},
{id: 4, parentId: 2, title: 中国},
{id: 5, parentId: 2, title: 韩国},
{id: 6, parentId: 3, title: 英国},
{id: 7, parentId: 3, title: 法国},
]
}
用一维数组来表示的n维树，如何处理这种数据结构呢？并且在处理过程中能保证较高的性能。
如果我们要从根到叶子的顺序去生成一个菜单
- 先寻找出所有的根节点（地球），判断条件为：数据节点的parentId没有对应的数据节点，在寻找的过程中需要第二个遍历，那么，假如有m条数据的话，需要遍历m*m次后，就可以找到所有的根节点了
- 先渲染根节点，然后从根节点开始，找到当前节点的儿子节点并渲染，然后用相同的算法递归儿子节点。寻找儿子节点的过程中需要遍历一次数据，判断条件为：数据节点的parentId等于当前节点的id。那么渲染完所有节点后，需要再次遍历m*m次。
按常规做法，一共会遍历 m * m * 2 次，遍历次数和数据条目是指数递增关系，当数据量增大时，这种遍历相当于一个瞬时的死循环，cpu使用率会瞬时上升，给用户的感受就是页面卡住或者卡死了。
- 设计一个树节点对象，此对象拥有parent和children属性，parent是父节点，也是树节点数据，children是儿子树节点的数组。
- 那么问题就变成了，如何在遍历次数最少的情况下将所有数据节点都转换成树节点对象。
// 树节点对象
function TreeBean(data){
this.code ;
this.pcode;
this.data;
this.root=false;
this.parent;
this.children=[];
this._init=function (data){
this.data=data;
this.code=data.code;
this.pcode=data.pcode;
}
this._init(data);
}
下一篇主要对本章提出的思路做出实现。