自然界的树，不需要我来解释。不过对于计算机中的树结构，可难倒了一大片人。其实，我们日常生活中会经常接触到树结构。
比如，一个公司的结构划分。公司最大的当然是老板了，老板将公司划分为多个大部门，各个大部门下又划分为多个小部门，而每个小部门内部还可能会划分为多个小组，组内还会根据工作种类的不同划分为不同的岗位。这里，如果需要查询这个公司总共有多少岗位，你会怎么办？想想都头大啊。
再比如，我们计算机中存储文件的时候，一个文件夹下面有多个子文件夹，而这些子文件夹还会有其他子子文件夹，还可能会有更多。如果我们要找某个文件，在不知道它在哪个文件夹的时候，我们会使用计算机的搜索功能。那么，计算机如何来实现这个功能呢？想想都头大啊。
这篇文章就来介绍一下我用JS实现的树结构及其常用操作。
介绍
了解一点计算机的朋友都知道，树是由一堆具有相同结构的元素嵌套而来的。它根据不同的特性分为很多的种类，比如二叉树，满树，红黑树，B树，B+树等等等。而树的嵌套结构就决定了，它相关的算法多数可以通过递归来解决，比如二叉树的先序遍历、中序遍历等。
废话不多说了，直接来看看实现代码吧。
实现一棵树
一棵树最重要的东西就是它的节点了，包括当前节点及其子节点，另外还需要一个ID来唯一标识每一个节点。所以我这里的节点如下：
var nodeID = 1;
Ycc.Tree = function() {
/**
* 节点的自增ID，不允许修改，且每个对象必须唯一
* @type {number}
*/
this.$id = nodeID++;
/**
* 节点的父节点ID，不允许修改
* @type {null|Ycc.Tree}
*/
this.$parentID = null;
/**
* 节点的子节点列表
* @type {Array}
*/
this.children = [];
/**
* 节点所携带的数据
* @type {any}
*/
this.data = null;
};
上面代码中Ycc为一个全局变量，是我真正做的一个项目名，可以忽略。
可以看到，这里除了自己的ID外，还使用了parentID，这样在寻找父节点的时候会非常方便。
另外，借助js的灵活性，直接使用children数组表示当前节点的子节点。
如果我告诉你，一棵树我们就写完了，你会感到惊讶吗？
事实确实如此，树是一个集合的概念，集合内元素的结构就决定了树的结构。只是，如果这样我们就需要手动的去设置ID和parentID，以此来保证它们的嵌套。
所以，为了丰富一棵树，我们还需要新增一些便利的方法，来保证树的特性，而不用手动去设置。
给树添加常用的操作
操作一：根据json初始化一棵树
在js及其他语言中，最常用的数据结构莫过于json了。比如，如下结构是示例中的一个json，我们会根据它来生成对应的树。
{
data:'/',
children:[
{
data:"a",
children:[
{
data:"d",
children:[
{
data:"g"
},
{
data:"h"
},
{
data:"i"
},
]
},
{
data:"e",
children:[
{
data:"j"
},
{
data:"k"
},
{
data:"l"
},
]
},
{
data:"f"
},
]
},
{
data:"b",
children:[
{
data:"m"
},
{
data:"n"
},
]
},
{
data:"c",
children:[
{
data:"o"
},
{
data:"p"
},
{
data:"q"
},
]
}
]
}
这里的实现代码如下：
Ycc.Tree.createByJSON = function (json) {
var root = new Ycc.Tree();
root.data = json.data;
if(Ycc.utils.isArray(json.children) && json.children.length>0){
for(var i=0;i<json.children.length;i++){
root.addChildTree(Ycc.Tree.createByJSON(json.children[i]));
}
}
return root;
};
上面代码，第2行，新建了一个root，表示这棵树的根节点，并在第3行将json中的数据附加给节点。
第4行判断节点是否有子节点，如果有子节点，在第5~7行我们递归调用方法createByJSON来为每一个子节点创建一颗子树，并调用addChildTree方法添加到我们的root。
最后返回了我们的树根。
这个addChildTree方法，我们暂时只需知道，它的作用是给当前节点添加一颗子树，稍后给出其实现。
可以看出，这段代码很明显的使用了分治算法策略。
即，将我们的问题分解成多个子问题，子问题使用相同的解决方法（createByJSON），待子问题解决完之后，将子问题合并（addChildTree），即可解决我们的原问题。
操作二：添加一颗子树
Ycc.Tree.prototype.addChildTree = function (tree) {
if(tree.$parentID) return console.error("sub tree's parent has exist! can't add!",tree);
tree.$parentID = this.$id;
this.children.push(tree);
return this;
};
添加子树，实质上只是添加一个节点ID的引用，即ID和parentID之间的关联关系。
上面代码中，第2行判断了树根，第3~4行就是在操作它们的关联关系。
操作三：获取树的最大深度
树的最大深度是指，从树根开始向下，总共有多少层级。
比如，我们文章开头，对于公司示例，因为有可能有的大部门不划分小部门，这个最大深度是指公司最多划分了几层。
对于文件夹示例，因为有的文件夹可能为空，这个最大深度是指文件夹最多能点到哪儿。
实现代码如下：
Ycc.Tree.prototype.getDepth = function () {
var self = this;
var dep = 1;
if(self.children.length>0){
for(var i=0;i<self.children.length;i++){
var subDep = self.children[i].getDepth();
dep = subDep+1>dep?subDep+1:dep;
}
}
return dep;
};
这个地方也用到了分治策略。
第4行判断有没子级，第5~7行求出子级的最大深度，将其加1与当前最大深度做比较，取最大值即为我们所求的最大深度。
操作四：树的遍历
我总共写了四种遍历方法。分别是：普通遍历 左子树优先遍历 右子树优先遍历 按层级向下遍历。
这里贴一个普通遍历，感兴趣的可以看看其他的遍历方式。
Ycc.Tree.prototype.itor = function (option) {
var self = this;
function each(cb) {
if(cb.call(self,self)) return true;
if(self.children.length>0){
for(var i=0;i<self.children.length;i++){
if(self.children[i].itor().each(cb)) return true;
}
}
return false;
}
}
地址为：https://github.com/lizhiqianduan/ycc/blob/develop/src/Ycc.Tree.class.js
总结
对于程序员，树结构是经常遇到的，我们的HTML文档就是一棵树，xml文件也是一棵树。
各个省市县也可以构成一颗树，淘宝京东的栏目分类也是一棵树，任何有嵌套结构的数据都可以构成一棵树。
所以，掌握树相关的算法是很有必要的。
最后附一个示例，是我实现的一个模拟windows的文件管理器，点开链接看看吧。
http://www.lizhiqianduan.com/products/ycc/examples/tree/
网友评论